deque 添加删除元素 迭代器失效问题

deque的储存空间主体在缓冲区buffer中，由一段一段的定量连续空间组成。为了便于迭代器的寻址，除了此储存空间，deque采用一个表(map)来记录每个连续空间的首地址。map是一小块连续的空间，每个元素(node)都是指针，指向buffer中的各首地址。
指向deque中某元素的迭代器iterator实际结构如图所示，first和last分别指向buffer中本段连续空间的首尾元素，cur指向iterator解引用得到的元素，node指向map中对应的node。
==需要注意的是，deque要求map前后要各预留一个node节点，以便扩充可用。==

插入元素

• 头尾
  可能使指向其他元素的迭代器失效（buffer中一段连续空间满，需重新分配内存和map时），但指针、引用仍有效
• 其他位置
  迭代器、指针、引用失效

删除元素

• 头尾
  指向其他元素的迭代器、指针、引用仍然有效
• 其他位置
  迭代器、指针、引用失效

在deque中push_back插入元素的例子

对deque push_back(23)，buffer需添加一段新的连续内存空间，因此map的node节点不够用，map被释放，对map重新分配存储空间为new_map。所有iterator的node指向原map，因此iterator均失效。但buffer的原有空间并未发生改变，因此其他元素的引用、指针仍然有效。