C ++: std :: sort с использованием уже уничтоженного объекта с пользовательским предикатом?

Question

У меня очень странная проблема с кодом, использующим std :: sort. Если я заменю std :: sort на stable_sort, проблема исчезнет.

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

Идея состоит в том, что я сортирую данные сначала по дате и времени, а затем по размеру. Однако, в зависимости от данных в векторе, я получу 0xfffffffe в размере, напечатанном в конце для первого объекта, что указывает на доступ к разрушенному объекту или на ошибку сегмента во время сортировки.

(Xcode 3.2.4 - 64-битная цель Intel)

Есть идеи кто-нибудь ?? Я подозреваю, что это как-то связано с моим предикатом, но я не могу понять, что это такое .... !! Эта страница, кажется, относится к той же проблеме:

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

но причина, которую он приводит (что предикат должен определять строгое слабое упорядочение), здесь, похоже, удовлетворяется ...

Answer 1

Ваш предикат не удовлетворяет строгим критериям слабого порядка. Посмотрите на свою функцию и спросите себя, что произойдет, если дата e1 наступит после e2, но время e1 наступит до e2?

Answer 2

Я думаю, что на самом деле ваш предикат должен выглядеть примерно так:

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

То, что вы написали - если e1._date>e2._date, первое условие будет ложным, но второе все еще может быть истинным, аФункция по-прежнему будет утверждать, что e1<e2, что, вероятно, не то, что вы хотите.

Answer 3

Ваш код должен быть:

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

Если дата e2 указана после e1, то ваши версии обрабатываются для сравнения времени и размера.Это не то, что вы хотите.Это в конечном итоге приводит к путанице в std :: sort, потому что если вы поменяете местами e1 и e2, вы не получите последовательного ответа.