std :: sort идет за борт

Question

Я пытаюсь отсортировать вектор объектов, используя функцию предиката, и получаю некоторые ошибки ...

У меня есть класс Item и список элементов в vector< Item > _items,Мне нужно было отсортировать его в соответствии с порядком отображения (числовой член класса), и я просто вызвал простую сортировку с функцией предиката.

sort(_items.begin(), _items.end(), sort_item_by_display_order);

, где функция предиката -

bool sort_item_by_display_order (Item i, Item j)
{
    return i.GetDisplayOrder()>j.GetDisplayOrder();
}

и GetDisplayOrder равен

int Item::GetDisplayOrder()
{
    return display_order;
}

, но ... при этом я получил некоторые ошибки.Затем я добавил счетчик в функцию предиката, чтобы проверить, сколько раз он вызывался, и обнаружил, что при сбое счетчик был больше, чем размер вектора.

После некоторого чтения я изменил код для использованияитераторы вместо использования .begin () и .end () (разве это не должно быть одинаково?!)

Итак, теперь у меня есть

vector<Item>::iterator it_start, it_end;
it_start = _items.begin();
it_end = _items.end();
sort(it_start, it_end, sort_item_by_display_order);

с тем же предикатомfunction.

И теперь он не падает, но ... для большей части сортировки я получаю больше итераций, чем размер вектора, который я сортирую (что, вероятно, нормально)

Итак ... В чем разница между сортировкой вызовов с _items.begin() или _it_start.Из того, что я могу сказать, они одинаковы, верно?!

Еще одна заметка.Item - это простой базовый класс, объявленный как

class Item
{
  private:
  (...)
  public:
  (...)
}

. В качестве ссылки я использовал http://www.cplusplus.com/reference/algorithm/sort/ и http://www.codeguru.com/forum/showthread.php?t=366064.

Во второй ссылке они добавляют const и & toаргументы предикатной функции, которые делают мою функцию примерно такой:

bool sort_item_by_display_order (const Item& i, const Item& j)
{
    return i.GetDisplayOrder()>j.GetDisplayOrder();
}

, но я получаю ошибку компилятора:

Item.cpp|1485|error: passing `const Item' as `this' argument of `int Item::GetDisplayOrder()' discards qualifiers|

arghhh ... Вопрос в том ... Что яделаешь неправильно?

Answer 1

Во-первых, совершенно нормально, что функция сравнения вызывается чаще, чем у вас есть элементы в коллекции.Это часть того, что подразумевается, когда мы говорим, например, что сложность алгоритма сортировки - это O ( n log n ).Количество сравнений, выполненных для коллекции размером n , составит около n × log ( n ).(На самом деле, n - это в значительной степени минимум количество раз, чтобы вызвать его; в противном случае, мы даже не смогли бы определить, была ли коллекция отсортирована в первую очередь..)

Во-вторых, вы получаете ошибку, когда делаете параметры константными ссылками, потому что вы объявили GetDisplayOrder как неконстантный метод.Вы не можете вызывать неконстантные функции-члены для константного объекта, потому что компилятор предполагает, что метод попытается изменить объект, даже если в этом случае он ничего не изменяет.Добавьте const в конец объявления и определения:

int GetDisplayOrder() const;

int Item::GetDisplayOrder() const {
  return display_order;
}

Наконец, есть проблема ошибок сегментации.Код, который вы здесь показали, недостаточен для точного определения причины.Вы правы, что изменение способа передачи итераторов на sort не должно иметь никакого эффекта.Я подозреваю, что вашему классу Item нужен конструктор копирования и оператор присваивания, но они либо не реализованы, либо не реализованы должным образом.Сортировка вектора, очевидно, включает перемещение элементов в коллекции, для чего требуется оператор рабочего присваивания.Для передачи этих элементов в исходную функцию сравнения, которая принимает параметры по значению, а не по константной ссылке, требуется конструктор рабочей копии.Если вы выполняете какое-либо динамическое выделение памяти (например, с помощью new или malloc), вам необходимо убедиться, что вы делаете «глубокую копию» памяти при назначении или копировании объекта, или вы выясняетеспособ для нескольких объектов совместно использовать одного и того же распределения.Если несколько объектов считают, что все они владеют одним и тем же блоком памяти, один из них, вероятно, освободит эту память до того, как другие закончат с ней, и это, безусловно, может привести к ошибкам сегментации (когда вы обращаетесь к освобожденной памяти).

Answer 2

В дополнение к тому, что сказал Роб Кеннеди, попробуйте поставить точку останова в std::swap (std::sort фактически меняет элементы, чтобы перемещать их). Вы даже можете реализовать свой собственный swap и сделать небольшую «отладку printf», если не можете использовать отладчик по какой-либо причине.

Когда вы достигнете точки останова, внимательно наблюдайте, правильно ли копируются объекты, и убедитесь, что ничего не повреждено. Идея состоит в том, чтобы попытаться найти точное место повреждения, которое может не обязательно сразу привести к сбою программы, но позже приведет к плохим последствиям.