这是否使用嵌套的矢量/多图/地图好吗？ [英] Is this use of nested vector/multimap/map okay?

问题描述

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

I am looking for the perfect data structure for the following scenario:

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

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.

所以我这样做：

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

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

但结果是效率低下，因为我还必须为以下操作2 ：删除 a 和<$ c $具有一定值的所有 Foo c> b （连同相关联的double值）。

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).

执行此操作2，我必须遍历向量中的映射，检查 Foo s的 a 和 b 并从地图上逐一删除，这似乎是非常昂贵的。

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;

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

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?

注意：每个多点图通常只会有一个或两个键（类型为 Foo0 ），每个它将具有约5-20个值（类型为 std :: map< int，double> ）。

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>).

推荐答案

回答标题问题：是的，嵌套STL容器是完全正确的。根据您的使用情况，这可能会导致幕后过度复制。一个更好的选择可能是使用 Boost :: shared_ptr 包装所有顶级容器的内容，以便容器内部管理不需要您的嵌套容器的整个内容。如果您打算花费大量时间插入和删除向量中的 VecElem 如果 VecElem 是一个直接的 multimap 。

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 removing VecElem in the toplevel vector - expensive if VecElem is a direct multimap.

内存数据结构中的开销可能不会比您使用等效功能设计的任何内容要差得多，更有可能更好，除非您计划在健康状况下花费更多时间。

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.

这篇关于这是否使用嵌套的矢量/多图/地图好吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！