STL 顺序容器
vector
- vector的底层是线性连续空间，vector是动态空间，内部机制会自行扩充空间
- vector的迭代器是普通指针，因此支持随机存取
- vector向尾端增长，如果发生满载或者在头部加入元素，会自动扩充空间(重新配置内存，元素移动，释放原空间)，过程占用很长时间
- 如果空间重新配置，则指向原vector的迭代器全部失效
- 使用alloc作为空间配置器
- 函数
- size() vector长度
- capacity() 内存空间大小
- resize() 重新配置空间
- pop_back() 删除最后一个元素，不会减小空间大小
- insert(iterator position, size_type n, const T& x); 插入点之后插入n个x，其他元素往后复制
list
- list是双向链表结构，更是环向链表，只需要一个指针就可以完整的表现整个链表
- list迭代器有能力进行正确的递增、递减、取值和成员存取等操作
- 插入和接合操作，迭代器不会失效
- 使用alloc作为空间配置器
- 函数
- front() 取头结点的元素
- back() 取尾节点的元素
- get_node() 配置一个节点
- creat_node() 配置并构造一个节点
- put_node() 释放一个节点
- destroy_node() 析构并释放一个函数
- push_front() 插入节点作为头结点
- push_back() 插入节点作为尾节点
- pop_front() 移除头结点
- pop_back() 移除尾节点
- remove(const T& value) 将值为value的节点移除
- unique() 移除连续而相同的元素，只剩最后一个
- transfer(iterator position, iterator first, iterator last) 将[first, last)之间的元素全部移动到position之前
- splice() 接合于position所指位置之前
- merge() 合并两个递增排序的list
deque
- 双向开口的连续线性空间，动态的以分段连续空间组合而成，在首端或者尾端配置定量连续空间串联在首部或者尾部
- 允许尝试时间内对头端进行元素插入和移除操作
- 迭代器不是普通指针，复杂度较高
- 使用一个map作为主控，map的每个元素管理一段连续线性空间，map每个元素都是指向每个缓冲区的头部节点
- deque维护两个迭代器start，finish指向第一个缓冲区的第一个元素和最后一个缓冲区的最后一个元素
deque<int, alloc, 8> ideq(20,9);缓冲区大小为8个元素，保留20个元素空间，每个元素的初值为9，必须指明alloc为空间配置器push_back_aux()配置一块新的缓冲区，更新迭代器finish的状态- 如果遇到需要配置一个节点，判断是否需要扩充map
reserve_map_at_front()，可能需要重新换一个map pop_back()删除最后一个缓冲区的最后元素，如果删除最后一个元素后，最后一个缓冲区没有内容，则释放最后一个缓冲区pop_back_aux()，finish指向上一个缓冲区的最后一个元素pop_front()用法类比上一条，pop_front_aux()clear()删除所有元素，释放除一个缓冲区外的所有元素insert()插入元素，如果在开始处使用push_front()，结尾处使用push_back()，否则使用insert_aux()insert_aux()判断插入点前面元素多还是后面元素多，移动少的那一部分元素，插入新值
stack
- 后进先出数据结构，不允许遍历，只能新增、移除、取出最顶端元素，没有迭代器
- 使用既有容器作为底部结构，改变接口变成后进先出，这种以底部容器完成所有工作的称为配接器
- 函数
- empty()
- size()
- top() 取出最后一个元素
- push()
- pop() 删除最后一个元素
queue
- queue是一种先进先出的数据结构，从底端加入元素，从顶端取出元素，不允许遍历
- 使用既有容器作为底部结构，是配接器
- 函数
- empty()
- size()
- front()
- back()
- push()
- pop()
heap
- 底层是完全二叉树，使用数组来存储所有节点，并且满足根节点比左右节点都大/小
push_heap()，插入元素到树的末尾，如果比父节点大，和父节点交换，不断上溯，知道满足条件pop_heap()，根节点是最大值，交换收尾节点，下溯至叶节点末端，使用back()取的末尾的值，使用pop_back()移除末尾节点sort_heap()算法，对整个heap做pop_heap()操作后，向前缩减一个元素，以此类推完成排序make_heap()算法，将现有的数据转换为一个heap- heap没有迭代器，不能遍历
priority_queue
- priority_queue默认是使用vector表现的完全二叉树，是配接器
- priority_queue没有迭代器，不能遍历
- 函数
- empty()
- size()
- top() 返回根节点的元素
- push() 将元素加入末端，然后重排heap
- pop() 取出根节点至末尾，重排除末尾外的所有元素，使用pop_back()取出被弹出的元素
slist
- 单向链表，迭代器是单向的Forward Iterator，插入、移除、接合操作不会使迭代器失效
- 只提供push_front()，元素顺序和插入顺序相反
- 函数/迭代器
- creat_node() 配置空间，构造元素
- destroy_node() 析构元素，释放空间
- head 头部节点
- begin()
- end()
- size() 需要遍历单向链表才能得到
- empty()
- swap()
- front() 取头部元素
- push_front() 从头部插入元素
- pop_front() 从头部删除元素
- insert(iterator, val) 在位置iterator前面插入99
