Why does std :: sort cause a segmentation error in this code?

Question

Can someone explain why the sorting below causes seg errors? Is this a known bug with g ++ (sorting a 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; } 

Compilation in codedex 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 } 

Thanks for all the quick answers. Original comp function:

 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 deleted the rest. But it turns out that he also suffers from not strict weak ordering (I forgot the case if (* x) [i]> (* y) [i]). I should probably write the whole function. However, thanks again!

Answer 1

The comparison function must determine a strict weak order, which means that a < b and b < a cannot be true. This comparison function does not have this property.

It does not define a pre-post relationship, so it is not surprising that an algorithm relying on this property does not work properly.

Answer 2

The third argument to std::sort should be a function (or a functional object) such that if compare(a, b) is true , then compare(b, a) must be false , but yours is not. Thus, your program is UB and can give any result.

Answer 3

There is no your code. The comparison functions for std :: sort should use <or this is equivalent using! = Is incorrect. You probably want this

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

Answer 4

Define the comparison function as

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