Сортировка объектов с дублирующимися ключами

Question

Мне нужен длинный список объектов, упорядоченных по одному из параметров. Каков самый быстрый способ сделать это на C++? Мне нужно иметь возможность добавлять и удалять элементы в этот список и по-прежнему сортироваться по этому конкретному параметру.

Class Foo { 
private: 
    int rank; 
} 

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

Любая идея, как я могу это сделать на C++? Я смотрел на make_heap(), но я не уверен, как использовать его (или если он может быть использован) с объектами.

Answer 1

Сначала вы, вероятно, следует определить operator< для Foo (что-то вроде этого) ...

inline bool operator< (const Foo& lhs, const Foo& rhs) { 
    return lhs.rank < rhs.rank; 
} 

, которые должны быть объявлены в качестве друга Foo-х:

class Foo { 
public: 
    explicit Foo(int rank_init) : rank(rank_init) {} 
    friend bool operator< (const Foo&, const Foo&); 
private: 
    int rank; 
}; 

Теперь вы можете создать std::multiset<Foo>, который сохранит Foo s отсортированный по возрастанию на rank, например

std::multiset<Foo> foo_multiset; 
foo_multiset.insert(Foo(5)); // 5 
foo_multiset.insert(Foo(3)); // 3, 5 
foo_multiset.insert(Foo(1)); // 1, 3, 5 
foo_multiset.insert(Foo(3)); // 1, 3, 3, 5 
size_t erased_count(foo_multiset.erase(Foo(3))); // 1, 5 (erased_count == 2) 

У нас нет гарантий, что это будет «самый быстрый» вариант в вашем конкретном случае. Вам нужно будет профилировать это. В зависимости от количества элементов, частоты операций вставки/стирания и реализации STL вы можете обнаружить, что отсортированный std::vector<Foo> лучше соответствует вашим потребностям.

Скотт Мейерс Effective STL описывает, как это может быть случай в пункте 23.