嵌套矢量/多映射/地图的使用是否好吗？

Question

我正在寻找以下方案的完美数据结构：

我有索引 i, ，对于每个人，我都需要支持以下 操作1: ：快速查找它的 Foo 对象（见下文），每个对象都与 double 价值。

所以我做到了：

struct Foo {
  int a, b, c;
};

typedef std::map<Foo, double> VecElem;
std::vector<VecElem> vec;

但事实证明这是低效的，因为我还必须为以下方面提供非常快速的支持 操作2: ： 移除所有 Foo具有一定价值的s a 和 b （以及关联的双重值）。

要执行此操作2，我必须迭代向量中的地图，检查 Foo为他们的 a 和 b 价值并从地图中逐一删除它们，这似乎非常昂贵。

因此，我现在正在考虑此数据结构：

struct Foo0 {
  int a, b;
};

typedef std::multimap<Foo0, std::map<int, double> > VecElem;
std::vector<VecElem> vec;

这应该为上述操作1和2提供快速的支持。那是合理的吗？嵌套容器结构上有很多开销吗？

注意：每个多示像通常只有一个或两个键（类型 Foo0），每个都有大约5-20个值（类型的值 std::map<int,double>).

Answer 1

要回答标题问题：是的，嵌套STL容器非常好。根据您的使用配置文件，这可能导致幕后过多复制。一个更好的选择可能是使用除顶级容器以外的所有内容使用 Boost::shared_ptr, ，因此容器家政服务不需要嵌套容器的整个内容的深层副本。如果您打算花费大量时间插入和删除，那将是这种情况。 VecElem 在高级 vector - 昂贵 VecElem 是直接的 multimap.

数据结构中的内存开销可能不会比您可以使用等效功能设计的任何内容都明显差，除非您计划花更多的时间在此上，否则更可能更好。

Answer 2

好吧，您从这个想法上有一个合理的开始...但是必须首先解决一些问题。

例如，是类型 Foo 可变？如果是，那么您需要谨慎创建类型 Foo0 （嗯...一个不同的名字可能是一个好主意，避免混乱），因为更改 Foo 可能无效 Foo0.

其次，您需要确定是否还需要此结构才能很好地用于插入/更新。如果人口 Foo 是静态和不变的 - 这不是问题，但是如果不是问题，您最终可能会花费很多时间维护 Vec 和 VecElem.

就嵌套STL容器的问题而言，这很好 - 通常用于创建任意复杂的结构。