c++ sort 函数comparator的注意事项

c++ sort 函数comparator的注意事项

1. comparator 的签名必须为

 bool cmp(const Type1 &a, const Type2 &b)

2. 对于相等的值永远返回 false

对于第二点可能有些难以理解，下面将进行详细解释
c++ sort 的实现非常厉害， 里面包括了插入排序， 堆排序，快排等等各种排序。

在快速排序的时候piovt 使用的是三数取中的方式
在__unguarded_partition函数，如果相等值返回 true的话， 那么这个函数可能会出现越界情况

  template
    void
    __introsort_loop(_RandomAccessIterator __first,
             _RandomAccessIterator __last,
             _Size __depth_limit)
    {
      typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

      while (__last - __first > int(_S_threshold))
    {
      if (__depth_limit == 0)
        {
          std::partial_sort(__first, __last, __last);
          return;
        }
      --__depth_limit;
      _RandomAccessIterator __cut =
        std::__unguarded_partition(__first, __last,
    
    // 三数取中                   _ValueType(std::__median(*__first,
                                *(__first
                                  + (__last
                                     - __first)
                                  / 2),
                                *(__last
                                  - 1))));
      std::__introsort_loop(__cut, __last, __depth_limit);
      __last = __cut;
    }
    }


  template
    _RandomAccessIterator
    __unguarded_partition(_RandomAccessIterator __first,
              _RandomAccessIterator __last, _Tp __pivot)
    {
      while (true)
    {
    // 如果 first 到 pivot 一直相等
    // 那么 会存在first越界的问题
      while (*__first < __pivot)
        ++__first;
      --__last;
      while (__pivot < *__last)
        --__last;
      if (!(__first < __last))
        return __first;
      std::iter_swap(__first, __last);
      ++__first;
    }
    }