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