STL的容器

• 顺序容器 vector(向量)、list（列表）、deque（队列）

  
  
  image.png

-- v1.end()指向的是最后一个元素的下一个位置
-- vector.clear()
-- vector.assign(iterator begin, iterator end) 会清空vector中原先的内容
-- 查找函数总结：https://segmentfault.com/a/1190000002890862
-- vector中的vt.capacity()表示vector的空间大小，vt.size()表示实际的对象数目，vt.resize(100)表示既创建空间又构造对象为默认初始化对象（0），vt.reserve(100)表示预留空间但不创建对象。
-- queue<int> q; q.front(); q.back(); q.push(); q.pop();

• map（集合）、set（映射）、multimap（多重集合）、multiset（多重映射） 容器适配器 栈stack 、队列queue 和优先级队列priority_queue
• pair<string, string> 两个类型不必相同，访问为->first, ->second

链表

常见题目

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第n个节点
• 链表的中间结点

哈希表

• C++ STL11: unordered_map<x,y> 对于基本类型，默认的值初始化为0
• 查找效率高，时间复杂度为常数级别 O(1)， 而额外空间复杂度则要高出许多
• 对于需要高效率查询的情况，使用 unordered_map 容器。而如果对内存大小比较敏感或者数据存储要求有序的话，则可以用 map 容器。
• unordered_map<> h(nums.begin(),nums.end());
• insert（） erase() s.count(val)
• map: 查找操作的时间复杂度为 O(logN)
  -- hash_map.lower_bound(val)
  -- hash_map.upper_bound(val) 均返回iterator

红黑树

• 红黑树是一种近似于平衡的二叉查找树，里面的数据是有序的

栈

stack<type> st;
st.push_back();
st.top();
st.pop();
st.push(i);

单调栈

博客：https://blog.csdn.net/liujian20150808/article/details/50752861， https://www.cnblogs.com/grandyang/p/8887985.html

优先队列

• 优先输出小队列 priority_queue<int, vector<int>, greater<int> > p;
• 自定义

struct cmp{
bool operator()(Node a, Node b){
    if(a.x == b.x)  return a.y>b.y;
    return a.x>b.x;}
};

priority_queue<Node, vector<Node>, cmp> q;
q.push(1);
q.top();
q.pop();