C++: std::sort using already destroyed object with custom predicate?

Question

I'm having a very odd problem with some code using std::sort. If I replace std::sort by stable_sort the problem goes away.

class Entry
{
public:
    Entry() : _date(0), _time(0), _size(0) {}
    Entry(unsigned int d, unsigned int t, unsigned int s) : _date(d), _time(t), _size(s) {}
    ~Entry() {_size=0xfffffffe;}

    unsigned int _date, _time, _size;

};

void initialise(std::vector<Entry> &vec)
    vec.push_back(Entry(0x3f92, 0x9326, 0x1ae));
    vec.push_back(Entry(0x3f92, 0x9326, 0x8a54));
   //....  + a large number of other entries
}

static bool predicate(const Entry &e1, const Entry &e2)
{
    // Sort by date and time, then size
    if (e1._date < e2._date )
        return true;
    if (e1._time < e2._time )
        return true;

    return e1._size < e2._size;
}

int main (int argc, char * const argv[]) {
    using namespace std;
    vector<Entry> vec;
    initialise(vec);
    sort(vec.begin(), vec.end(), predicate);

    vector<Entry>::iterator iter;
    for (iter=vec.begin(); iter!=vec.end(); ++iter)
        cout << iter->_date << ", " << iter->_time <<
                  ", 0x" << hex << iter->_size << endl;

    return 0;
}

The idea is that I sort the data first by date and time then by size. However, depending on the data in the vector, I will end up with 0xfffffffe in the size printed out at the end for the first object, indicating that a destroyed object has been accessed, or a seg fault during the sort.

(Xcode 3.2.4 - 64 bit intel target)

Any ideas anyone?? I suspect it has something to do with my predicate, but I can't see for the life of me what it is....!! This page seems to refer to the same problem:

http://schneide.wordpress.com/2010/11/01/bug-hunting-fun-with-stdsort/

but the reason he gives (that the predicate needs to define a strict weak ordering) seems to be satisfied here...

score 3 · Answer 1 · answered Mar 15 '11 at 16:23

3

Your predicate does not satisfy strict weak ordering criteria. Look at your function and ask yourself, what happens if e1's date comes after e2, but e1's time comes before e2?

answered Mar 15 '11 at 16:23

Benjamin Lindley

101,917
9
204
274

An important point to note with this answer is that the requirement that the predicate satisfy strict weak ordering prevents the algorithm from running properly. The inexplicable behavior you are seeing might result from an improperly-defined predicate. – fbrereto Mar 15 '11 at 16:30
+1 writing strict weak ordering with multiple items to compare can be hard. One trick I've seen is to bind your attributes into a `boost::tuple` and letting it do the comparison for you. – Mark B Mar 15 '11 at 16:30
I asked a question about the best way to implement these a while ago; you might find it useful: http://stackoverflow.com/questions/1892379/preferred-implementation-of-for-multi-variable-structures – fbrereto Mar 15 '11 at 20:23

score 2 · Answer 2 · answered Mar 15 '11 at 16:29

I think what your predicate really should be is something like this:

static bool predicate(const Entry &e1, const Entry &e2)
{
    // Sort by date and time, then size
    return e1._date < e2._date || 
      (e1._date == e2._date && 
        (e1._time < e2._time || 
          (e1._time == e2._time && e1._size < e2._size)));
}

What you wrote - if e1._date>e2._date, the first condition will be false, but the second may still be true and the function will still claim that e1<e2 which is probably not what you want.

Thanks for your answers!! Just got back and realised myself what the problem was... :) — janusz, Mar 15 '11 at 18:54

score 1 · Answer 3 · answered Mar 15 '11 at 16:31

1

Your code needs to be:

static bool predicate(const Entry &e1, const Entry &e2)
{
    // Sort by date and time, then size
    if (e1._date != e2._date )
        return e1._data < e2._date;
    if (e1._time != e2._time )
        return e1._time < e2._time;
    return e1._size < e2._size;
}

If e2's date is after e1, then your version treats goes on to compare the time and size. This is not what you want. This eventually confuses std::sort because if you swap e1 and e2 you will not get a consistent answer.

answered Mar 15 '11 at 16:31

Winston Ewert

44,070
10
68
83

What does one do if (in this example) if date, time and size are all equal, this would cause a corruption no matter what you return – deek0146 Mar 15 '11 at 16:39
@Alasdair It would return `false` in that case, which is correct. – Mark B Mar 15 '11 at 16:41

C++: std::sort using already destroyed object with custom predicate?

3 Answers3