除了标准将其定义为连续的事实之外，为什么 std::vector 是连续的？
如果空间不足，则需要重新分配一个新块并将旧块复制到新块，然后再继续。
如果不是连续的呢？当存储填满时，它只会分配一个新块并保留旧块。通过迭代器访问时，它会执行简单的 >、< 检查以查看索引在哪个块中并返回它。这样，每次空间不足时都不需要复制数组。
这真的会工作/更好吗？还是我错过了什么？
问问题
6921 次
5 回答
27
如果std::vector不能保证连续性，就会发明一个新的容器来保证连续性。
连续性保证使得与期望连续数组的现有代码进行互操作变得更容易，并且还提供了非常好的性能，因为它是缓存友好的。（因此，对于中等大小，在中间插入/删除实际上非常快。）
在扩展时复制数组非常便宜 - 如果您一次向向量追加一百万个元素，则每个元素平均将被复制一次左右。
于 2013-11-09T12:48:43.103 回答
13
标准 C++ 库也定义了一个非连续的类数组容器：std::deque<T>. 迭代 astd::deque<T>比迭代 a 慢得多std::vector<T>。如果操作相当简单，它可能会慢 5 倍：这些是我在比较累加整数序列时得到的实际时间。这是您为非连续表示支付的成本！
这种相当陡峭的减速的原因是 gcc 知道如何在 a 上对循环进行矢量化，std::vector<int>而不是在 a 上std::deque<int>。即使没有矢量化，迭代也会慢约 30%。也就是说，相当小std::vector<T>的重新分配成本实际上并没有那么重要！
于 2013-11-09T14:47:19.010 回答
11
这有几个原因：
首先，由于两个因素，连续容器上的迭代比非连续容器上的迭代快得多：第一个是分支预测——处理器不需要在每次完成读取其中一个子时丢弃它的管道。容器，更少的管道重置意味着更快的代码。第二个是完全缓存一个连续的内存块比一堆各种各样的小块更容易，这使得你的数组更有可能被整个缓存。
其次，那里有很多 C++ 代码必须与 C 代码交互，并且很多代码在接收数组/缓冲区时需要一个连续的内存空间，因为这是最少依赖数据结构实现的方式去做吧。当您与不断需要缓冲区/数组的代码进行交互时，将您std::deque转换为数组的开销与实际瞬时传递到数组相比会付出代价std::vector（这基本上可以只是给出一个指向内部数组的指针） .
所有这些都证明了连续容器的存在是合理的。正如其他人所说，当您不需要快速迭代或内存连续性时，您始终可以使用std::deque.
于 2013-11-09T15:12:28.547 回答
9
通过使std::vector连续，它可以被视为一个数组。但是，它也可以调整大小。它的大小是在运行时而不是编译时定义的。此外，向量可用于为需要缓冲区的函数分配内存。这样做的好处是内存将在vector超出范围时被释放。例如，当使用ReadFile向量时，可用于创建缓冲区。：
unsigned int bytesRead = 0;
std::vector<char> buffer(fileSize);
// open file, etc.
ReadFile(hFileIn, buffer.data(), buffer.size(), &bytesRead, nullptr);
请注意，这data是 C++11 中的新功能。在旧代码中，您可能会看到一个等价的&(buffer.at(0))或&(buffer[0])返回第一个元素的地址。
Astd::deque更适合您所描述的内容。
于 2013-11-09T12:48:32.670 回答
3
作为其他答案的补充（它们非常完整），在一种情况下，您确实更喜欢向量不连续：当您需要同时调整向量的大小时。这就是 Intel Thread Building Block 提供 tbb::concurrent_vector 的原因，这或多或少是您所说的您所期望的
“当存储填满时，它只会分配一个新块并保留旧块。当通过迭代器访问时，它会执行简单的 >、< 检查索引在哪个块中并返回它。”
然后，比较 tbb::concurrent_vector 和 std::vector 将使您更好地了解连续内存的优点（速度）和缺点（不能同时增长 std::vector）。我希望 tbb::concurrent_vector 比 std::deque 得到更好的优化，这就是为什么 tbb::concurrent_vector vs std::vector 是一个更公平的比较。
于 2013-11-09T16:28:39.860 回答