CODEWITHSUNDEEP
c++sortingsegmentation-fault
Jack Cheng
Jack Cheng

Reputation: 409

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

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!!

Upvotes: 11

Views: 9522

Answers (5)

Luke Dupin
Luke Dupin

Reputation: 2305

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.

Upvotes: 3

zvrba
zvrba

Reputation: 24546

Define your comparison function as

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

Upvotes: 1

john
john

Reputation: 87944

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

Upvotes: 10

UncleBens
UncleBens

Reputation: 41333

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.

Upvotes: 26

Mihran Hovsepyan
Mihran Hovsepyan

Reputation: 11088

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.

Upvotes: 12

Related Questions