Why does std::sort throw a segmentation fault on this code?

Can someone explai开发者_开发问答n why the sort below causes seg faults? Is this a known bug with g++ (sorting vector of pointers)? I am compiling with 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;
}

Compiling on codepad gives:

/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
}

Thank you for the all the quick replies. The original comp function was:

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;
}

I just changed the first line and removed the rest. But it turns out it also suffers from not being a strict weak ordering (I forgot the case if (*x)[i] > (*y)[i]). I should probably have posted the entire function to begin with. Nevertheless, thanks again!!

---

The comparison function must define a strict weak ordering which means that a < b and b < a cannot be both true. Your comparison function does not have this property.

It does not define any "before-after" relationship, so it's no wonder that the algorithm relying on this property does not function properly.

---

Third argument of std::sort should be a function (or functional object) such that if compare(a, b) is true then compare(b, a) should be false, but your one isn't such. So your program is UB and can give any result.

---

No your code is wrong. Comparison functions for std::sort must use < or it's equivalent, using != is not correct. Probably you want this

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

---

Ensure that you're just using greater than or less than. DO NO USE equal to. Equal to will SEGFAULT with certain data sets:

// 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;
}

The real danger with <= is the lack of repeatability. I had some C++ code that SEGFAULT'ed on Android, while happily running on my x86 PC. For me, the magic number was 68 elements, 67 was fine, 68 SEGFAULT'ed.

---

Define your comparison function as

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