这部分内容主要是针对序列式容器来记录的，了解各种序列式容器的底层实现以及对源码、实现逻辑进行分析。

分类

• 序列式容器(缩进表示基层与衍生层的关系，衍生是内含关系，例如priority_queue内含一个heap
  其中的元素是可序(ordered)，但未必有序(sorted)）
  
  • array(c++内建)
  • vector
    
    • heap(以算法形式呈现)
      
      • priority_queue
  • list(非标准)
  • slist(非标准)
  • deque(非标准)
    
    • stack(配接器, adapter，修改某物接口，形成另一种风貌)
    • queue(配接器, adapter)

vector

• vector
  
  • vector是动态空间，随着元素的增加，他的内部机制会自动扩充空间以容纳新元素，能够合理和灵活地运用内存。关键技术在于对其大小的控制以及重新配置时的数据移动效率。(array是静态空间，一旦配置了就不能改变，如果要换个大一点的空间，需要由用户客户端执行，首先需要配置一块新空间，再将元素从旧地址一一搬到新地址，最后将原来的空间还给系统)
  • vector维护的是一个连续线性空间，支持随机存取，普通指针有这样的能力，因此vector提供的是Random Access iterators
  • 数据结构：三个迭代器——start(表示目前使用空间的头)、finish(表示目前使用空间的尾)、end_of_storage(表示目前可用空间的尾)
  • 满载的时候，会扩充空间：重新配置、移动数据、释放原空间
  • 空间拓展的原则：如果原大小为0，则配置为1(个元素大小)，如果原大小不为0，则配置原大小的两倍，前半段用于放置原数据，后半段准备用来放置新数据。
  • 所谓的动态增加大小，不是在原空间之后接续新空间，而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后再在原内容之后构造新元素，释放原空间。因此一旦引起空间重新配置，指向原vector的所有迭代器都会失效。
  • 操作
    
    • push_back
    • pop_back
    • erase
    • clear
    • insert

if(插入元素个数大于0){1. 备用空间足够，大于等于新增元素个数1.1 插入点之后的现有元素大于新增元素个数uninitialized_copy()移动finishcopy_backward()fill()1.2 插入点只有的现有元素小于新增元素个数uninitialized_fill_n()移动finishuninitialized_copy()移动finishfill()2. 备用空间不够，扩展空间2.1 首先决定新长度：旧长度的两倍，或者旧长度+新增元素个数2.2 再将旧vector的插入点之前的元素复制到新空间 uninitialized_copy()2.3 再将新增元素填入新空间 uninitialized_fill_n()2.4 再将旧vector的插入点之后复制到新空间 uninitialized_copy()
}

list

• list
  
  • 每次插入或者删除一个元素，就配置或释放一个元素空间，对空间的使用绝对精准，对于任何位置的元素插入和删除都是常数时间
  • list是一个双向链表，而且是一个环状双向链表，迭代器必须具备前移后移的能力，所以list提供的是Bidirectional Iterators
  • 插入和删除操作不会造成原有的list迭代器失效
  • 相关操作：push_back, push_front，erase, pop_front,pop_back, clear, remove,unique
  • transfer迁移操作：将某连续范围的元素迁移到某个特定位置之前，技术上只是指针的移动而已。
  • list不能用STL算法的sort()，必须使用自己的sort() member function，因为STL的sort函数只接受RandomAccessIterator

deque

• deque

  • 双向开口的连续线性空间，可在头尾两端分别做元素的插入和删除，效率为常数时间。没有容量的概念，它是以分段连续空间组合而成，随时可以增加一段新的空间并链接起来
  • deque是由一段一段的定量连续空间构成，一旦有必要在deque的前端或者尾部增加新空间，便配置一段定量持续空间，串接在整个deque的头端或尾端。

  • start(iterator)指向第一缓冲区的第一个元素：cur,first, last, node
    finish(iterator)指向最后缓冲区的最后一个元素的下一个位置:cur, first, last, node
    多个缓存区，每个缓存区储存多个元素
    维护一个指向map的指针map_pointer，也维护start、finish的迭代器
    

  • 在头部或者尾部插入元素的时候，会判断是否需要扩充map(备用空间是否足够)，如果需要就付诸行动，配置一块新的缓冲区，直接将节点安置在现有的map中，设定新元素，然后改变迭代器start或者finish的状态。

  • 相关操作：push_back(考虑扩充缓冲区)、push_front(考虑扩充缓冲区)、pop_back(考虑将缓冲区释放掉)、pop_front(考虑将缓冲区释放掉)、clear(回复初始状态，即保留一个缓冲区)、erase(根据position，判断移动前面的元素还是后面的元素)、insert(根据插入值的position，判断移动前面的元素还是后面的元素，挪好位置再插入值)

stack

• stack
  
  • 先进后出的结构
  • SGI STL以deque为缺省情况下stack的底部结构，也可以用list作为底层结构。封闭其头端开口。
  • 相关操作：empty,size, front, back, push, pop
  • stack不提供走访功能，不提供迭代器

template<class T,class Sequence=deque<T> >
class stack{...
}

queue

• queue
  
  • queue是一种先进先出的数据结构，有两个出口，从最底端存入，从最顶端取出，不存在遍历行为
  • 相关操作：empty,size, front, back, push, pop
  • 底层结构可以是deque也可以是list

heap

• heap
  
  • 不归属STL容器组件，binary max heap是priority_queue的底层机制。没有迭代器
  • binary heap是一种完全二叉树，除了最底层的叶子节点，其他节点都是填满的，最底层的叶子节点从左到右不得有空隙，可用array来存储所有节点。
  • 对于节点位于array的i处时，其左子节点位于array的2i处，其右节点位于array的2i+1处，其父节点为i/2(取整)
  • heap可分为max-heap(最大值在根节点，STL提供)与min-heap
  • push_heap算法(上溯法)
    
    1. 将节点放在最下层作为叶节点，填补从左至右的第一个空格
    2. 向上比较父节点与当前节点，如果叶子节点比父节点大，交换两者的值
    3. 直至到顶端，或者满足heap的次序才停止
  • pop_heap算法(下溯法)
    因为取走的一定是根节点，我们必须割舍最下层最右边的叶子节点，将它的值重新安插到max-heap中，重新调整heap的结构。pop_heap后，最大元素只是被放在了底部容器的最尾端，尚未被取走。要用pop_back()操作函数。
    
    1. 比较左右孩子的大小
    2. 替换洞值和max(左右孩子)的值，移动洞值
    3. 往下继续调整
  • make_heap算法

priority_queue

• priority_queue
  
  • 归类为container adapter，没有迭代器
  • 允许用户以任何次序将任何元素存入容器中，但取出的时候一定是从优先级最高的元素开始取。
  • 如果用RB tree作为priority_queue的底层机制，元素的插入和极值的取得有O(logN)的表现，但是小题大做。binary search tree(RB tree)要求输入足够随机，并且binary search tree(RB tree)不容易实现。
  • priority_queue的复杂度介于queue和binary search tree之间，比较适合。binary heap满足条件。

slist

• slist
  
  • 单向链表，single linked list，与list的区别在于，list的迭代器是双向的bidirectional iterator, 而slist的迭代器是单向的forwarded Iterator。优点在于所耗用的空间更小，某些操作更快。共同点在于他们的插入(insert)、移除(erase)、结合(splice)等操作不会引起原来的迭代器失效。
  • 相关操作：insert_after, erase_after, push_front