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:
RandomAccessIterator
shall satisfy the requirements ofValueSwappable
(20.5.3.2). The type of*first
shall satisfy the requirements ofMoveConstructible
(Table 23) and ofMoveAssignable
(Table 25).- Effects: After
nth_element
the element in the position pointed to bynth
is the element that would be in that position if the whole range were sorted, unlessnth == last
. Also for every iteratori
in the range[first, nth)
and every iteratorj
in 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
true
if 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
false
for 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)?