第8.5章: 投影

概述

投影是在算法使用某个元素之前，先对作用于该元素的一个函数。算法不直接处理元素，而是处理投影后的值。这样一来，算法就可以基于派生字段或计算出来的值工作，而不必修改底层的数据结构。

投影在概念上很简单：算法看到的是 proj(x) 而不是 x。但要写出正确且高效的代码，理解投影如何与迭代器、引用以及算法语义相互作用是必不可少的。

1. 什么是投影？

投影是一个一元函数，在算法处理每个元素之前先作用于该元素。例如，如果有一个含两个数值字段的结构体，我们可以用投影按其中一个字段排序。

struct Record {
    ::std::size_t index;
    ::std::ptrdiff_t offset;
};

::fast_io::vector<Record> v = {
    {3, -10},
    {1,  25},
    {2,   5}
};

// Sort by the offset field
::std::ranges::sort(v, {}, &Record::offset);
      

算法从不直接比较 Record 对象，它比较的是 &Record::offset 返回的投影值。

2. 为什么需要投影

在没有投影的时候，定制算法通常需要：

• 编写自定义的比较 lambda
• 到处重复字段名
• 手动重写算法

投影消除了这些样板代码。它让你能够指定算法该使用元素的哪一部分，而不改变算法如何工作。

3. 投影与比较器的区别

比较器定义两个投影值如何比较；投影定义比较的是元素的哪一部分。

// Comparator only:
::std::ranges::sort(v, [](auto const& a, auto const& b) {
    return a.offset < b.offset;
});

// Comparator + projection:
::std::ranges::sort(v, {}, &Record::offset);
      

投影版本更短，不需要捕获，也不会重复字段名。与 lambda 相比，它还能减小二进制体积。

4. 投影必须是纯函数且开销低

投影会被调用很多次，因此它必须：

• 纯（没有副作用）
• 低开销（最好是平凡的）
• 安全（不返回临时量的引用）

投影的行为应当和一次字段访问差不多。任何更昂贵的操作都可能破坏算法性能。

// Bad: expensive projection
::std::ranges::sort(v, {}, [](auto const& r) {
    return r.offset * r.offset * r.offset; // expensive
});
      

这会把 O(n log n) 的排序变成糟糕得多的东西。

5. 投影与引用

投影可以返回引用，但该引用必须在算法整个执行期间保持有效。返回临时量的引用是未定义行为。

// Bad: returns reference to a temporary
::std::ranges::sort(v, ::std::ranges::greater{}, [](auto const& r) -> ::std::ptrdiff_t const& {
    return r.offset + 1; // temporary
});
      

安全的投影返回：

• 字段引用
• 指针
• 小值（复制开销低）

6. 投影与稳定性

投影不会改变算法是否稳定，它只改变算法看到的内容。如果两个元素的投影值相等，稳定算法会保留它们的原始顺序。

要点

• 投影在算法看到元素之前对每个元素做一次变换。
• 投影能简化代码、减少样板。
• 投影必须是纯的、开销低的、安全的。
• 返回临时量的引用是未定义行为。
• 投影不会改变算法的稳定性。
• 使用简单的 POD 类类型可以让投影保持高效。