43

STLにソートされたコンテナはありますか？

私が意味するのは次のとおりです。私はstd::vector<Foo>、Fooカスタムメイドのクラスを持っています。クラスのフィールドを比較するある種のコンパレータもありますFoo。

今、私のコードのどこかで私はやっています：

std::sort( myvec.begin(), myvec.end(), comparator );

これは、コンパレータで定義したルールに従ってベクトルをソートします。

次に、クラスの要素をFooそのベクトルに挿入します。できれば、次のように書きたいと思います。

 mysortedvector.push_back( Foo() );

そして何が起こるかというと、ベクトルはコンパレータに従ってこの新しい要素をその場所に配置します。

代わりに、今私は書く必要があります：

myvec.push_back( Foo() );
std::sort( myvec.begin(), myvec.end(), comparator );

ベクトルはすでにソートされており、必要なのは新しい要素を適切に配置することだけなので、これは時間の無駄です。

現在、私のプログラムの性質上std::map<>、キーと値のペアがなく、単純なベクトルであるため、使用できません。

を使用する場合はstl::list、挿入するたびに再度sortを呼び出す必要があります。

4

3 に答える 3

72

はい、std::set、std::multiset、std::map、およびstd::multimapはすべてstd::less、デフォルトの比較操作として使用してソートされます。使用される基礎となるデータ構造は、通常、赤黒木などのバランスのとれた二分探索木です。したがって、これらのデータ構造に要素を追加してから、含まれている要素を反復すると、出力は並べ替えられた順序になります。データ構造に N 要素を追加する複雑さは O(N log N) になります。または、一般的な O(log N) 複雑さの並べ替えを使用して N 要素のベクトルを並べ替えるのと同じです。

特定のシナリオでは、キーと値のペアがないstd::setかstd::multiset、おそらく最善の策です。

于 2013-03-23T01:51:57.130 に答える