How does std::sort work with duplicated numbers?

Question

When I was testing the std::sort function to deal with a vector filled with duplicated numbers, I found something really bewildering.

For example, here is a piece of c++ code.

#include <ctime>
#define startTime std::clock_t stTime = clock()
#define endTime std::clock_t edTime = clock()
#define processTime static_cast<double>(edTime - stTime) / CLOCKS_PER_SEC
#include <bits/stdc++.h>
using namespace std;
int main() {
    int i = 0;
    vector<int> v;
    while (i != 1000000) {
        v.push_back(2);
        ++i;
    }
    startTime;
    sort(begin(v), end(v), [](const int& lhs, const int& rhs) { return lhs <= rhs; });
    endTime;
    cout << processTime;
    system("pause");
}

When I didn't transmit the lambda expression including <= to the std::sort, everyting went well. However, various exceptions uccured when I actually did it. In this case, Segmentation Error occured. Sometimes the compiler failed to delete the elements in vector.

After throughly examination, I found something may happen in the STL files:

//stl_algo.h
  /// This is a helper function...
  template<typename _RandomAccessIterator, typename _Compare>
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
              _RandomAccessIterator __last,
              _RandomAccessIterator __pivot, _Compare __comp)
    {
      while (true)
    {
      while (__comp(__first, __pivot))
        ++__first;
      --__last;
      while (__comp(__pivot, __last))
        --__last;
      if (!(__first < __last))
        return __first;
      std::iter_swap(__first, __last);
      ++__first;
    }
    }

Where __pivot is __first+1 .

While comparing __first and __pivot , the statement is alway true, so we don't know where __first goes to.

Who can explain how does std::sort work in these cases?

score 1 · Answer 1 · answered Jan 16 '20 at 02:14

You have created an invalid comparator function with your lambda, should have used < instead of <=, otherwise sort() keeps swapping equal elements.

According to the reference for sort a comparator must:

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.

How does std::sort work with duplicated numbers?

1 Answers1