使用 Devector 比 std::deque 更好
5.00/5 (8投票s)
本文表明，双端向量（devector）比 std::deque 快得多，应该优先使用。
1. 引言
双端向量（devector）已被讨论过几次。其中一些实现由 Lars Greger Nordland Hagen [1]、 Valasiadis Fotios [2] 完成，此外还有一个 Boost 实现 [3]。
双端向量的概念非常简单：如果一个 vector 中的数据从预分配空间的开头开始，那么在双端向量中，数据相对位于中间，这意味着在一段时间内，可以在两端添加新元素，而无需重新分配空间或移动元素。
图 1 展示了 std::vector 的内存预留。
图 1. std::vector 内存预留。数据空间始终从预留内存的开头开始，其大小称为容量。随着数据的增长，容量应增加。
如果数据需要的空间超过了容量，则应分配具有增加容量的新空间。新分配的空间通常大于所需空间（因子在 1.5 到 2.0 之间）。这可以避免在数据增加时过于频繁地分配内存。vector 的问题在于，很容易在 vector 的末尾添加数据（**push_back** 操作），但在开头不行。
如果数据大致位于预留空间的 中间，以便它可以在两个方向上增长，我们就得到了**双端向量**或 devector，如图 2 所示。
图 2. Devector 内存预留。**数据 可以在两个方向上增长，因此可以轻松执行 push_front 和 push_back 操作。**
头部空间用于 push_front ，尾部容量用于 push_back ；如果任一方向的空间不足，通常可以预留一个新的内存槽，该槽的大小可以是所需数据大小的三倍，数据将位于预留槽的中间。
2. 特殊考虑：平衡插入
一个需要考虑的问题是插入。当元素被插入到 vector 中时，只有一个选项——通过增加内存中元素的地址来向前移动其余元素。在 devector 中， 则有两个选项：
- 向前移动其余元素；
- 向后移动前面的元素。
选择哪种选项？这取决于元素的位置。如果它更靠近数据的末尾，则选择选项 1（向前）。如果它更靠近开头，则选择选项 2（向后）。如果它在中间，则任一选项都可以。图 3 示出了平衡插入的基本思想。
图 3. Devector 中的平衡插入.
这重要吗？是的，很重要。想象一下，如果一个 devector 是使用随机插入元素构建的。通过使用平衡插入，我们可以将时间缩短一半！如果一个 devector 用于创建一个 flat map ，其中包含“键值”对作为元素并使用二分查找来找到正确的元素。通过使用平衡的 devector ，与 vector 所用时间相比， flat map 的插入时间可以缩短一半。
不幸的是，在 Boost 实现（ Boost devector ）中，插入不是平衡的，基准测试显示了这一点。我已经包含了我的实现，我称之为 DeVector ，其中插入和删除都是平衡的。
3. 基准测试
3.1. 总体观察
起初，我在 Visual C++ 2022 中测试了 devector，发现使用 devector 有很大的优势。然后我在 GCC 11.2 和 C++17 中进行了测试，结果不太明显。 我将同时展示两个编译器的结果。
3.2. 使用的系统
代码在一台配备 Intel i7-4790、3.6GHz 处理器、16GB RAM 的 PC 上执行。
在 Visual C++ 2022 中编译时，使用了以下选项
在 GCC 11.2 中，使用了以下命令行
g++ -O3 -std=c++17 -I"/boost_1_80_0" -m64 DeVectorTests.cpp -o DeVectorTests.exe
3.3. 随机插入
3.3.1. Visual C++ 2022 的结果
图 4a 显示了随机插入的结果。
图 4a. Visual C++ 2022。 随机插入双精度浮点值（每元素微秒）。数据采用对数刻度。
这表明，与使用平衡插入的 DeVector 相比， vector 或 Boost devector 的随机插入大约慢一倍。同时，与 DeVector 相比， deque 的插入平均慢 7 倍，对于 500 万个元素，这一比例增加到 14 倍。这在实际创建包含 500 万个元素的结构时意味着什么？
- 对于
std::deque，需要 8 小时； - 对于
std::vector和Boost devector，需要 1 小时 5 分钟； - 对于
DeVector，需要 34 分钟。
对于 100,000 个元素
- 对于
std::deque，需要 3 秒； - 对于
std::vector，大约需要 0.7 秒； - 对于
Boost devector，大约需要 0.85 秒； - 对于
DeVector，需要 0.5 秒。
对于随机插入，双端向量相对于 std::deque 的优势显而易见。
3.3.2. GCC 11.2 C++ 的结果
图 4b 显示了随机插入的结果。
图 4b. GCC 11.2 C++。 随机插入双精度浮点值（每元素微秒）。
有一些差异，但没有 Visual C++ 中那么显著：对于 500 万个及以上元素， deque 所需的时间是 DeVector 的两倍多。
3.4. 随机访问
3.4.1. Visual C++ 2022 的结果
随机访问结果如图 5a 所示。
图 5a. Visual C++ 2022。 随机访问双精度浮点值（每元素纳秒）。
可以看到，对于多达 100,000 个元素，结果没有太大差异，但之后 deque 元素的访问速度开始减慢，与所有其他结构相比。
3.4.2. GCC 11.2 C++ 的结果
随机访问结果如图 5b 所示。
图 5b. GCC 11.2 C++。 随机访问双精度浮点值（每元素纳秒）。
差异不大。实际上，访问 deque 中的 109 个元素需要 38 秒，而访问 devector 中的相同数量的元素需要 32 秒。
3.5. 在开头插入
3.5.1. Visual C++ 2022 的结果
在所有结构中，除了 vector ，此操作称为 push_front 。 对于 vector ，使用的是索引为 0 的 insert 。结果如图 6a 所示。
图 6a. Visual C++ 2022。在开头插入（纳秒/元素）。
对于 deque ，每个元素大约需要 27 纳秒；对于双端向量，大约需要 10-12 纳秒/元素；对于 vector ，效率非常低。结果是，在 vector 的开头插入 500 万个元素需要超过 2.5 小时，而对于所有其他结构，则只需零点几秒。
3.5.2. GCC 11.2 C++ 的结果
图 6b 显示了 push_front 的结果。
图 6b. GCC 11.2 C++。push_front 的结果（纳秒/元素）。
没有重大差异。但你可以看到 deque 更快。但我们仍然在谈论零点几秒：将 1000 万个元素推送到前面， deque 需要 0.05 秒， devector 大约需要 0.097 秒。10 亿个元素对于 deque 需要 4.4 秒，对于两个 devectors 大约需要 7.7 秒。
3.6. **push_back** 操作
3.6.1. Visual C++ 2022 的结果
关于 push_back 没有什么特别之处：这是一个非常快速的操作，即使对于一百万个元素也只需要零点几秒。 结果如图 7a 所示。
图 7a. push_back（纳秒/元素）。
deque 的性能大约是 devectors 的 2.5 倍慢。
3.6.2. GCC 11.2 C++
结果如图 7b 所示。
图 7b. push_back 操作（纳秒/元素）。
结果 deque 略快。总的来说，结果与 push_front 相似。
4. 结论
结果清楚地表明， deque 比双端向量慢，尤其是在随机构建一百万个或更多元素时。在随机访问方面， deque 也较慢。在 Visual C++ 中， deque 尤其效率低下。令我惊讶的是 Visual C++ 和 GCC 实现之间的差异：后者的 deque 实现要好得多，推操作相当高效。
也许 C++ 库应该提供 devector 作为标准结构之一，例如 std::deque 、 std::vector 和 std::list 。 deque 而不是 devector 的唯一优势可能是内存空间较小的系统，在这些系统中，很难分配大块内存，因为碎片化分配可能具有一些优势。
实际上，对于存储 10000 个浮点元素， deque 足够了。对于更多的元素，应特别注意性能，应优先选择 devector ，因为其随机插入和访问更有效。
参考文献
1. http://larshagencpp.github.io/blog/2016/05/22/devector
2. https://github.com/fvalasiad/devector
3. https://boost.ac.cn/