std::vector 连续性含义

Question

我在很多地方看到过，比如这里，说std::vector总是连续的，但我没有找到解释其意义或为什么这很重要的说明？

这是否意味着它们在内存中有一个固定的位置或者其他什么呢？

- novalain

---

我认为你应该在“英语语言和用法”论坛上提出问题。 :) - Vlad from Moscow

我知道contiguous的意思，但不知道在这个上下文中是什么意思。 - novalain

Answer 1

在这个上下文中，“连续的”意味着顺序编号的向量元素在内存空间中相邻。例如，如果一个元素 i 位于地址 a，并且具有大小 s，则元素 i+1 将位于地址 a+s，元素 i+2 将位于 a+s+s，以此类推。

这是有两个重要原因：

- 连续性要求使随机访问成为可能 - 您可以根据向量的基地址和元素的索引计算任何元素的位置。 - 您可以预测参考局部性 - 对于缓存行为分析，按顺序处理向量元素与按顺序处理数组元素相同。

- Sergey Kalinichenko

Answer 2

std::vector中的元素占据一段连续的内存块。 std::vector是一个改进的数组。

这很重要，因为它意味着对任意元素的访问速度快。由于大小和元素数量已知，您可以快速查找任何元素。

缺点是任何重新组织，例如在中间插入或删除元素，都是昂贵的操作，因为它需要所有其他元素进行洗牌以保持连续性。

其他数据结构（如列表）允许更容易的重新组织，但也有其他权衡。

- jbarlow

---

这与性能有关，但不是主要原因。请看@sashang的回答。 - Eldar Dordzhiev

@Eldar Dordzhiev：我说过你可以快速查找任何元素。我没有描述指针算术运算的工作原理，因为这是一个初学者问题。实际上，在std::vector上执行指针算术运算是错误的做法。 - jbarlow

我告诉你 std::vector 要求查找速度快，但不保证是连续的。这在 C++11 标准中已经修复。另外，std::vector<bool> 不是连续的。 - Eldar Dordzhiev

Answer 3

这意味着您始终可以通过指针算术运算访问下一个元素的地址。

- sashang

Answer 4

它意味着在 std::vector 的内部存储表示中没有空洞。在内存中看起来像这样：

每个方格代表内存中的一个地址，每个橙色方格表示向量占用的一个元素。

大多数其他容器不是连续的。例如，std::forward_list 在内存中的结构如下：

在这里，橙色地址包含容器的元素。但是它们分散在内存中。还有灰色元素；它们代表列表需要的额外内存，以使每个元素知道下一个元素的位置。^[*] 可以想象，std::vector的清晰简洁的内存表示给您带来了许多优势。这就解释了为什么std::vector具有其他容器缺乏的某些操作，或者为什么这些操作在常数时间内运行。例如，要到达第n个元素，只需执行一次加法（基地址+n）。这也解释了为什么您可以安全地获取&v [0]并对其执行指针算术运算。

---

这是一种简化，因为示例中有char元素，但列表中的指针占用的内存比典型的C++实现中单个char更多。更真实的图表应该使用4或8个灰色方块来表示每个元素，因为这是典型现代计算机上一个指针的大小。

- Christian Hackl

Answer 5

由于没有任何答案提到这一点：

感谢 std::vector 的这个特性，你可以做出以下操作：

std::ifstream file( "file.txt", std::ios::ate | std::ios::binary );
std::vector<char> vec;
if (!file)
{
    file.seekg(0, std::ios_base::end);
    auto fileSize = file.tellg();
    vec.resize(fileSize);

    file.seekg(0, std::ios_base::beg);

    // here we leverage contiguous memory in std::vector
    file.read(&vec[0], fileSize);
}

避免逐个读取/写入元素的方法。

这可以自C++03开始使用，正如（C++03）标准中所述（23.2.4.1）

vector的元素是连续存储的，这意味着如果v是一个vector，其中T是除bool之外的某种类型，则它遵循所有0 <= n < v.size()的恒等式&v[n] == &v[0] + n。

- Patryk