按元素地址排序

Question

我偶然发现了一种情况，库std::vector<T>使用用户提供的比较对象对容器（例如）进行排序。对于一种特定情况，用户实际上不想对容器进行排序，但排序是无条件发生的。

因此，为了尽量避免这种情况，我想尝试使用根据元素地址排序的比较对象。等价地，我们有：

std::vector nums{1, 5, 4};
auto cmp = [](auto& a, auto& b) { return &a < &b; };
std::sort(nums.begin(), nums.end(), cmp);

这是“有效的”，因为std::vector<T>元素以与向量中元素相同的顺序存储在（连续）内存位置中。最终结果是，nums即使在排序之后，向量似乎也没有被改变。

但是，一旦我替换std::vector<T>为std::array<T, N>，我就会遇到分段冲突（请参阅https://gcc.godbolt.org/z/9srehdbhG）。

我的第一个想法是我违反了https://en.cppreference.com/w/cpp/algorithm/sort中列出的类型要求：

• RandomIt必须满足ValueSwappable和LegacyRandomAccessIterator的要求。
• 解除引用的类型必须满足MoveAssignable和MoveConstructibleRandomIt的要求。
• Compare必须满足Compare的要求。

我的假设是元素的地址在整个排序过程中保持稳定 - 这几乎肯定是错误的。

那么，std::sort()我违反了哪些要求/先决条件？

Answer 1

问题在于，std::sort不仅限于通过对指定范围的元素的引用来调用比较器，它还调用辅助变量与该范围的元素之间的比较。

获取该辅助变量的地址是合法的，但进行指针比较是不合法的。

如果你切换到std::less()(&a, &b) 分段错误就会消失，但它仍然会表现得很奇怪——你的比较器在副本下并不是不变的。

这违反了排序比较函数所需的概念：

对于 [alg.binary.search] 中描述的算法以外的算法，comp 应对值进行严格的弱排序。

请注意“对值进行排序”，而不是“对对象进行排序”。这意味着除了值之外，您不能依赖被排序对象的任何属性（例如内存地址）。