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();
