我从C++标准2003(第23.2.1.3章)中学到了deque::insert()的复杂性，如下所示:
在最坏的情况下，将单个元素插入双端队列在从插入点到双端队列的开始处的距离和从插入点到双端队列的末尾的距离中最小的时间是线性的。
我一直将STL deque的实现理解为内存块的集合。因此，插入只会影响与插入位置相同的存储块中的元素。我的问题是，“从插入点到双端队列的距离和从插入点到双端队列的末尾的距离中的最小值是线性的”，这个标准是什么意思？
我的理解是因为C++标准没有强制执行双端队列。一般而言，最坏的情况就是复杂性。但是，在编译器的实际实现中，它与内存块中的元素数量成线性关系，该数量可能随元素大小的不同而变化。
另一个猜测可能是，由于insert()将使所有迭代器无效，因此deque需要更新所有迭代器。因此，它是线性的。
最佳答案
std::deque通常(总是？)实现为一组内存块，但是通常不会仅仅为了您在集合的中间插入一个新元素而插入一个全新的块。这样，它会发现插入点是更靠近起点还是终点，并且对现有元素进行混洗以为现有块中的新元素腾出空间。它只会在集合的开头或结尾添加新的内存块。
关于c++ - STL deque::insert()的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7572529/