c++ - vector 的 STL vector - 好主意？调整 "inner" vector 大小的机制？

Question

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

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

我有两个问题:

这是实现此类 map 的一种有效且值得推荐的方法吗？

此外，我想知道元素的连续性及其对调整大小的影响。说，我用 my_map[key].push_back(val) 添加了一个元素, 和 my_map[key]与 key != N-1需要调整大小。这会触发整个 vector 的拷贝吗 my_map为了保持其内容连续？或者是 my_map通过指向堆上 vector 的指针在内部实现？

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

---

更新

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

我对随机访问“建立”进行了计时，其工作方式如下:

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

Answer 1

Is this an efficient and recommended way of realizing such a map?

我认为这是实现这种 map 的一种非常合理的方式。

Also, I wonder about contiguity of elements and its implications on resizing. Say, I add an element with my_map[key].push_back(val), and my_map[key] with key != N-1 needs to resize. Does this trigger a copy of the entire vector my_map in order to keep its contents contiguous? Or is my_map realized internally with pointers to vectors on the heap?

不，它不会触发整个外部 vector 的复制。只有子 vector 是连续的；整个 vector 通常不是。

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