SGI STL 标准库 deque stack queue 4

github源码分析仓库

deque 双端队列

vector是单向开口的连续线程空间,deque是双向开口的连续线性空间。
deque支持常数事件内对起头端进行元素的插入和移除操作。deque没有容量的概念,因为它由动态分段连续空间组合而成,随时可以增加一段新空间并链接起来。
deque提供RandomAccessIterator。
deque是由一段一段的定量连续空间组成。一旦有必要在deque的前端或者尾端增加新空间,则需要配置一段定量连续空间,串接在整个deque的头端或尾端,deque的最大任务,便是在分段的定量连续空间上,维护其整体连续的假象,提供随机存取的接口,避开”重新配置、复制、释放”,代价则是复杂的迭代器构架。
deque采用一块”map”(不是STL的map容器)作为主控,管理缓冲区(多块定量连续空间)。”map”是一小块连续空间,每个node都是指针,指向另一段连续线性空间,即缓冲区,缓冲区是deque的存储空间主体。SGI STL允许指定缓冲区大小,默认0表示使用512B缓冲区。

deque的结构设计中,map和node-buffer的关系

deque的结构设计中,map和node-buffer的关系

deque中控器、缓冲区、迭代器的相互关系

deque中控器、缓冲区、迭代器的相互关系

deque::begin()传回迭代器start, deque::end()传回迭代器finish

deque::begin()传回迭代器start, deque::end()传回迭代器finish

deque的插入、删除操作会导致迭代器失效,需要注意。

stack 栈

stack是种先进后出(FILO)的数据结构,只要一个出口,stack允许新增元素,移除元素,取得最顶端元素。stack不允许遍历行为,因此stack没有迭代器。
SGI STL缺省使用deque作为stack的底部结构,因此stack是一种配接器(修改某物接口,形成另一种风貌)。
stack也可以用list作为底层容器。

queue 队列

queue是种先进先出(FIFO)的数据结构,只有一个入口,也只有一个入口,queue循序新增元素,移除元素,从最底端加入元素、取得最顶端元素。queue不允许遍历操作,因此queue没有迭代器。
SGI STL缺省使用deque作为queue的底部结构,因此queue是一种配接器(修改某物接口,形成另一种风貌)。
queue也可以用list作为底层容器。