3

stlまたは一般に、一種の「逆」連想コンテナが存在しますか? たとえば、同じ要素が一連のキーによって共有されるコンテナが必要です。

私のキーが であるとしましょう。たとえば、次のintようになります。

container.at(3) -> some object A
container.at(4) -> same object A
container.at(1) -> other object B

このコンテナーは (理想的には) さまざまな操作の std::map と同じ複雑さを持ちます。そのようなことは可能ですか？

最初は複数のインデックスが同じオブジェクトを指している a を使用することを考えていましたstd::map<int, T*>が、マップからアイテムを削除すると、実行時間が O(n) になります。これは、他のアイテムをチェックして、 Tを削除する必要がありますobject

stlまたはboostに「ネイティブに」この種のコンテナがすでにありますか？

編集：使用例：

container<int, myClass> myContainer;
myClass obj(...); //new object
myContainer.insert(3, obj); //insert object for specific key
myContainer.insert(2, obj); //insert same object for specific key, since both objects would compare equal we would actually not "insert" a new object but have it shared by both keys
myContainer.duplicate_object(2,5); //key 5 also has the same object as key 2 (and 3)
myContainer.getAllKeys(2); //would return 2,3 and 5 since they all reference the same object as key 2
myContainer.removeKey(3);
myContainer.removeKey(2);
myContainer.removeKey(5); //would destroy the object here, not before
4

3 に答える 3

6

あなたは使用することができます

std::map<int,std::shared_ptr<myclass>>

標準の一部であるC++ 11では。それ以外の場合は、Boost ライブラリによって提供される共有ポインターを使用します。

共有ポインタの考え方は、参照カウントを内部的に保持することです。つまり、ポインタのコピーが作成された回数を追跡します。マップのエントリを削除すると、共有ポインタ オブジェクトのデストラクタによって、カウンタが減分されます。ゼロになると、オブジェクトは削除されます。

（編集:)答えをより完全にするために、いくつかの使用例：

#include <map>
#include <memory>

struct myclass
{

};


int main()
{
  std::map<int,std::shared_ptr<myclass>> mymap;

  /* std::make_shared() calls the constructor and creates a shared_ptr: */
  std::shared_ptr<myclass> object1 { std::make_shared<myclass>() };
  std::shared_ptr<myclass> object2 { std::make_shared<myclass>() };
  std::shared_ptr<myclass> object3 { std::make_shared<myclass>() };

  mymap[1] = object1;
  mymap[2] = object2;
  mymap[3] = object3;
  mymap[4] = object2;
  mymap[5] = object1;

  mymap.erase(2); // erases the (2,object2) entry
                  // therefore, decreases the counter
                  // for object2
                  // but (4,object2) is still intact

  return 0;
}
于 2012-09-19T00:46:59.670 に答える
0

Boost.MultiIndexを見たいと思うかもしれません。説明には次のように書かれています。

Boost Multi-index Containers Library は、multi_index_container という名前のクラス テンプレートを提供します。これにより、異なる並べ替えとアクセス セマンティクスを持つ 1 つ以上のインデックスを維持するコンテナーの構築が可能になります。

于 2012-09-19T14:21:36.180 に答える
-1

したがって、必要なのは std::map のような高速な挿入とルックアップの両方だけでなく、値によってエントリをすばやく削除する機能でもあります。

それを行う標準コンテナはありません。しかし、自分で書きたい場合は、2 つの内部データ構造を維持することでこれを行うことができます。

  1. キーを値にマップするstd::map
  2. 値をそれらを指すキーのセットにマップする 2 番目のstd::multimap

キーを値で削除する場合は、2 番目のマップで検索できます。

于 2012-09-19T00:47:59.467 に答える