I just got a segmentation fault from both GCC 9.1 and clang 8.0 when using std::nth_element with the custom predicates std::less_equal or std::greater_equal:
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> vals{1, 2, 5, 1, 3, 2, 1};
std::nth_element(begin(vals), begin(vals)+2, end(vals), std::greater_equal{});
copy(cbegin(vals), cend(vals), std::ostream_iterator<int>(std::cout, "\n"));
}
In contrast, everything works as expected when using std::less or std::greater.
I believe that I understand the reason behind it: as an optimization, unguarded loops (without bounds checking) are used internally under the assumption that the predicate returns false for equal elements. I am just surprised that I can not find that requirement in the documentation.
Here is what I find in N4659:
// [...] template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp); // [...]
- Requires:
RandomAccessIteratorshall satisfy the requirements ofValueSwappable(20.5.3.2). The type of*firstshall satisfy the requirements ofMoveConstructible(Table 23) and ofMoveAssignable(Table 25).- Effects: After
nth_elementthe element in the position pointed to bynthis the element that would be in that position if the whole range were sorted, unlessnth == last. Also for every iteratoriin the range[first, nth)and every iteratorjin the range[nth, last)it holds that:!(*j < *i)orcomp(*j, *i) == false.- Complexity: [...].
From the above, I can not infer the requirement that the predicate must return false for equal elements.
Here is a quote from cppreference.com on std::nth_element:
// [...] template< class RandomIt, class Compare > void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp ); // (until C++20) // [...][...]
comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns
trueif the first argument is less than (i.e. is ordered before) the second. [...]
Although the two words less and before are displayed with italic font, I feel like there could be a more explicit hint.
Here are my questions:
- Am I correct that the predicate has to return
falsefor equal elements? - Am I missing some important statement from the standard that explicitly documents this requirement?
- Depending on answers on the above: is there anything to do on this issue (read more parts of the standard, defect report, bug report, or improve cppreference.com documentation)?