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) 中，因为您必须检查其他项目以查看您是否需要删除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
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 的类模板，它支持构建容器来维护一个或多个具有不同排序和访问语义的索引。

于 2012-09-19T14:21:36.180 回答
-1

因此，您想要的是像 std::map 中那样快速插入和查找，而且还需要按值快速删除条目的能力。

没有标准的容器可以做到这一点。但是当你想自己写一个时，你可以通过维护两个内部数据结构来做到这一点：

  1. 将键映射到值的std::map
  2. 第二个std::multimap将值映射到指向它们的键集

当您想按值删除键时，您可以在第二张地图中查找它。

于 2012-09-19T00:47:59.467 回答