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 视为指向一维数组的指针数组，而不是单个连续的二维数组。