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

Question

Can someone explain 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!!

Answer 1

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.

Answer 2

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.

Answer 3

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