为什么std :: vector是连续的？

Question

除了标准将其定义为连续的事实之外,为什么std :: vector是连续的？

如果空间不足,则需要重新分配新块并将旧块复制到新块,然后再继续.

如果它不连续怎么办？当存储填满时,它只会分配一个新块并保留旧块.当通过迭代器访问时,它会执行简单的>,<检查以查看索引所在的块并将其返回.这样,每次空间不足时都不需要复制数组.

这会真的有用吗？还是我错过了什么？

Answer 1

如果std::vector不能保证连续性,那么就会发明一种新的容器.

连续性保证使得更容易与期望连续数组的现有代码进行互操作,并且由于它是缓存友好的,因此也提供了非常好的性能.(因此,在中间插入/删除对于中等大小来说非常快.)

在扩展上复制数组是非常便宜的 - 如果你一次向一个向量追加一百万个元素,每个元素平均一次被复制一次.

Answer 2

标准C++库也定义了一个非连续的类似数组的容器:std::deque<T>.迭代a std::deque<T>比迭代a慢得多std::vector<T>.如果操作相当简单,它可能会慢5倍:这是我在比较累积整数序列时得到的实际时间.这是您为非连续表示支付的费用!

这种相当陡峭的减速的原因是gcc知道如何将循环矢量化为a std::vector<int>而不是a std::deque<int>.即使没有矢量化,迭代也会慢约30%.也就是说,std::vector<T>重新分配的相当小的成本实际上并不那么重要!

Answer 3

这有几个原因:

首先,由于两个因素,对连续容器的迭代要比非连续容器快得多:第一个是分支预测 - 处理器不需要在每次完成读取其中一个子系统时丢弃其管道容器和更少的管道重置意味着更快的代码.第二个是完全缓存连续的内存块要比一堆各种小块容易得多,这使得你的阵列更有可能完全缓存.

其次,有很多C++代码必须与C代码进行交互,并且许多代码在接收数组/缓冲区时会期望连续的内存空间,因为这是与数据结构最不依赖的实现方式去做吧.当您与不断期望缓冲区/数组的代码进行交互时,将数据转换std::deque为数组的开销与数组的实际瞬时传递相比std::vector(这基本上只是给出了指向内部数组的指针) .

所有这些都证明存在一个连续的容器.正如其他人所说,当你不需要快速迭代或连续的内存时,你总是可以使用std::deque.

Answer 4

通过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])返回第一个元素的地址.

A std::deque将更适合您所描述的内容.