在最坏的情况下,将单个元素插入到双端队列中需要时间在从插入点到双端队列开始的距离的最小值以及从插入点到双端队列结束的距离的线性.

我总是将stl deque的实现理解为内存块的集合.因此,插入仅影响与插入位置相同的存储块中的元素.我的问题是,标准是什么意思是“从插入点到双端队列开始的距离的最小值和从插入点到双端队列结束的距离的线性”？

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

另一个猜测可能是,因为insert()将使所有迭代器无效,deque需要更新所有迭代器.因此它是线性的.