Сохраняет ли qStableSort порядок эквивалентных элементов?

Question

Предположим, у меня есть QList из 100 MyItem объектов, вставленных в определенном порядке. У каждого MyItem есть связанный timestamp и некоторая собственность p, которая не гарантируется быть уникальной.

struct MyItem { 
    enum MyProperty { ONE, TWO, THREE }; 

    double timestamp; //unique 
    MyProperty p;  //non-unique 

    bool operator<(const MyItem& other) const { 
     return p < other.p; 
    } 
}; 

Предположив Я добавил мои 100 объектов в хронологическом порядке, если бы я был бежать qStableSort на этом контейнере (таким образом, сортировка по p), у меня есть гарантия, что при заданном значении p, что они все еще находятся в хронологический порядок?

Answer 1

https://en.wikipedia.org/wiki/Category:Stable_sorts

устойчивых алгоритмов сортировки поддерживать относительный порядок записей с одинаковыми ключами (т.е. значений). То есть алгоритм сортировки является стабильным, если всякий раз, когда есть две записи R и S с одним и тем же ключом и с R, появляющимся перед S в исходном списке, R появится перед S в отсортированном списке.

Поэтому ключевое слово в qStableSortстабильной точно ссылаясь на то, что вы просите.

Однако обратите внимание, что qStableSort вместо этого obsoleted in Qt 5.5

Использование станд :: stable_sort.

Сортирует элементы в диапазоне [начало, конец] в порядке возрастания, используя стабильный алгоритм сортировки.

Если ни один из двух элементов не «меньше» другого, элементы считаются равными. Элемент, который появился перед другим в исходном контейнере, по-прежнему будет отображаться первым после сортировки. Это свойство часто полезно при сортировке видимых пользователем данных.

Согласно документации Qt, вы должны предпочесть использовать std::stable_sort