这种嵌套向量/多重贴图/贴图的使用可以吗？
我正在为以下场景寻找完美的数据结构：
我有一个索引i，对于每个索引我需要支持以下操作1：快速查找其Foo 对象（见下文），每个对象都与一个 double 值关联。
所以我这样做了：
struct Foo {
int a, b, c;
};
typedef std::map<Foo, double> VecElem;
std::vector<VecElem> vec;
但事实证明效率很低，因为我还必须为以下操作2提供非常快速的支持：删除所有具有特定值的Foo对于 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）。
I am looking for the perfect data structure for the following scenario:
I have an index i, and for each one I need to support the following operation 1: Quickly look up its Foo objects (see below), each of which is associated with a double value.
So I did this:
struct Foo {
int a, b, c;
};
typedef std::map<Foo, double> VecElem;
std::vector<VecElem> vec;
But it turns out to be inefficient because I also have to provide very fast support for the following operation 2: Remove all Foos that have a certain value for a and b (together with the associated double values).
To perform this operation 2, I have to iterate over the maps in the vector, checking the Foos for their a and b values and erasing them one by one from the map, which seems to be very expensive.
So I am now considering this data structure instead:
struct Foo0 {
int a, b;
};
typedef std::multimap<Foo0, std::map<int, double> > VecElem;
std::vector<VecElem> vec;
This should provide fast support for both operations 1 and 2 above. Is that reasonable? Is there lots of overhead from the nested container structures?
Note: Each of the multimaps will usually only have one or two keys (of type Foo0), each of which will have about 5-20 values (of type std::map<int,double>).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
回答一下标题问题：是的，嵌套 STL 容器是完全没问题的。不过，根据您的使用情况，这可能会导致在幕后进行过多的复制。更好的选择可能是使用 Boost::shared_ptr 包装除顶级容器之外的所有内容，以便容器管理不需要嵌套容器的整个内容的深层副本。如果您计划花费大量时间在顶级
vector中插入和删除VecElem，情况就会如此 - 如果VecElem是一个直接多重映射。数据结构中的内存开销可能不会比您可以设计的具有同等功能的任何东西差很多，并且更有可能更好，除非您计划在这方面花费比正常情况更多的时间。
To answer the headline question: yes, nesting STL containers is perfectly fine. Depending on your usage profile, this could result in excessive copying behind the scenes though. A better option might be to wrap the contents of all but top-level container using
Boost::shared_ptr, so that container housekeeping does not require a deep copy of your nested container's entire contents. This would be the case say if you plan on spending a lot of time inserting and removingVecElemin the toplevelvector- expensive ifVecElemis a directmultimap.Memory overhead in the data structures is likely to be not significantly worse than anything you could design with equivalent functionality, and more likely better unless you plan to spend more time on this than is healthy.
好吧，你对这个想法有了一个合理的开始……但有一些问题必须首先解决。
例如，类型
Foo是可变的吗？如果是，那么您在创建类型Foo0时需要小心（嗯……使用不同的名称可能是一个好主意，以避免混淆），因为对Foo进行了更改> 可能会使Foo0无效。其次，您需要决定是否也需要此结构才能很好地进行插入/更新。如果
Foo的数量是静态且不变的 - 这不是问题，但如果不是，您最终可能会花费大量时间维护Vec和VecElem。就嵌套 STL 容器的问题而言，这很好 - 并且通常用于创建任意复杂的结构。
Well, you have a reasonable start on this idea ... but there are some questions that must be addressed first.
For instance, is the type
Foomutable? If it is, then you need to be careful about creating a typeFoo0(um ... a different name may be a good idea hear to avoid confusion) since changes toFoomay invalidateFoo0.Second, you need to decide whether you also need this structure to work well for inserts/updates. If the population of
Foois static and unchanging - this isn't an issue, but if it isn't, you may end up spending a lot of time maintainingVecandVecElem.As far as the question of nesting STL containers goes, this is fine - and is often used to create arbitrarily complex structures.