STL——std::sort（一次值得记录的排障）

今天在使用std::sort的时候遇到了一个非常奇妙的溢出异常，先给大家看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    int x;
    int y;
};
node in[1005];
bool comp(const struct node a, const struct node b)
{
    return a.x * a.y <= b.x * b.y;
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> in[i].x >> in[i].y;
    }
    sort(in, in + n, comp);
    for (int i = 0; i < n; i++)
    {
        cout << in[i].x << in[i].y;
    }
    return 0;
}

看上去是不是一个非常朴素且简单的排序？

请使用这样一组数据

100
1 1
2 1
2 2
1 2
1 2
2 2
1 2
1 2
2 2
2 2
1 2
2 1
1 2
1 2
1 2
1 2
2 2
1 2
1 1
1 1
1 1
1 1
1 2
1 2
1 1
1 1
1 2
1 2
2 2
1 1
1 2
1 1
1 2
2 2
1 2
1 2
2 2
2 2
1 2
1 2
2 1
1 2
1 1
1 2
1 1
2 1
2 2
1 1
2 2
1 1
2 2
1 2
2 2
1 2
2 2
1 2
1 2
2 2
1 2
2 2
1 2
1 2
1 1
2 1
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 1
2 2
1 2
2 1
2 2
1 2
1 1
1 2
1 1
1 2
1 2
2 2
1 2
1 1
1 1
2 2
1 2
2 2
2 1
1 2
2 1
1 2
1 2
2 2
1 2
1 2
1 2
1 1
1 2

你会奇妙的发现他栈溢出了。

但是类似的，如果你将这个数据放到到1e5或者缩小到40,50，又没有问题了。

反复查阅相关资料我发现是在std::sort的插入排序部分出现了栈异常

  /// This is a helper function for the sort routine.
  template<typename _RandomAccessIterator, typename _Compare>
    void
    __unguarded_linear_insert(_RandomAccessIterator __last,
			      _Compare __comp)
    {
      typename iterator_traits<_RandomAccessIterator>::value_type
	__val = _GLIBCXX_MOVE(*__last);
      _RandomAccessIterator __next = __last;
      --__next;
      while (__comp(__val, __next))
	{
	  *__last = _GLIBCXX_MOVE(*__next);
	  __last = __next;
	  --__next;
	}
      *__last = _GLIBCXX_MOVE(__val);
    }

错误出在这一段stl对插入排序实现上，在交换时出现了栈溢出，反复查阅资料，了解这一部分的代码实质是一个非约束性的插入排序，通常插入排序我们需要将两个元素比较两次，即a?b与b?a，而这里是非约束性的，也就是说其实只判断一次。

而我们错误的原因正是因为comp函数的不规范书写。

事实上，这一点非常隐蔽也非常容易被忽视。

std::sort的本质是快排，选排，堆排，三者共同作用实现的Introspective Sorting(内省式排序)。

关键就是stl对用户的comp函数有明确的要求

在文档当中，我们查阅到comp(a,b)必须满足Strict Weak Ordering(严格弱序关系)

即满足严格的反自反性，非对称性与可传递性

对于所有 a，comp(a,a)==false

若 comp(a,b)==true 则 comp(b,a)==false

若 comp(a,b)==true 且 comp(b,c)==true 则 comp(a,c)==true

以上缺一不可，显然我们反例当中的comp函数并不具有反自反性。

事实上这一点容易被忽略，尤其是在结构体等复杂对象的排序当中，保证严格的偏序关系是std::sort高效与安全的前提