操作员要求<std::stable_sort 中的常量性 [英] Requirement of operator&lt; constness in std::stable_sort

问题描述

我对 std::sort 和 std::stable_sort 的 operator< const 限定符的要求差异有点困惑.假设一个简单的结构:

I'm a bit confused about the difference in requirements of operator< const qualifier for std::sort and std::stable_sort. Suppose a simple structure:

#include <vector>
#include <algorithm>

struct Custom {
    bool operator<(const Custom& custom) /* const */{
        return true;
    };
};

如果我们尝试编译并运行这段代码，一切都会好的:

Everything is ok if we try to compile and run this code:

int main() {
    std::vector<Custom> values(3);
    std::sort(values.begin(), values.end());
    return 0;
}

但是这段带有 std::stable_sort 的代码无法编译:

But this code with std::stable_sort failed to compile:

int main() {
    std::vector<Custom> values(3);
    std::sort(values.begin(), values.end());
    return 0;
}

这是一个错误堆栈跟踪:

Here's an error stack trace:

In file included from /usr/include/c++/5/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/5/bits/char_traits.h:39,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/ostream:38,
                 from /usr/include/c++/5/iostream:39,
                 from temp.cpp:1:
/usr/include/c++/5/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = const Custom; _Iterator = __gnu_cxx::__normal_iterator<Custom*, std::vector<Custom> >]’:
/usr/include/c++/5/bits/stl_algo.h:2050:14:   required from ‘_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = __gnu_cxx::__normal_iterator<Custom*, std::vector<Custom> >; _Tp = Custom; _Compare = __gnu_cxx::__ops::_Val_less_iter]’
/usr/include/c++/5/bits/stl_algo.h:2522:26:   required from ‘void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = __gnu_cxx::__normal_iterator<Custom*, std::vector<Custom> >; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/5/bits/stl_algo.h:2782:34:   required from ‘void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Custom*, std::vector<Custom> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/5/bits/stl_algo.h:4863:28:   required from ‘void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Custom*, std::vector<Custom> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/5/bits/stl_algo.h:4897:36:   required from ‘void std::stable_sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Custom*, std::vector<Custom> >]’
temp.cpp:15:45:   required from here
/usr/include/c++/5/bits/predefined_ops.h:71:22: error: no match for ‘operator<’ (operand types are ‘const Custom’ and ‘Custom’)
       { return __val < *__it; }

所以我的问题是:是技术实现细节的结果还是存在一些支持这种行为的客观论据?

So my question is: Is it just the consequence of technical implementation details or there exists some objective arguments in favor of such behavior?

推荐答案

[alg.sorting]/2 Compare 是一个函数对象类型 (20.9).应用于 Compare 类型对象的函数调用操作的返回值，当上下文转换为 bool(第 4 条)时，产生 true，如果调用的第一个参数小于第二个参数，否则为 false.Compare comp 始终用于假设排序关系的算法.假设 comp 不会通过解引用的迭代器应用任何非常量函数.

[alg.sorting]/2 Compare is a function object type (20.9). The return value of the function call operation applied to an object of type Compare, when contextually converted to bool (Clause 4), yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

[alg.sorting]/3 对于所有采用 Compare 的算法，有一个版本使用 operator< 代替.也就是说， comp(*i, *j) != false 默认为 *i <;*j != false.

[alg.sorting]/3 For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false.

[res.on.functions]/1 在某些情况下(替换函数、处理函数、对用于实例化标准库模板组件的类型的操作)，C++ 标准库依赖于由一个 C++ 程序.如果这些组件不满足他们的要求，标准不会对实现提出任何要求.

[res.on.functions]/1 In certain cases (replacement functions, handler functions, operations on types used to instantiate standard library template components), the C++ standard library depends on components supplied by a C++ program. If these components do not meet their requirements, the Standard places no requirements on the implementation.

强调我的.通过向标准库函数提供不满足函数要求的组件，您的程序表现出未定义的行为.

Emphasis mine. Your program exhibits undefined behavior by way of supplying to a standard library function a component that doesn't meet the function's requirements.

顺便说一下，clang 拒绝了 std::sort 和 std::stable_sort.

By the way, clang rejects both std::sort and std::stable_sort.

这篇关于操作员要求<std::stable_sort 中的常量性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！