dynamic arrays 的基本实现大小为 2n，其中一半空间由现有元素填充，另一半保留在末尾，用于在 O(1) 时间内追加新元素。
在数组末尾以外的任何地方插入新元素需要重新分配数组，这是一项昂贵的操作。
是否有可调整大小数组的任何 C++ 实现，其中空间也在数组的开头保留，以便有效地前置元素？如果是这样，与末尾为追加保留的空间相比，保留了多少空间？我想预置是一个不太常见的操作，但如果它在程序中发生得足够频繁，那么在每个预置操作上重新分配可能是毁灭性的。
最佳答案
Deques允许在摊销的常数时间内添加和添加。
不同于vectors ，其中数组连续存储并在达到容量时重新分配，不保证双端队列元素连续存储。相反，双端队列以 block 的形式存储元素。如果由于 push_back() 而需要更多空间或 push_front()调用，一个新的空间 block 被分配并链接到。
感谢Mark Ransom用于在评论中发布有关双端队列的信息。
关于c++ - 动态数组的实现是否在开始时预留空间用于前置？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25513845/