動的属性に基づいてソートされたアイテムを保持する方法は？

Question

私は、STL std :: multiset <をポインタのソートされたリストとして使用しています。アイテムのプロパティによって決定されたソート順を指されて、この簡単な例の線に沿って何か：

struct A 
{ 
    int x; 
}; 

bool CompareAPointers(const A* lhs, const A* rhs) 
{ return lhs->x < rhs->x; } 

std::multiset<A*, CompareAPointers> sorted_set; 

合併症セットをソートするために使用されるプロパティの値は、（あなたができる変更できるということですソート順序が間違って作ることができ、上記の例では、変更アックス）、：

A a1, a2; 
a1.x = 1; 
a2.x = 2; 
sorted_set.insert(&a1); 
sorted_set.insert(&a2); 
a1.x = 3; 

私は関連がある場合、属性の変更要素を消去し、再挿入順にソートされたリストを維持することができんだけど、簿記がになっています痛みが少しあります。私はこれについてすべて間違っているように感じる。並べ替え順序を動的に変更できるときにソートされたリストを保持するためのよりよい方法を提案する人はいますか？変更は予測可能な時期に予測可能な方法で行われますが、私の現在のアプローチはただで、が間違っていると感じています。

Answer 1

Boost Multi-Indexは、リストのフィールドの変更をサポートしていますが、a1.x=1はもう入力できませんが、MultiIndex::replace()を使用する必要があります。
要素の削除と再挿入はとにかくやっていなければならないので、もっと速く/より自然なやり方で考えることはできません。他の人が使用して、指摘

Answer 2

私の代わりにソートstd::vectorを使用して検討します。セットのメンバーの1つに対してxを予測的に変更するポイントの1つで、ベクトルを再ソートするだけです。アイテムを削除して再挿入する必要があるより少しきれいです。ただし、単一のメンバーのプロパティを頻繁に変更して再ソートする場合は、オーバーヘッドが大きくなる可能性があります。これらのプロパティの多くを一度に変更する可能性が高い場合は、はるかに便利です。

Answer 3

としてのstd ::設定またはSTD ::多重集合ちょうどそれをカットしていません。

あなたは、ポインタを使用するので、あなたはおそらく気づかなかったが、仮定は、オブジェクト（この場合には、それは先の尖った値をポインタがconstのあることを意味するが、していないが）不変であるということです。

したがって、あなたは（直接）自動的に簿記を行います標準コンテナを使用することはできません。この時点で

あなたはいくつかのソリューションがあります：あなたはライブラリを使用すること

• を、この場合にはBoost.MultiIndexは、あなたがそれ
• かを使用することを学ぶ必要がありますにもかかわらず、頭に浮かぶ専用のクラス（たとえば、あなたのセット）に標準のコンテナをラップすることがあります

私は両方とも同様に有効だと思います。操作は非常に簡単なので、Boostライブラリをまだ使用したくないかもしれません（学習曲線、統合、...）。

また、あなたは「侵襲のコンテナを使用して検討することができます。つまり、オブジェクトが値を変更するたびにそのコンテナにコンテナに通知して、コンテナが '新しい'正しい位置（std :: multisetを内部的に使用して）に再配置するようにすることができます。 。

効率が懸念される場合は、私はベクトルをソート考えていません。 1つのオブジェクトを変更するたびに完全なコンテナをソートすることは無駄ですが、消去/挿入メソッドの方がはるかに効率的です。