c++ - "inverse"关联容器？

Question

在 STL 中或一般情况下是否存在一种“反向”关联容器？ 例如，我想要一个容器，其中同一元素由一组键共享。

假设我的 key 是 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*>其中几个索引指向同一个对象，但是当从 map 中删除一个项目时，运行时间在 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

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