C++ STL容器
一、序列式容器
容器的通用查询方法
InputIterator find (InputIterator first, InputIterator last, const T& val);
其中，first 和 last 为输入迭代器，[first, last) 用于指定该函数的查找范围；val 为要查找的目标元素。
该函数会返回一个输入迭代器，当 find() 函数查找成功时，其指向的是在 [first, last) 区域内查找到的第一个目标元素；如果查找失败，则该迭代器的指向和 last 相同。
count(first,last,value);
其中first是容器的首迭代器，last是容器的末迭代器，value是询问的元素。函数返回和value相同的元素个数；
count可以用于关联容器的查询：
map<Key_Type, ValType> mymap;
if(map.count(value1) == 0){/*.没有元素.*/}1. vector
特点：从尾部快速插入和删除，可直接访问任意元素。
实现：动态数组。malloc、rela
常用方法：
头文件：
#include <vector>创建和初始化
vector<Type> arr; vector<Type> arr(n [, val]); //创建长度为n，[初始值为val]的数组 vector<vector<Type>> arr(n, vector<Type>(m, val)); //n*m的二维数组，初值为val
尾部插入和删除
arr.push_back(elem); //尾部插入 arr.pop_back(); //尾部删除
查询
arr[i]; //下标访问 arr.front(); //返回头部元素 arr.back(); //返回尾部元素
容器大小
arr.size(); //返回元素个数 arr.capacity(); //容器容量
任意位置插入
arr.insert(pos, elem); //pos位置插入elem arr.insert(pos, n, elem); //pos位置插入n个elem
任意位置删除
arr.erase(pos); //删除pos位置元素，返回下一个元素位置 arr.erase(begin, end); //删除[begin, end)元素，返回下一个的位置
逆序存储
arr.reverse(pos1, pos2); //pos1到pos2的元素逆序存储
迭代器
arr.begin(); arr.end(); for(auto i = arr.begin(); i != arr.end(); i++){ cout<<*i<<endl; }
2. deque (Double-Ended Queue)
特点：从前面或后面快速的插入与删除，直接访问任何元素。
实现：双端队列。中控器（map，索引数组）+缓冲区（分段数组，实际存储体），像二维数组。
常用方法：
头文件：
#include <deque>创建和初始化（同vector）
deque<Type> deq;
头部/尾部插入和删除
deq.push_front(elem); //头部插入 deq.pop_front(); //头部删除 deq.push_back(elem); dqe.pop_back();
查询
dqe[i]; dqe.front(); //返回头部元素 dqe.back();
任意位置插入/删除（同vector）
迭代器（同vector）
3. list
特点：从任何地方快速插入与删除
实现：双向链表
常用方法：
头文件
#include <list>创建和初始化（同vector）
list<Type> li;
插入和删除
li.push_front(elem); li.pop_front(); li.push_back(elem); li.pop_back();
查询：使用迭代器
//遍历访问 for(auto i = li.begin(); i != li.end(); i++){ cout<<*i<<endl; } //搜索 list<int>::iterator int_itor=find(li.begin(),li.end(),3); cout <<*int_itor << endl;容器大小
任意位置插入（同vector）
代码块
任意位置删除（同vector）
迭代器（同vector）
li.begin(); li.end();
二、关联容器
特点：都是有序的，升序排列
1. set
特点：快速查找，不允许重复值。存储的是一组无重复的元素。如果要修改某一个元素值，必须先删除原有的元素，再插入新的元素。
实现：红黑树
常用方法：
头文件
#include <set>创建和初始化
set<Type> myset; set<Type, op> myset; //op为仿函数，排序规则，默认是 升序less<T>，降序为greater<T> //仿函数 struct cmp{ bool operator()(T &a, T &b){ return a < b; //降序 } }插入和删除
myset.empty(); //判断是否为空 myset.insert(elem); //插入elem myset.insert(pos, elem); //pos位置插入elem myset.erase(elem); //删除elem myset.erase(pos); //删除pos位置元素 myset.clear(); //清空集合
查询
myset.find(elem); //返回迭代器，=myset.end()时则找不到元素 myset.count(elem); //返回elem元素的数目
容器大小
myset.size(); myset.max_size(); //可容纳最大元素数量
迭代器
//顺序遍历 myset.begin(); myset.end(); //逆序遍历 myset.rbegin(); myset.rend();
2. multiset
特点：快速查找，允许重复值
实现：红黑树
常用方法：
- 头文件
#include <set>
3. map
特点：单重映射，基于关键字快速查找，不允许重复值
实现：红黑树，按Key排序
常用方法：
- 头文件
#include <map>
- 创建和初始化
map<KeyType, ValType> m; map<KetType, ValType, op> m; //op为排序规则，仿函数，默认是less<T>,升序
- 插入和删除
直接插入（修改式）
m[key] = vlaue; //不适用于multimap
用pair<>构造键值对，然后插入
m.insert(pair<KeyType, ValType>(key, value));
使用make_pair()函数构建键值对，然后插入
m.insert(make_pair(key, value));
使用value_type标志
m.insert(map<KeyType, ValType>::value_type(key, value));
- 查询
m[key]; //使用前需要保证key在m中，否则会自动插入key的值 m.find(key); //返回迭代器，找不到时返回m.end() m.count(key); //返回数量，找不到时返回值为0
使用m.begin()和m.end()迭代器遍历
for(auto i = m.begin(); i != m.end(); i++){
cout<<i->first<<" "<<i->second<<endl;
}容器大小
m.size(); m.max_size();
迭代器
m.begin(); m.end();
4. multimap
特点：一对多映射，基于关键字快速查找，允许重复值
实现：红黑树
常用方法：
5. C++11新特性
用hash实现map、multimap、set、multiset
- unordered_map
- unordered_multimap
- unordered_set
- unordered_multimset
三、容器适配器
1. stack栈
特点：先进后出
实现：deque
常用方法：
- 头文件
#include <stack>
创建
stack<Type> st;
插入和删除
st.push(elem); //elem插入到栈顶 st.pop(); //删除栈顶元素
查询
st.top(); //返回栈顶元素
容器大小
st.size();
判断是否为空
st.empty();
2. queue
特点：先进先出，只能在尾部插入，只能在头部弹出
实现：deque
常用方法：
- 头文件
#inclue <queue>
创建和初始化
queue<Type> que;
插入和删除
que.push(elem); //队列尾部插入元素 que.pop(); //弹出队列头部元素
查询
que.front(); //返回队列头的元素引用 que.back(); //返回队列尾的元素引用
容器大小
que.size();
判断是否为空
que.empty();
3. priority_queue
特点：优先级最大的先出
实现：vector，堆排序，大顶堆/小顶堆
常用方法：
- 头文件
#include <queue>
创建和初始化
priority_queue<int> pq； priority_queue<Type, container<Type>, op> pq; //container可以是C++中任意一种容器。op为排序规则，是仿函数。对基本类型，默认less<T>是大顶堆，也可以选greater<T> //仿函数 struct cmp{ bool operator() (Type &a, Type &b){ return a > b; //小顶堆 } }插入和删除
pq.push(elem); //插入元素elem，并调整堆 pq.pop(); //弹出堆顶（优先级最大）元素
查询
pq.top(); //返回堆顶元素索引
容器大小
pq.size();
判断优先队列是否为空
pq.empty();
查看9道真题和解析
