"逆"关联容器？

Question

在stl或一般情况下是否存在一种"逆"关联容器？例如,我想要一个容器,其中相同的元素由一组键共享.

假设我的密钥是一个int,那么我会举例说:

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

对于不同的操作,此容器(理想情况下)具有与std :: map相同的复杂性.这样的事情可能吗？

我在考虑首先使用std::map<int, T*>几个索引指向同一个对象的位置,但是当从地图中删除一个项目时,运行时间在O(n)中,因为你必须检查其他项目以查看是否你需要删除Tobject

在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

Answer 1

你可以用一个

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;
}