深入解析C++ STL中的常用容器
字体：[ ] 类型：转载 时间：
这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点。STL中的常用容器包括：顺序性容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）
STL是C/C++开发中一个非常重要的模板，而其中定义的各种容器也是非常方便我们大家使用。下面，我们就浅谈某些常用的容器。这里我们不涉及容器的基本操作之类，只是要讨论一下各个容器其各自的特点。STL中的常用容器包括：顺序性容器（vector、deque、list）、关联容器（map、set）、容器适配器（queue、stac）。
1、顺序性容器
（1）vectorvector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。vector有多个构造函数，默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的，即内存空间增长是按照20,21,22,23.....增长的，在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露，现在经常用的方法是swap函数来进行解决：
代码如下:vector&int& V;V.push_back(1); V.push_back(2);V.push_back(1); V.push_back(2);vector&int&().swap(V); //或者 V.swap(vector&int&());利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象的内存为V对象的内存。交换以后，临时对象消失，释放内存。
（2）dequedeque和vector类似，支持快速随机访问。二者最大的区别在于，vector只能在末端插入数据，而deque支持双端插入数据。deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。
（3）listlist是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访问，这使list的随机存储变得非常低效，因此list没有提供[]操作符的重载。但list可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。
（4）在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：1) 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector2) 如果你需要大量的插入和删除，而不关心随即存取，则应使用list3) 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque
2、关联容器
（1）mapmap是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功能。map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。这是map的模板：template & class Key, class T, class Compare= less&Key&, class Allocator=allocator& pair&const Key,T& & &从模板中我们可以看出，再构造map时，是按照一定的顺序进行的。map的插入和删除效率比其他序列的容器高，因为对关联容器来说，不需要做内存的拷贝和移动，只是指针的移动。由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑色），所以map的其中的一个缺点就是比较占用内存空间。
（2）setset也是一种关联性容器，它同map一样，底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。set中的元素都是唯一的，而且默认情况下会对元素进行升序排列。所以在set中，不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。set模板原型：template &class Key, class Compare=class&Key&, class Alloc=STL_DEFAULT_ALLOCATOR(Key) &set支持集合的交(set_intersection)、差(set_difference)、并(set_union)及对称差(set_symmetric_difference) 等一些集合上的操作。
3、容器适配器
（1）queuequeue是一个队列，实现先进先出功能，queue不是标准的STL容器，却以标准的STL容器为基础。queue是在deque的基础上封装的。之所以选择deque而不选择vector是因为deque在删除元素的时候释放空间，同时在重新申请空间的时候无需拷贝所有元素。其模板为：template & TYPENAME _Sequence="deque&_TP" typeneam _Tp,& &
（2）stackstack是实现先进后出的功能，和queue一样，也是内部封装了deque，这也是为啥称为容器适配器的原因吧（纯属猜测）。自己不直接维护被控序列的模板类，而是它存储的容器对象来为它实现所有的功能。stack的源代码原理和实现方式均跟queue相同。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具随笔- 393&
评论- 155&
&&&&&&&&&&&&&
1.vector：
vector&int&vector&int& v(10);//定义大小为10的int型向量容器。vector&int& v(10,3);//定义大小为10，每个元素为3。
v.push_back(2);//尾部添加元素2.
v.pop_back();//尾部删除一个元素.
v[0]=2;v[1]=3;//下标访问。
vector&int&:://迭代器访问for(it=v.begin();it!=v.end();it++){
cout&&*it&&" ";}
//元素插入，插入位置必须是迭代器位置v.insert(v.begin(),8);//最前面插入v.insert(v.begin()+2,8);v.insert(v.end(),8);//末尾追加
//元素删除v.erase(v.begin()+2);//删除第2+1个元素v.erase(v.begin()+1,v.begin()+5);//删除迭代器第一到第五区间的所有元素v.clear();//删除所有元素
reverse(v.begin(),v.end());//反向排列向量所有元素（可以反向排列某段迭代器区间元素）
sort(v.begin(),v.end());//sort排序（默认升序排列）
//设计排序比较函数bool comp(const int& a,const int& b){
return a&b;//降序排列}sort(v.begin(),v.end(),comp);
v.size();//返回向量大小,即元素个数v.empty();//判空，空时返回1，不空时返回0。
//堆栈容器
stack&int&s.push(1);//入栈s.pop();//出栈s.top();//返回栈顶元素s.size();//返回元素个数s.empty();//判空
//队列容器//只能从队尾插入元素，队首删除元素queue&int&q.push(1);//入队q.pop();//出队q.front();//返回队首元素q.back();//返回队尾元素q.size();//返回元素个数q.empty();//判空
4.priority_queue：
//优先队列容器//只能从队尾插入元素，队首删除元素//队列中最大的元素总是位于队首（默认从大到小排序，自己可以自定义比较函数来修改）
priority_queue&int&pq.push(1);//入队pq.pop();//出队pq.top();//返回队首元素pq.size();//返回元素个数pq.empty();//判空
//自定义比较函数元素为结构体：struct info{
bool operator & (const info &a) const
return score&a.//从小到大（注意这次的符号）
元素非结构体：struct mycomp{
bool operator () (const int &a,const int &b) const
return a&b;//从小到大（注意这次的符号）
}};priority_queue&int,vector&int&,mycomp&//显示说明其内部结构是vector.（注意：当有自定义比较函数时，必须显示说明其内部结构是vector！）
创建deque&int&deque&int& d(10);//容量为10deque&int& d(10,8.5);//10个并初始化为8.5
插入：push_back()尾部插入，扩张队列push_front()头部插入，不扩张队列，往后挤，把尾部的元素挤出去了以上两个参数是一个元素对象insert()中间某位置插入元素，不扩张队列，仍是挤出尾部的元素参数为两个：迭代器位置+元素对象eg：d.insert(d.begin()+1,88);//即插入到第二个位置，后面的往后顺延，最后一个丢失
遍历：d[i]//数组方式
deque&int&::for(it=d.begin();it!=d.end();it++){ cout&&*it&&" ";}//前向迭代器方式
deque&int&::reverse_for(rit=d.rbegin();rit!=d.rend();rit++){ cout&&*rit&&" ";}//反向迭代器方式
删除：首部：d.pop_front();尾部：d.pop_back();中间：d.erase(d.begin()+1);清空：d.clear();
#include &set&#include &algorithm&
//不会重复插入相同键值的元素//采用红黑树的平衡二叉检索树结构，中序遍历
s.insert(3);//默认从小到大
set&int&::for(it=s.begin();it!=s.end();it++){
cout&&*it&&"　"；}
//反向遍历set&int&::reverse_//反向迭代器for(rit=s.rbegin();rit!=s.rend();rit++){
cout&&*rit&&" ";}
//元素删除，删除对象可以是某个迭代器位置上的元素、等于某键值的元素、一个区间上的元素s.erase(s.begin()+1);s.erase(6);s.erase(s.begin(),s.begin()+4);s.clear();
s.find(6);//查找键值6，查到了则返回其迭代器位置，否则返回最后一个元素后面的位置，即end()set&int&::it=s.find(6);if(it!=s.end())
cout&&*it&&
//自定义比较函数
默认从小到大存储
//非结构体元素struct comp{
bool operator () (const int& a,const int& b) const
return a&b;//从大到小
}}set&int,comp&//创建set&int,comp&::其他操作一样
//结构体元素struct info{
bool operator & (const info &a) const
return score&a.//从大到小
}}set&info&//创建set&info&::
7.multiset：
#include &set&#include &algorithm&
//允许重复的元素键值插入
//在插入，删除，查找方面与&set&有区别
multiset&string&ms.insert("abc");multiset&string&::
//erase()可以删除某个迭代器位置的元素，某段区间的元素，键值等于某个值的所有重复元素（并返回删除元素个数）。ms.erase("123");ms.clear();
//find()，如果查到，返回该元素第一次出现的迭代器位置，否则返回end()it=ms.find("123");
#include &map&#include &algorithm&
//不会重复插入相同键值的元素//采用红黑树的平衡二叉检索树结构，中序遍历//比较函数只对键值进行比较//和set使用大都相同
map&string,float&m["jack"]=98.5;//插入元素m.insert(pair&string,float&("lvhuan",18.5));
map&string,float&::for(it=m.begin();it!=m.end();it++){
cout&&(*it).first&&":"&&(*it).second&&//输出键值与映照数据}
//可以删除某个迭代器位置元素、等于某键值的元素、某迭代器区间的所有元素m.erase(4);m.clear();
//反向遍历map&string,float&::reverse_for(it=m.rbegin();it!=m.rend();it++){
cout&&(*it).first&&":"&&(*it).second&&//反向输出键值与映照数据}
//find()返回键值所处迭代器位置或end()位置
//自定义比较函数（默认从小到大）非结构体元素struct comp{
bool operator () (const int &a,const int &b) const
return a&b;//从大到小
}}map&int,char,comp&map&int,char,comp&::
结构体元素struct info{
bool operator & (const info &a) const
return score&a.//从大到小
}}map&info,int&//创建map&info,int&::for(it=m.begin();it!=m.end();it++){
cout&&(*it).second&&":";
cout&&((*it).first).name&&" "&&((*it).first).score&&}
9.multimap：
#include &map&#include &algorithm&
//允许重复插入相同键值的元素
multimap&string,float&m["jack"]=98.5;//插入元素m.insert(pair&string,float&("lvhuan",18.5));
multimap&string,float&::for(it=m.begin();it!=m.end();it++){
cout&&(*it).first&&":"&&(*it).second&&//输出键值与映照数据}
//erase()可以删除某个迭代器位置的元素，某段区间的元素，键值等于某个值的所有重复元素（并返回删除元素个数），还有清空clear()
//find()，如果查到，返回该元素第一次出现的迭代器位置，否则返回end()it=m.find("123");
//双向循环链表容器
//迭代器只能使用&++&或&--&，不能使用&+n&或&-n&。
创建：list&int&list&int& l(10);//容量10
插入，都会自动扩张：尾部：push_back()首部：push_front()中间：只能插到迭代器位置处：l.insert(it,20);//元素对象为20
遍历：list&int&::for(it=l.begin();it!=l.end();it++){ cout&&*it&&" ";}//前向迭代器方式
list&int&::reverse_for(rit=l.rbegin();rit!=l.rend();rit++){ cout&&*rit&&" ";}//反向迭代器方式
删除：remove()删除一个元素值，值相同的元素都会被删除。l.remove(1);//删除值为1的所有元素
l.pop_front();//删除首部元素l.pop_back();//删除链表尾部元素
list&int&::for(it=l.begin();it!=l.end();it++){ cout&&*it&&" ";}it=l.begin();it++;it++;l.erase(it);//删除迭代器位置元素
l.clear();//清空
查找：find()，找到则返回迭代器位置，否则返回end().eg:it=find(l.begin(),l.end(),5);//查找这个区间上的值为5的元素的位置
升序排序：l.sort();
删除连续重复元素,只保留一个：l.unique();//注意是删除连续重复，不是单单重复
11.bitset：
//bit位元素的序列容器，每个元素只占一个bit位，取值0或1.
/*bitset类方法列表：b.any()
b中是否存在置为1的二进制位？b.none()
b中不存在置为1的二进制位吗？b.count()
b中置为1的二进制位的个数b.size()
b中二进制位的个数b[pos]
访问b中在pos处的二进制位b.test(pos) b中在pos处的二进制位是否为1？b.set()
把b中所有二进制位都置为1b.set(pos)
把b中在pos处的二进制位置为1b.reset()
把b中所有二进制位都置为0b.reset(pos)
把pos处的二进制位置为0b.flip()
把b中所有二进制位取反b.flip(pos) 把pos处的二进制位取反b.to_ulong()
用b中同样的二进制位返回一个unsigned long值os&&b
把b中的位集输出到os流*/
//创建bitset&100000&//创建时必须指定容器大小，且不能再修改大小。默认初始值为0.
//元素赋值b[6]=1;//下标法，最低位为第0位b.set();//全部置1b.set(6);//将指定位置1b.reset();//全部置0b.reset(6);//指定位置0
//输出元素cout&&b[i];//下标法输出，可以借用b.size()来控制个大规模输出cout&&b;//注意输出的可是二进制形式哦（01串）
&posted on
阅读(...) 评论()【C++研发面试笔记】21. 常用算法-STL中常用算法函数
1、for_each(容器起始地址，容器结束地址，要执行的函数)
指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。
2、查找find
InputIterator find (InputIterator first, InputIterator last, const T& val);
前闭后合的区间 begin，end中，查找value如果查找到了就返回第一个符合条件的元素，否则返回end指针
3、数值运算（&numeric&）
T accumulate (InputIterator first, InputIterator last, T init)
计算一个范围内的累积和
OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result)
计算相邻差（y0=x0, y1=x1-x2, y2=x2-x1…）
T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init)
计算内积（y=init+x0*x0+x1*x1+…）
4、判断是否相等
bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2) 找到所示子序列的位置
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
cmp函数的两种使用方式
bool myfunction (int i,int j) { return (i&j); }
struct myclass {
bool operator() (int i,int j) { return (i&j);}
std::sort (myvector.begin()+4, myvector.end(), myfunction);
std::sort (myvector.begin(), myvector.end(), myobject);
template &class T& void swap ( T& a, T& b )
void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
void reverse (BidirectionalIterator first, BidirectionalIterator last)
11、统计元素值为val的数目
difference_type count (InputIterator first, InputIterator last, const T& val)
12、最值比较
const T& min (const T& a, const T& b)
const T& max (const T& a, const T& b)
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：200807次
积分：2587
积分：2587
排名：第14779名
原创：88篇
评论：148条
阅读：6062
阅读：4240
文章：22篇
阅读：17206
文章：10篇
阅读：50691
(9)(5)(8)(22)(5)(6)(2)(7)(2)(2)(5)(14)(1)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'C++___STL库中Set的一些常用的内置函数_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
C++___STL库中Set的一些常用的内置函数
你可能喜欢君，已阅读到文档的结尾了呢~~
STL-ACM常用函数
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
STL-ACM常用函数
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口}