今天遇到的一个诡异的core和解决 std::sort

其实昨天开发pds，就碰到了core，我还以为是内存不够的问题，或者其他问题。

今天把所有代码挪到了as这里，没想到又出core了。

根据直觉，我就觉得可能是std::sort这边的问题。

上网一搜，果然很多提到了这个问题。

原来 std::sort调用的方法，在相同元素这里，不能够返回true.

因为

std::sort()的排序分2种，当元素个数>16(_S_threshold)时选择快速排序，<=16个则选择插入排序(对象少时快排性能不理想)。按照快排原理，每次都是遍历所有值和一个中间值比较，小的放左边，大的放右边。从下面STL源代码可看出，std::sort()在遍历比较时，是没有边界保护的。如果比较相等的元素返回真，则在极端情况下(如所有元素相等，__pivot为最小|最大值时)会出现访问越界，导致coredump

/// This is a helper function...

  template<typename _RandomAccessIterator, typename _Tp, typename _Compare>

    _RandomAccessIterator

    __unguarded_partition(_RandomAccessIterator __first,

              _RandomAccessIterator __last,

              _Tp __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;

    }

    }

参考：

http://blog.csdn.net/yyyiran/article/details/38797237

http://blog.csdn.net/stpeace/article/details/52202341

函数中使用的是

while (__comp(*__first, __pivot))

    ++__first;

如果当比较元素相同返回真时，此时比较元素将会继续向下遍历，在极端情况下，例如程序中所有元素都是一样的情况下，在这种情况下，就会出现访问越界，结果就是导致程序出现segment fault

巴特西

今天遇到的一个诡异的core和解决 std::sort

最新文章

热门文章