c++容器list、vector、map、set有什么区别和用法
这篇文章主要讲解了c++容器list、vector、map、set有什么区别和用法,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。
成都创新互联公司专业为企业提供武都网站建设、武都做网站、武都网站设计、武都网站制作等企业网站建设、网页设计与制作、武都企业网站模板建站服务,10年武都做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
c++容器list、vector、map、set区别
list
- 封装链表,以链表形式实现,不支持[]运算符。
- 对随机访问的速度很慢(需要遍历整个链表),插入数据很快(不需要拷贝和移动数据,只需改变指针的指向)。
- 新添加的元素,list可以任意加入。
vector
- 封装数组,使用连续内存存储,支持[]运算符。
- 对随机访问的速度很快,对头插元素速度很慢,尾插元素速度很快
- 新添加的元素,vector有一套算法。
map
- 采用平衡检索二叉树:红黑树
- 存储结构为键值对
set
- 采用平衡检索二叉树:红黑树
- set中不包含重复的数据
Hash_Map
- 采用hash算法加快查找过程,但需要更多内存存放hash桶元素,是一种采用空间换取时间的策略。
c++容器list、vector、map、set用法
vector
在内存中分配一块连续的存储空间进行存储,支持不指定vector大小的存储。即将元素置于一个动态数组中加以管理的容器。
vector对象的创建
vector<数据类型> vector容器名称 vectorvecInt; //一个存放int的vector容器。 vector vecFloat; //一个存放float的vector容器。 vector vecString; //一个存放string的vector容器。
vector常用操作
vector.size(); //返回容器中元素的个数 vector.empty(); //判断容器是否为空 vector.resize(num); //重新指定容器的长度为num vector.push_back(1); //在容器尾部加入一个元素 vector.pop_back(); //移除容器中最后一个元素 vector.clear(); //移除容器的所有数据 vector.erase(beg,end); //删除[beg,end)区间的数据,返回下一个数据的位置。 vector.erase(pos); //删除pos位置的数据,返回下一个数据的位置。 vector.insert(pos,elem); //在pos位置插入一个elem元素的拷贝,返回新数据的位置。 vector.insert(pos,n,elem); //在pos位置插入n个elem数据,无返回值。 vector.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据,无返回值 vector::iterator iter = find(vector.begin(),vector.end(),3);//查找元素3是否存在vector中。若存在返回元素,否则返回vector.end()。find()函数加上头文件**#include **
vector的正向遍历和反向遍历
//正向遍历 for(vector::iterator it=vecInt.begin(); it!=vecInt.end(); ++it) { int iItem = *it; cout << iItem; //或直接使用 cout << *it; } //反向遍历 for(vector ::reverse_iterator rit=vecInt.rbegin(); rit!=vecInt.rend(); ++rit) //注意,小括号内仍是++rit { int iItem = *rit; cout << iItem; //或直接使用cout << *rit; } //直接用vector[i]的方式访问第i个元素 for(int i = 0;i<5;i++) { cout << vector[i] << " " ; } //for_each进行遍历 for_each(vector.begin(),vector.end(),print);
支持随机访问,即支持[]运算符和vector.at()
vector.at(idx); //返回索引idx所指的数据,如果idx越界,抛出out_of_range异常。 vector[idx]; //返回索引idx所指的数据,越界时,运行直接报错
只能从尾部进行插入和删除,不能从头部进行插入和删除。中间进行插入和删除操作需要把插入位置后妈的元素后移或前移,效率低。
vector的内存管理与效率
当元素需要插入且容器的容量不足时会发生重新分配。
问题这会导致vector的原始内存分配和回收、对象的拷贝和析构和迭代器、指针和引用的失效。
问题产生的原因:vector容器分配的是一块连续的内存空间,每次容器的增长,并不是在原有连续的内存空间后再进行简单的叠加,而是重新申请一块更大的新内存(一般是当前大小的1.5~2倍的新内存区),并把现有容器中的元素逐个复制过去,同时销毁旧的内存。
问题解决方法
提前使用reserve()函数设定容器大小,在vector操作的末尾添加vector
list
list是一个双向链表容器,可高效地进行插入删除操作
list.push_back(elem); //在容器尾部加入一个元素 list.pop_back(); //删除容器中最后一个元素 list.push_front(elem); //在容器开头插入一个元素 list.pop_front(); //从容器开头移除第一个元素
list常用操作
list的大小size()之类的和插入删除操作以及遍历操作同vector
list.front(); //返回第一个元素。 list.back(); //返回最后一个元素。 list.begin(); //返回容器中第一个元素的迭代器。 list.end(); //返回容器中最后一个元素之后的迭代器。 list.reverse(); //反转链表,
不支持内部的随机访问,即不支持[]操作符和vector.at()
deque
deque在功能上合并vector和list
- deque是双端数组,vector是单端,所以这两个容器在操作上很多地方是一样的。添加删除操作和list一样,其他操作同上。
- 支持内部的随机访问,即不支持[]操作符和vector.at()
- 可在内部方便的进行插入和删除操作,两端都可进行push和pop
stack
stack堆栈容器,是一种“先进后出”的容器
stack.push(elem); //往栈头添加元素 stack.pop(); //从栈头移除第一个元素 stack.top(); //返回最后一个压入栈元素,即返回栈顶元素
queue
queue队列容器,是一种“先进先出”的容器
stack.push(elem); //往队尾添加元素 stack.pop(); //从队头移除第一个元素
其他操作同deque容器。
priority_queue
- priority_queue优先级队列,背后是堆的思想。
- 用来开发一些特殊的应用,可以对STL类库进行扩展
priority_queue> pq; priority_queue > pq;
最大值优先级队列、最小值优先级队列
priority_queuep1; //默认是 最大值优先级队列 大顶堆,队头元素最大 //priority_queue , less > p1; //相当于这样写 priority_queue , greater > p2; //最小值优先级队列
set和multiset容器
这两个容器属于关联式容器(元素的值与某个特定的键相关联),对应同一个头文件#include
- set是一个集合容器,其中所包含的元素是唯一的,集合中的元素按一定顺序排列,元素插入过程是按排序规则插入,所有不能指定插入位置。
- set采用红黑树变体的数据结构实现,红黑树属于平衡二叉树,在插入和删除操作上比vector快。
原因set容器本质是二叉树,不需要做内存拷贝和移动。set容器内所有元素都是以节点的方式来存储,其节点的结构和链表类似,如图所示。在插入时只需把节点的指针指向新的节点即可,删除类似把指向删除节点的指针指向其他节点即可。
set容器中每次insert后,以前保存的iterator不会失效。因为iterator相当于指向节点的指针,内存不变,指向内存的指针就不会变。
set不支持内部的随机访问,即不支持[]操作符和vector.at()。但是set中查找使用二分查找,即使数据元素增多,插入和搜索的速度也不会变即log2。
multiset与set的区别:set支持唯一键值,每个元素值只能出现一次;而multiset中同一值可以出现多次。
不可以直接修改set或multiset容器中的元素值,因为该类容器是自动排序的。如果希望修改一个元素值,必须先删除原有的元素,再插入新的元素。
基本操作
set> setIntA; //该容器是按升序方式排列元素。 set > setIntB; //该容器是按降序方式排列元素。 set 相当于 set >。
pair的使用
pair译为对组,可以将两个值视为一个单元。
pair
以下操作返回一个pair
set.find(elem); //查找elem元素,返回指向elem元素的迭代器。 set.count(elem); //返回容器中值为elem的元素个数。对set来说,要么是0,要么是1。对multiset来说,值可能大于1。 set.lower_bound(elem); //返回第一个>=elem元素的迭代器。 set.upper_bound(elem); // 返回第一个>elem元素的迭代器。 set.equal_range(elem); //返回容器中与elem相等的上下限的两个迭代器。上限是闭区间,下限是开区间,如[beg,end)。
map和multimap容器
这两个容器属于关联式容器,对应同一个头文件#include
- map是一个键值对序列,即(key,value)对,其中key是唯一的,集合中的元素按一定顺序排列,元素插入过程是按排序规则插入,所有不能指定插入位置。
- map采用红黑树变体平衡二叉树的数据结构实现,在插入和删除操作上比vector快。
- map可以直接存取key所对应的value,支持[]操作符,如map[key]=value。
- multimap与map的区别:map支持唯一键值,每个键只能出现一次;而multimap中相同键可以出现多次。multimap不支持[]操作符。
基本操作
插入元素四种方式,前三种返回值为pair
一、通过pair的方式插入对象 mapStu.insert( pair(3,"小张") ); 二、通过pair的方式插入对象 mapStu.inset(make_pair(-1, “校长-1”)); 三、通过value_type的方式插入对象 mapStu.insert( map ::value_type(1,"小李") ); 四、通过数组的方式插入值 mapStu[3] = “小刘"; map.begin(); //返回容器中第一个数据的迭代器。 map.end(); //返回容器中最后一个数据之后的迭代器。
迭代器遍历
//前向遍历和反向遍历同上 for (map::iterator it=mapA.begin(); it!=mapA.end(); ++it) { cout < first << " " << it->second << endl; } //数组方式遍历 for(int i = 1;i<=mapStu.size();++i) { cout << i << " " << mapStu[i] << endl; }
map的排序
map> mapA; //该容器是按键的升序方式排列元素。未指定函数对象,默认采用less 函数对象。 map > mapB; //该容器是按键的降序方式排列元素。
总结
deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。
vector与deque的比较:
vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置却是不固定的。
如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
deque支持头部的快速插入与快速移除,这是deque的优点。
list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。
map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。
看完上述内容,是不是对c++容器list、vector、map、set有什么区别和用法有进一步的了解,如果还想学习更多内容,欢迎关注创新互联行业资讯频道。
文章标题:c++容器list、vector、map、set有什么区别和用法
分享路径:http://azwzsj.com/article/gghpsp.html