为什么std::sort不接受引用比较器？

Question

标准中关于 std::reference_wrapper 的说明指出，现在 std::sort 接受 std::reference_wrapper，这样可以通过引用传递一个比较器。

为什么 std::sort 一开始不接受引用传递的比较器呢？

- Elazar Leibovich

---

@LightnessRacesinOrbit 我不理解。如果您这样做，就可以启用计数排序器。 - Elazar Leibovich

然后你必须限制算法的实现，以便您的计数器正常工作。 - juanchopanza

现在，std::sort 接受 std::reference_wrapper。需要注意的是，sort 没有发生任何改变，如果早些时候 reference_wrapper 已经存在，它也总是能够被接受的。 - Jonathan Wakely

@ElazarLeibovich 你可以通过保持（智能）指针来实现计数排序。 - pal

Answer 1

简而言之，没有必要采用引用方式；这是一种“设计决策”。

我认为这个决策的原因主要涉及C++和标准库存在已久的一些基本原则：

- 值语义 - 尽量少地限制实现

值语义无处不在。几乎所有算法、容器等都希望其中包含的数据遵循值的正常规则，即表现得像内置类型。这也是C++类型系统的一个原因，使用户定义类型能够表现得像内置类型。

算法的实现可以自由地复制函数参数。当实现允许复制函数时，将签名限制为引用并不是非常有用；因此从一开始就允许复制。这意味着函数对象不应该包含任何状态，因为它可能不被保留；反过来，这使得函数对象非常轻便，根本没有用到引用。

关于API设计的一般性说明。对于模板等规范和标准的API设计，在最好的情况下都是一个非常重要的任务。如果委员会今天使用了r-values、引用折叠、完美转发和移动语义，是否会以不同的方式设计函数？我不知道。在我看来，通过值传递函数对象可以平衡与内部复制和移动、可能的优化以及绑定到临时对象(pr-values/x-values)相关的问题。在这里使用“通用引用”可能会更好，但我感觉遗留的论点会权衡改变的论点。

- Niall

---

有什么想法为什么算法需要“自由地复制那些函数对象”？我了解像std::set和std::map这样的数据结构需要，但我不明白为什么在算法库中看到的任何东西都需要。 - Don Hatch

@DonHatch，我没有一个“可引用”的理由给你；但我的第一个猜测可能是可能的优化或值语义原理；考虑到在早期，这些可能是基本函数指针。 - Niall

Answer 2

在C++03中，通过引用接受比较器将防止绑定到非const右值，例如函数指针表达式：

bool comp(T const&, T const&);
sort(first, last, &comp);

或者一个临时的函数对象：

struct Comparator { bool operator()(T const&, T const&) { ... } };
sort(first, last, Comparator());

在C++11中，采用万能引用来传递比较器可以避免这个问题，但这是一个不必要的改变，因为我们有reference_wrapper。

- ecatmur

---

但为什么不同时为两者提供重载呢？ - Elazar Leibovich

需求不足；提供reference_wrapper可以在不必修改每个接受函数对象的算法的情况下提供该功能。 - ecatmur