1

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);

// [...]
  1. Requires: RandomAccessIterator shall satisfy the requirements of ValueSwappable (20.5.3.2). The type of *first shall satisfy the requirements of MoveConstructible (Table 23) and of MoveAssignable (Table 25).
  2. Effects: After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted, unless nth == last. Also for every iterator i in the range [first, nth) and every iterator j in the range [nth, last) it holds that: !(*j < *i) or comp(*j, *i) == false.
  3. 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:

  1. Am I correct that the predicate has to return false for equal elements?
  2. Am I missing some important statement from the standard that explicitly documents this requirement?
  3. 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)?
Julius
  • 1,816
  • 10
  • 14
  • 1
    If the first argument is equal to the second, it isn't _less than_ the second. I don't believe that's ambiguous. – Mat Aug 03 '19 at 11:23
  • 1
    Possible duplicate or at least very much related: https://stackoverflow.com/q/1293231/5910058 – Jesper Juhl Aug 03 '19 at 11:27
  • 2
    @JesperJuhl: Thank you, that made me find it [28.7(3) of N4659](http://open-std.org/JTC1/SC22/WG21/docs/papers/2017/n4659.pdf#section.28.7): "[...] For algorithms other than those described in 28.7.3, `comp` shall induce a strict weak ordering on the values." – Julius Aug 03 '19 at 11:34

0 Answers0