c++ - STL deque::insert() 的复杂性

Question

我从 C++ 标准 2003(第 23.2.1.3 章)了解到 deque::insert() 的复杂性如下:

在最坏的情况下，将单个元素插入双端队列所花费的时间与从插入点到双端队列开头的距离和从插入点到双端队列末尾的距离中的最小值成线性关系。

一直把STL deque的实现理解为内存块的集合。因此，插入只会影响与插入位置相同的内存块中的元素。我的问题是，标准中所说的“从插入点到双端队列开头的距离和从插入点到双端队列结尾的距离的最小值呈线性关系”是什么意思？

我的理解是因为C++标准没有强制deque的某种实现。对于最坏的情况，复杂性一般。然而，在编译器的实际实现中，它与内存块中元素的数量成线性关系，不同的元素大小可能会有所不同。

另一种猜测可能是，由于 insert() 会使所有迭代器失效，因此 deque 需要更新所有迭代器。因此它是线性的。

Answer 1

std::deque 通常(总是？)实现为内存块的集合，但是它通常不会插入一个全新的 block ，只是为了让您在集合的中间。因此，它会找出插入点是更靠近开头还是结尾，然后打乱现有元素以为现有 block 中的新元素腾出空间。它只会在集合的开头或结尾添加一个新的内存块。