2

std::multiset の演算子のいずれかを何らかの形でオーバーロードして ('()' を使用してカスタム比較関数を作成するように)、マルチセット内の 2 つの要素が交換されたときに、別のベクトルの別の 2 つの要素がそれらにリンクされるようにすることはできますか?

つまり、実際にはマルチセットに要素 {a、b、c、d、e} を挿入したいのですが、.find() を使用せずに、マルチセット内の位置を追跡したいのです。そこで、別のベクトル pos を作成することを考えました。ここで、pos[k] は、マルチセット内の要素 k の位置です。

したがって、このベクトル pos がある場合でも、要素を挿入するときに multiset を作成する必要があります。これは、要素を multiset 内の適切な場所に配置するだけでなく、スワップされたすべての要素の pos[] を変更するためでもあります。

マルチセットが要素をどのように変更/スワップしてソートするのか正確にはわかりませんが、次の代わりにそれをオーバーライドできますか:

swap(a,b);

のようなものがあります。

swap(pos[a],pos[b]);
swap(a,b)

また、.find() (等しい要素に対して O(N) の複雑さを持つ) を使用せずに、マルチセット内の要素の位置を追跡する方法について他のアイデアがある場合は、素晴らしいでしょう!

編集

pos[n]また、新しい要素 (n) を挿入すると、「スワップ」が行われる前にの正しい初期化が行われるように、何かを変更する必要があると思います。

4

2 に答える 2

2

別の方法として、注文統計ツリーのデータ構造を調べることもできます。この構造には、すべてO（log n）時間で機能する次の機能があります。

  • 入れる
  • 消去
  • 後継者を探す
  • 前任者を探す
  • キーで検索
  • インデックスで検索
  • 要素のインデックスを教えてください（すでにイテレータがある場合は、O（1）で）

つまり、位置またはキーで要素をツリーに要求し、特定の要素がどの位置にあるかをツリーに通知させることができます。また、要素を（のようにstd::multiset）ソートされた順序で格納し、重複する要素を簡単に処理できるようにします。std::multisetつまり、インデックス作成を効率的にサポートするように使用できます。

残念ながら、順序統計ツリーはC ++標準ライブラリに含まれていませんが、これが最善のアプローチのようです。あなたは彼らのためにサードパーティのライブラリを見つける必要があるでしょう。

お役に立てれば！

于 2012-02-13T20:53:28.007 に答える
0

から継承せずにこれらをオーバーライドすることはできませんがmultiset、これはお勧めできません。したがって、必要なのは、 内の要素の位置を追跡するロジックmultisetです。

要素を に挿入すると、その要素へのmultiset反復子が取得されます。それを使用して、挿入した要素の前の要素を特定し、そこから新しい位置を特定できます。

std::multiset<your_item_type> it = your_set.insert(item);
std::size_t new_element_pos = it != your_set.begin() ? pos[*(it--)] + 1
                                                     : pos[*(it++)] - 1

重要な部分は、挿入した項目の後のすべての項目の位置を 1 ずつ増やして更新する必要があることです。

スワップを追跡するには、単純std::swapにタイプを特殊化できます。2 つの要素がスワップされると、位置ベクトル内の位置がスワップされます。

于 2012-02-13T20:44:53.397 に答える