2

我经常需要表示从整数0...N-1到某种类型的列表的映射T。对于各个列表，我需要在末尾动态添加元素。N通常是事先知道的（但不是在编译时）。我需要快速访问各个列表。

我通常使用 来实现它vector<vector<T> > my_map(N)，并且我使用它my_map[key].push_back(val)来添加元素。

我有两个问题：

这是实现此类地图的有效且推荐的方法吗？

另外，我想知道元素的连续性及其对调整大小的影响。说，我添加了一个元素my_map[key].push_back(val)，并且my_map[key]需要key != N-1调整大小。这是否会触发整个向量的副本my_map以保持其内容连续？或者是在my_map内部用指向堆上的向量的指针实现的？

我知道这可能取决于 STL 的实现。我主要对 Visual Studio 2010 和 Linux 中的 GCC 的机制（和速度影响）感兴趣。

更新

在评论中，@PeterWood 指向我std::deque作为列表的容器，它不需要重新分配来增长。我做了一些不科学的基准测试来vector< deque<T> >与asvector< vector<T> >进行比较。对于这两种情况，我分别为 100 万个包含 30 个元素的列表和 10,000 个包含 3000 个元素的列表计时。请注意，我的测试反映了我对此类数据结构的典型应用场景。unsigned intT

我定时了一个随机访问“建立”，它的工作原理如下：

vector<ContainerT> my_map(numKeys);
vector<unsigned int> random_keys(numKeys);
for (unsigned int i=0; i<numKeys; ++i) random_keys[i] = i;
random_shuffle(random_keys.begin(),random_keys.end());

for (auto pKey=random_keys.begin(); pKey!=random_keys.end(); ++pKey)
{
  for (unsigned int i=0; i<listSize; ++i)
  {
    my_map[*pKey].push_back( rand() );
  }
}

我定时从随机选择的列表中查询 3000 万个随机元素。

结果

deque对于许多小列表，构建速度稍快，但在两种情况下，查询速度都比向量慢。我得出结论，我会vector< vector<T> >因为我的问题类型而坚持下去。

deque

Keys: 1000000, list size: 30
Mean time buildup: 1.29517 seconds
Mean time query: 4.17624 seconds

Keys: 10000, list size: 3000
Mean time buildup: 0.998761 seconds
Mean time query: 5.052 seconds


vector

Keys: 1000000, list size: 30
Mean time buildup: 1.5347 seconds
Mean time query: 1.63043 seconds

Keys: 10000, list size: 3000
Mean time buildup: 0.604954 seconds
Mean time query: 1.58328 seconds
4

3 回答 3

2

这是实现此类地图的有效且推荐的方法吗？

我认为这是实现这种地图的一种完全合理的方式。

另外，我想知道元素的连续性及其对调整大小的影响。说，我添加了一个元素my_map[key].push_back(val)，并且my_map[key]需要key != N-1调整大小。这是否会触发整个向量的副本my_map以保持其内容连续？或者是在my_map内部用指向堆上的向量的指针实现的？

不，它不会触发整个外部向量的副本。只有子向量是连续的；整个向量通常不是。

就心理模型而言，您可以将其my_map视为指向一维数组的指针数组，而不是单个连续的二维数组。

于 2013-03-13T10:58:18.127 回答
0

它复制外部向量中的向量对象。但是这些向量内的堆上的对象不会被重新分配。

于 2013-03-13T10:59:05.037 回答
0

每个 std::vector 通常都有一个内部指针，指向它分配 T 类型对象数组的内存。

在此类 T 类型的向量的向量中，调整内部向量的大小不会调整外部向量的大小（my_map在您的示例中），因为外部向量只能被视为指向此类数组的指针的向量。内部向量数组位于外部向量之外的其他内存位置。

出于同样的原因，你的内部向量之间没有邻接my_map

于 2013-03-13T10:59:07.407 回答