重複キーを使用してオブジェクトを並べ替える

Question

パラメータの1つで順序付けられたオブジェクトの長いリストが必要です。 C++でこれを行う最速の方法は何ですか？私は、このリストに要素を追加したり削除したりして、その特定のパラメータでソートする必要があります。

Class Foo { 
private: 
    int rank; 
} 

私は新しいものが追加されたり、それがために適切な場所を取る必要があります削除されたときにすべての私のFooオブジェクトが昇順とに記載されていることにしたいです。同じrankを持つ複数のオブジェクトが存在する可能性があるため、キー値は使用できません。

私はこれをC++でどのように行うことができますか？私はmake_heap()を見ていましたが、オブジェクトを使用する方法（または使用できるかどうか）はわかりません。

Answer 1

まずあなたはおそらく... Foo（このようなもの）のために

Foo年代のフレンドとして宣言する必要があります

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

operator<を定義する必要があります。

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

を今度は、Fooを昇順でソートしたstd::multiset<Foo>を作成することができます。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.