首页 / C++ / C++STL几种常用容器简要归纳
C++STL几种常用容器简要归纳
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C++STL几种常用容器简要归纳，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5067字，纯文字阅读大概需要8分钟。
内容图文
文章目录
本文参考李煜东《算法竞赛进阶指南》，笔者作归纳总结。
本文将简要介绍STL中vector,queue,priority_queue,deque,set,multiset,map,bitset八种容器及其操作方法。
vector
使用此容器需在程序前加上头文件#include< vector >。
vector可理解为变长数组，基于倍增思想。当以已申请vector长度为m时，若实际长度n=m,则申请长度为2m的数组，将内容转移至新地址上，并释放旧空间；删除元素时，若n<=m/4,则释放一半空间。
vector容器能像数组一样随机访问第i个数a[i]，但不支持随机插入，其将元素插入尾部时的摊还代价为3。
#include<vector> //头文件
vector<int> a;
vector<int> b[100];
struct rec{···};
vector<rec> c; //各种声明
vector<int>::iterator it; //vector的迭代器，与指针类似
a.size() //返回实际长度（元素个数），O(1)复杂度
a.empty() //容器为空返回1，否则返回0，O(1)复杂度
a.clear() //把vector清空
a.begin() //返回指向第一个元素的迭代器，*a.begin()与a[0]作用相同
a.end() //越界访问，指向vector尾部，指向第n个元素再往后的边界
a.front() //返回第一个元素的值，等价于*a.begin和a[0]
a.back() //返回最后一个元素的值，等价于*--a.begin()和a[size()-1]
a.push_back(x) //把元素x插入vector尾部
a.pop_back() //删除vector中最后一个元素
迭代器使用与指针类似,可如下遍历整个容器
for ( vector<int>::iterator it=a.begin() ; it!=a.end() ; it++ )
queue
循环队列queue需使用头文件< queue >
queue<int> q;
struct rec{···};queue<rec> q; //声明
q.push(x); //从队尾使元素x入队，O(1)
q.pop(x); //使队首元素出队，O(1)
int x=q.front(); //询问队首元素的值，O(1)
int y=q.back(); //询问队尾元素的值，O(1)
priority_queue
优先队列priority_queue可理解为一个大根二叉堆，必须定义“小于号”，而int，string本身就能比较。同样需要头文件< queue >。
其声明与queue相似。
priority_queue<int> q;
priority_queue<pair<int,int>> q;
q.push(x); //插入 O(log n)
q.pop(); //删除堆顶元素 O(log n)
q.top(); //查询堆顶元素 O(1)
可通过插入元素的相反数取出时再取反，或重载“小于号”的方式实现小根堆，通过懒惰删除法实现随机删除操作。
deque
双端队列，是一个支持在两端高效插入或删除元素的连续线性存储空间，可像数组一样随机访问，使用前加头文件< deque >。
q.begin()/q.end() //头/尾迭代器，与vector类似
q.front()/q.back() //头/尾元素，与queue类似
q.push_back(x)/q.push_front(x) //从队尾/队头入队
q.pop_back(x)/q.pop_front(x) //从队尾/队头出队
q.clear() //清空队列
clear复杂度为O(n),其余为O(1)。
set/multiset
两容器相似，但set为有序集合，元素不能重复，multiset为有序多重集合，可包含若干相等的元素，内部通过红黑树实现，支持的函数基本相同，同样必须定义“小于号”运算符，头文件为< set >。
其迭代器不支持随机访问，支持星号(*)结束引用，仅支持 ++ 、-- 两个与算术有关的操作。迭代器it++,则指向从小到大排序的结果中排在it下一名的元素，两操作时间复杂度均为O(log n)。
q.size()
q.empty()
q.clear()
q.begin()/q.end() //作用与上文几种容器类似
q.insert(x) //将元素x插入集合中，O(log n)
q.find(x) //查找等于x的元素，返回其迭代器，无则返回q.end()，O(log n)
q.lower_bound(x) //查找>=x的元素中最小的一个，返回指向该元素的迭代器
q.upper_bound(x) //查找>x的元素中最小的一个，返回指向该元素的迭代器
q.erase(it) //删除迭代器it指向的元素，O(log n)
q.erase(x) //删除所有等于x的元素，复杂度为O(k+log n),k为被删除的元素个数
q.count(x) //返回等于x的元素个数，O(k+log n)，k为元素x的个数
若想从multiset中删除之多一个等于x的元素，可执行
if((it=q.find(x))!=q.end())
q.erase(it);
map
map容器是一个键值对key-value的映射。内部为一棵以key为关键码的红黑树，key和value可以是任意类型，其中key必须定义“小于号”运算符，声明方法为
map<key_type,value_type> name;
例如
map<long long,bool> vis;
map<string,int> hash;
q.size()
q.empty()
q.clear()
q.begin()/q.end() //作用与上文几种容器类似
q.insert(x) //插入，参数为pair<key_type,value_type>
q.erase(it) //删除，参数可以是pair或迭代器
q.find(x) //查找key为x的二元组，返回其迭代器，无则返回q.end()，O(log n)
q[key] //可得到key对应的value，也可对key进行赋值，改变对应的value
//若查找的key不存在，则会新建一个二元组(key,zero)。
bitset
bitset可看作一个多位二进制数，每8位占用1个字节，相当于采用了状态压缩的二进制数组，并支持基本的位运算。一般以32位整数的运算次数为基准估算运行时间，n位bitset执行一次的位运算复杂度可视为n/32，效率较高。头文件。
同样具有~,&,|,^,<<,>>操作符，==，!=可比较二进制数是否相等
bitset<10000> q; //声明一个10000位的二进制数
q[k] //表示q的第k位，可取值，赋值，最低位为q[0]
q.count() //返回有多少位1
q.none() //所有位都为0则返回true,至少1位为1则返回false
q.any() //所有位都为0则返回false,至少1位为1则返回true,与函数none相反
q.set() //把所有位变为1
q.set(k,v) //把第k位变为v，即q[k]=v
q.reset() //把所有位变为0
q.reset(k) //把第k位变为0，即q[k]=0
q.flip() //把所有位取反，即s=~s
q.flip(k) //把第k位取反，即q[k]^=1
此上所有容器均可视作一个前闭后开的结构。
内容总结
以上是互联网集市为您收集整理的C++STL几种常用容器简要归纳全部内容，希望文章能够帮你解决C++STL几种常用容器简要归纳所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。