deque

一个非常强大的数据结构，既支持 O(1) 随机读取，又支持 O(1) 的头部增删和尾部增删，不过有一定的额外开销。操作大同vector。（可认为底层是连续的）

• 任意位置插入一个元素：deq.insert(iterator it, const T& x);
• 任意位置删除一个元素：deq.erase(iterator it);

迭代器失效

笔者在面字节时受其bug困扰，了解到这个事实：

• 已映射的迭代器，在顺序式容器下，若进行一定的调整，迭代器可能会失效。

• 这个失效表现为，获取不到正确的信息。粗暴理解之，迭代器相当于下标。

• 因此，此类需要则建议使用非线性容器。比如说list

list

双向链表，与deque大致相同，但是由于 list 的实现是链表，因此不提供随机访问的接口。若需要访问中间元素，则需要使用迭代器。相较于 deque ，如果需要大量的插入和删除，而不关心随机存取，则应使用list。