1

我正在为以下场景寻找完美的数据结构：

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

所以我这样做了：

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

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

但事实证明它效率低下，因为我还必须为以下操作 2提供非常快速的支持：删除所有对andFoo具有特定值的 s （以及相关联的 double 值）。ab

要执行此操作 2，我必须遍历向量中的映射，检查Foos 的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>）。

4

2 回答 2

2

回答标题问题：是的，嵌套 STL 容器非常好。但是，根据您的使用情况，这可能会导致在幕后进行过多的复制。更好的选择可能是使用 包装除顶级容器之外的所有内容Boost::shared_ptr，以便容器内务管理不需要嵌套容器的全部内容的深层副本。如果您计划花费大量时间VecElem在顶层插入和删除，就会出现这种情况vector- 如果VecElem是直接的，则成本很高multimap。

数据结构中的内存开销可能不会比你可以设计的任何具有同等功能的东西更糟糕，而且更有可能更好，除非你计划在这方面花费更多的时间而不是健康。

于 2010-09-22T16:35:46.017 回答
1

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

例如，类型是Foo可变的吗？如果是，那么您在创建类型时需要小心Foo0（嗯......不同的名称可能是避免混淆的好主意），因为更改Foo可能会使Foo0.

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

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

于 2010-09-22T16:36:00.590 回答