为什么这段代码会导致std::sort抛出分段错误？

Question

请问为什么下面的排序会导致段错误？这是 g++ 的已知 bug 吗（对指针向量进行排序）？我正在使用 g++ 4.5.2 进行编译。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef vector<int> A;
bool face_cmp(const A *x, const A *y) {
  return x != y;
}

int main(int argc, char* argv[]) {

  vector<A *> vec;
  for (int i=0; i<100; i++) {
    vec.push_back( new vector<int>(i%100, i*i) );
  }

  vector<A *>::iterator it;
  sort(vec.begin(), vec.end(), face_cmp);

  return EXIT_SUCCESS;
}

在codepad上编译的结果是：

/usr/local/lib/gcc/i686-pc-linux-gnu/4.1.2/../../../../include/c++/4.1.2/debug/safe_iterator.h:240:
    error: attempt to decrement a dereferenceable (start-of-sequence)     
    iterator.

Objects involved in the operation:
iterator "this" @ 0x0xbf4b0844 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPPN15__gnu_debug_def6vectorIiSaIiEEEN10__gnu_norm6vectorIS7_SaIS7_EEEEENS4_IS7_SB_EEEE (mutable iterator);
  state = dereferenceable (start-of-sequence);
  references sequence with type `N15__gnu_debug_def6vectorIPNS0_IiSaIiEEESaIS3_EEE' @ 0x0xbf4b0844
}

非常感谢大家的快速回复。原始的比较函数是：

if (x == y) return false;
if (x->size() < y->size()) return true;
else if (x->size() > y->size()) return false;
else {
  for (register int i=0; i<x->size(); i++) {
    if ((*x)[i] < (*y)[i]) return true;
  }
  return false;
}

我只更改了第一行并删除了其他内容。但是，它似乎也没有成为一个严格的弱序（我忘记了情况if (*x)[i] > (*y)[i]）。我可能应该一开始就发布整个函数。尽管如此，再次感谢！！

- Jack Cheng

---

你的比较函数有问题。它不是在比较值，而只是指针 - 最多也只能算是这样。 - Jonathan Leffler

你正在比较 vector<int> 的指针，比较必须在数据上进行。 - Arunmu

然后，完全删除比较函数。只需放置...或其他内容; 当它不是实际问题时，看到明显损坏的代码会分散注意力。 - Nicol Bolas

那么，实际的比较函数是什么？因为将其更改为合理的内容可以解决段错误。http://ideone.com/qaaOA - Benjamin Lindley

对于指针向量的排序没有问题；问题在于在比较函数中使用不等于而不是小于。 - zvrba

Answer 1

比较函数必须定义一个严格的弱序关系，这意味着a < b和b < a不能同时为真。您的比较函数没有这个属性。

它未定义任何“先后”关系，所以依赖此属性的算法无法正常工作。

- UncleBens

Answer 2

std::sort的第三个参数应该是一个函数（或可调用对象），这样如果compare(a, b)返回true，那么compare(b, a)应该返回false，但是您提供的函数不符合此要求。因此，您的程序行为未定义，可能会产生任何结果。

- Mihran Hovsepyan

---

都是正确的。但仍然没有真正回答问题。你需要解释比较运算符实际上需要定义的关系。 - Martin York

Answer 3

不，你的代码是错误的。std::sort 的比较函数必须使用 < 或其等效方式，使用 != 是不正确的。可能你想要这样

bool face_cmp(const A *x, const A *y) {
  return *x < *y;
}

- john

---

另外两个答案表述得更好，严格弱序是我真正想要说的 :) - john

当然可以使用 < 比较向量，可参考此处：http://www.cplusplus.com/reference/stl/vector/operators/。请取消您的反对票。我的答案可能不如其他人好，但并不是错误的。 - john

@ArunMu 是的，你可以这样比较向量。 - Benjamin Lindley

比较运算符不一定需要使用'<'，它同样可以使用'>'或其他许多比较方式。这是一个不够强有力的答案，因为您没有定义比较运算符必须定义的关系。 - Martin York

@Martin：是的，这正是我在第一条评论中提到的重点。然而我的回答包含了一些代码，因此对于楼主可能会有所帮助。 - john

Answer 4

请确保您只使用大于或小于符号。 不要使用等于符号。在某些数据集中，等于符号会导致SEGFAULT错误:

// Good
bool face_cmp(const A *x, const A *y) {
  return *x < *y;
}

// Also okay for reverse sorting
bool face_cmp(const A *x, const A *y) {
  return *x > *y;
}

// This will SEGFAULT
bool face_cmp(const A *x, const A *y) {
  return *x <= *y;
}

<=的真正危险在于缺乏可重复性。我有一些C++代码，在我的x86 PC上运行得很顺畅，但在Android上SEGFAULT'ed。对我来说，这个魔数是68个元素，67个是好的，68个导致SEGFAULT。

- Luke Dupin

Answer 5

将您的比较函数定义为

bool face_cmp(const A *x, const A *y) {
  return x < y;
}

- zvrba

---

你应该向楼主询问这个问题。 - zvrba

OP所展示的原始比较函数比较值（它只是优化了相同对象的比较...） - Matthieu M.