在现代编程语言中，数据结构的选择对于程序的性能有着重要的影响。本文将探讨一种名为双端向量（Devector）的数据结构，它与传统的向量（std::vector）和双端队列（std::deque）相比，在某些操作中展现出了显著的优势。双端向量的概念相对简单：它允许数据在预分配空间的中间开始，这意味着可以在两端同时添加新元素，而不需要重新分配空间或移动元素。
如图1所示，std::vector的内存预留始终从预留内存的开始处开始，这个预留内存的大小称为容量。随着数据的增长，容量也应该增加。如果数据需要的空间超过了容量，就需要分配新的、容量更大的空间。新分配的空间通常比所需的空间大（大约是1.5或2.0倍）。这样可以避免频繁分配内存，因为数据在增长。向量的问题在于，它很容易将数据追加到向量的末尾（push_back操作），但不是开始。
如果数据大致位于预留空间的中间，那么它就可以在两个方向上增长，最终得到的就是双端向量或devector，如图2所示。数据可以在两个方向上增长，因此可以轻松执行push_front和push_back操作。前部空间用于push_front，尾部空间用于push_back；如果两者都没有足够的空间，通常可以预留一个新的内存槽，这个内存槽可以是所需数据大小的三倍，并且位于预留槽的中间。
在考虑插入操作时，需要特别考虑一个问题。当元素被插入到向量中时，只有一个选项——通过增加内存中的地址来移动其余元素。在devector中，有两个选项：将其余元素向前移动；将前面的元素向后移动。应该选择哪个选项？这取决于元素的位置。如果它更接近数据的末尾，则选择选项1（向前）。如果它更接近开始，则选择选项2（向后）。如果它在中间，两个选项都可以。图3展示了平衡插入的基本思想。
这重要吗？是的，很重要。想象一下，如果一个devector是使用随机插入元素构建的。通过使用平衡插入，可以将时间减半！如果一个devector用于创建一个包含“键-值”对元素的平面映射，并且使用二进制搜索来找到正确的元素。通过使用平衡devector，插入到平面映射中的时间可以与使用向量的时间相比减少一半。
不幸的是，在Boost实现（Boost devector）中，插入操作并不是平衡的，基准测试显示了这一点。包含了实现，称之为DeVector，其中插入和删除都是平衡的。
接下来，将展示一些基准测试的结果。首先，在Visual C++ 2022中测试了devector，并看到了使用devector的主要优势。然后在GCC 11.2中使用C++17进行了测试，结果并不那么明显。将展示两个编译器的结果。
代码在配备Intel i7-4790，3.6GHz处理器和16GB RAM的PC上执行。在Visual C++ 2022中编译时，使用了以下选项：
/O2 /Ob2 /arch:AVX2
在GCC 11.2中，使用了以下命令行：
g++ -O3 -std=c++17 -I"/boost_1_80_0" -m64 DeVectorTests.cpp -o DeVectorTests.exe
随机插入的结果显示在图4a中。图4a显示了在Visual C++ 2022中随机插入双精度浮点值的结果（每个元素的微秒数）。数据显示，向向量或Boost devector中进行随机插入的速度大约是向DeVector中进行平衡插入的两倍。同时，向deque中插入的速度平均比向DeVector中插入慢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的优势是显而易见的。
在GCC 11.2 C++中的随机插入结果如图4b所示。图4b显示了在GCC 11.2 C++中随机插入双精度浮点值的结果。有一些差异，但并不像在Visual C++中那样戏剧性：对于500万个元素或更多元素的数量，deque需要的时间是DeVector的两倍多。
随机访问的结果显示在图5a中。图5a显示了在Visual C++ 2022中随机访问双精度浮点值的结果（每个元素的纳秒数）。可以看到，在多达100,000个元素的结果中没有太大的差异，但随后访问deque元素的速度减慢，与所有其他结构形成对比。
在GCC 11.2 C++中的随机访问结果如图5b所示。图5b显示了在GCC 11.2 C++中随机访问双精度浮点值的结果。没有太大的差异。在实践中，访问10^9个元素在deque中需要38秒，在devector中需要32秒。
在所有结构中，除了向量外，这个操作被称为push_front。对于向量，使用索引0的插入。结果如图6a所示。图6a显示了在Visual C++ 2022中在开始处插入的结果（每个元素的纳秒数）。对于deque，每个元素大约需要27纳秒；对于双端向量大约需要10-12纳秒/元素；对于向量，非常低效。结果，向向量的前面插入500万个元素需要超过2.5小时，而所有其他结构只需要几秒钟。
在GCC 11.2 C++中的push_front结果如图6b所示。图6b显示了在GCC 11.2 C++中push_front的结果（每个元素的纳秒数）。没有太大的差异。但可以看到deque更快。但仍然在谈论几秒钟：对于将1000万个元素推到前面，deque需要0.05秒，而devector大约需要0.097秒。10亿个元素需要deque 4.4秒，而两种devector都需要大约7.7秒。
push_back操作没有什么特别的：它是一个非常快速的操作，即使对于一百万元素也需要几秒钟。结果如图7a所示。图7a显示了在Visual C++ 2022中push_back的结果（每个元素的纳秒数）。deque的性能大约比devectors慢2.5倍。
在GCC 11.2 C++中的结果是图7b所示。图7b显示了在GCC 11.2 C++中push_back操作的结果（每个元素的纳秒数）。deque稍微快一些。总的来说，结果与push_front相似。
结果清楚地表明，deque比双端向量慢，特别是在随机构建一百万元素或更多元素时。在随机访问中，deque也更慢。在Visual C++中，deque特别低效。惊讶地看到Visual C++和GCC实现之间的差异：deque的实现在后者中要好得多，其中push操作相当高效。