c++容器list、vector、map、set区别与用法详解

c++容器list、vector、map、set区别

list

  • 封装链表,以链表形式实现,不支持[]运算符。
  • 对随机访问的速度很慢(需要遍历整个链表),插入数据很快(不需要拷贝和移动数据,只需改变指针的指向)。
  • 新添加的元素,list可以任意加入。

vector

  • 封装数组,使用连续内存存储,支持[]运算符。
  • 对随机访问的速度很快,对头插元素速度很慢,尾插元素速度很快
  • 新添加的元素,vector有一套算法。

map

  • 采用平衡检索二叉树:红黑树
  • 存储结构为键值对<key,value>

set

  • 采用平衡检索二叉树:红黑树
  • set中不包含重复的数据

Hash_Map

  • 采用hash算法加快查找过程,但需要更多内存存放hash桶元素,是一种采用空间换取时间的策略。

c++容器list、vector、map、set用法

vector

在内存中分配一块连续的存储空间进行存储,支持不指定vector大小的存储。即将元素置于一个动态数组中加以管理的容器。

vector对象的创建

vector<数据类型> vector容器名称
vector<int> vecInt;     //一个存放int的vector容器。
vector<float> vecFloat;     //一个存放float的vector容器。
vector<string> 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<int>::iterator iter = find(vector.begin(),vector.end(),3);//查找元素3是否存在vector中。若存在返回元素,否则返回vector.end()。find()函数加上头文件**#include<algorithm>**

vector的正向遍历和反向遍历

//正向遍历
for(vector<int>::iterator it=vecInt.begin(); it!=vecInt.end(); ++it)
{
   int iItem = *it;
   cout << iItem;  //或直接使用 cout << *it;
}
//反向遍历
for(vector<int>::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<int>().swap(v)来修正过剩的空间或内存。

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<int, deque<int>>   pq;
priority_queue<int, vector<int>>  pq;

最大值优先级队列、最小值优先级队列

priority_queue<int> p1; //默认是 最大值优先级队列 大顶堆,队头元素最大
//priority_queue<int, vector<int>, less<int> > p1; //相当于这样写
priority_queue<int, vector<int>, greater<int>> p2; //最小值优先级队列

set和multiset容器

这两个容器属于关联式容器(元素的值与某个特定的键相关联),对应同一个头文件#include<set>

  • set是一个集合容器,其中所包含的元素是唯一的,集合中的元素按一定顺序排列,元素插入过程是按排序规则插入,所有不能指定插入位置。
  • set采用红黑树变体的数据结构实现,红黑树属于平衡二叉树,在插入和删除操作上比vector快。

原因set容器本质是二叉树,不需要做内存拷贝和移动。set容器内所有元素都是以节点的方式来存储,其节点的结构和链表类似,如图所示。在插入时只需把节点的指针指向新的节点即可,删除类似把指向删除节点的指针指向其他节点即可。

set容器中每次insert后,以前保存的iterator不会失效。因为iterator相当于指向节点的指针,内存不变,指向内存的指针就不会变。

set不支持内部的随机访问,即不支持[]操作符和vector.at()。但是set中查找使用二分查找,即使数据元素增多,插入和搜索的速度也不会变即log2。

multiset与set的区别:set支持唯一键值,每个元素值只能出现一次;而multiset中同一值可以出现多次。
不可以直接修改set或multiset容器中的元素值,因为该类容器是自动排序的。如果希望修改一个元素值,必须先删除原有的元素,再插入新的元素。

基本操作

set<int,less<int> > setIntA; //该容器是按升序方式排列元素。
set<int,greater<int>> setIntB;  //该容器是按降序方式排列元素。
set<int> 相当于 set<int,less<int>>。

pair的使用

pair译为对组,可以将两个值视为一个单元。
pair<T1,T2>存放的两个值的类型,可以不一样,如T1为int,T2为float。T1,T2也可以是自定义类型。

以下操作返回一个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>,查找的时间复杂度为logn

  • map是一个键值对序列,即(key,value)对,其中key是唯一的,集合中的元素按一定顺序排列,元素插入过程是按排序规则插入,所有不能指定插入位置。
  • map采用红黑树变体平衡二叉树的数据结构实现,在插入和删除操作上比vector快。
  • map可以直接存取key所对应的value,支持[]操作符,如map[key]=value。
  • multimap与map的区别:map支持唯一键值,每个键只能出现一次;而multimap中相同键可以出现多次。multimap不支持[]操作符。

基本操作

插入元素四种方式,前三种返回值为pair<iterator,bool>。其他操作同set容器。

一、通过pair的方式插入对象
mapStu.insert( pair<int,string>(3,"小张") );
二、通过pair的方式插入对象
mapStu.inset(make_pair(-1, “校长-1”));
三、通过value_type的方式插入对象
mapStu.insert( map<int,string>::value_type(1,"小李") );
四、通过数组的方式插入值
mapStu[3] = “小刘";
map.begin(); //返回容器中第一个数据的迭代器。
map.end(); //返回容器中最后一个数据之后的迭代器。

迭代器遍历

//前向遍历和反向遍历同上
for (map<int,string>::iterator it=mapA.begin(); it!=mapA.end(); ++it)
{
  cout <<it->first << " " << it->second << endl;
}
//数组方式遍历
for(int i = 1;i<=mapStu.size();++i)
{
   cout << i << " " << mapStu[i] << endl;
}

map的排序

map<T1,T2,less<T1> > mapA; //该容器是按键的升序方式排列元素。未指定函数对象,默认采用less<T1>函数对象。
map<T1,T2,greater<T1>> mapB;  //该容器是按键的降序方式排列元素。

总结

deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。

vector与deque的比较:

vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置却是不固定的。
如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
deque支持头部的快速插入与快速移除,这是deque的优点。
list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。
map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。

参考
《传智播客c++基础和进阶课堂讲义》
《后台开发 核心技术与应用实践》---第三章

到此这篇关于c++容器list、vector、map、set区别与用法详解的文章就介绍到这了,更多相关c++ list、vector、map、set内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • c++ vector 常用函数示例解析

    c++ vector 常用函数 Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike ar

  • c++中为什么不提倡使用vector示例详解

    vector< bool> 并不是一个STL容器,不是一个STL容器,不是一个STL容器! 首先vector< bool> 并不是一个通常意义上的vector容器,这个源自于历史遗留问题. 早在C++98的时候,就有vector< bool>这个类型了,但是因为当时为了考虑到节省空间的想法,所以vector< bool>里面不是一个Byte一个Byte储存的,它是一个bit一个bit储存的! 因为C++没有直接去给一个bit来操作,所以用operator[]

  • C++实现动态顺序表(vector)

    vector是连续存储结构,支持随机的高效的随机和在尾部进行插入.删除操作,其它位置的插入.删除操作相对来说效率较低. vector相当于一个数组,但它的数组空间大小需要写一程序来实现. 它的内存分配原理大概可分为下面几步: 1)首先分配一块内存空间进行存储: 2)当所需存储的数据超过分配的空间时,再重新分配一块空间: 3)将旧元素复制到新空间: 4)释放旧空间. 实现代码如下: vector.h #pragma once #include<stdio.h> #include<asser

  • C++ 中Vector常用基本操作

    标准库vector类型是C++中使用较多的一种类模板,vector类型相当于一种动态的容器,在vector中主要有一些基本的操作,下面通过本文给大家介绍,具体内容如下所示: (1)头文件#include<vector>. (2)创建vector对象,vector<int> vec; (3)尾部插入数字:vec.push_back(a); (4)使用下标访问元素,cout<<vec[0]<<endl;记住下标是从0开始的. (5)使用迭代器访问元素. vect

  • 通过代码实例解析c++ vector常用方法

    1. c++ vector 每个元素加上一个特定值 (c++ vector add a constant value for each element) https://stackoverflow.com/questions/4461446/stl-way-to-add-a-constant-value-to-a-stdvector vector<int> x = {0, 30, 80, 100, 120, 150, 190, 220, 250}; //transform可以将函数应用到序列的

  • C++中stack、queue、vector的用法详解

    一.栈(stack) 引入头文件 #include<stack> 常用的方法 empty() 堆栈为空则返回真 pop() 移除栈顶元素 push() 在栈顶增加元素 size() 返回栈中元素数目 top() 返回栈顶元素 3.实例代码 #include<iostream> #include<stack> using namespace std; int main(){ //创建栈 s stack<int> s; //将元素压入栈 for(int i=0;

  • C++ vector使用的一些注意事项

    1. 初始化 c++ 11以后新增了大括号{}的初始化方式,需要注意与()的区别,如: std::vector<int> vecTest1(5);         //初始化5个元素,每个都是0 std::vector<int> vecTest2{ 5 };       //初始化1个元素,值是5 2.  添加元素:push_back 通过push_back添加新的元素进入vector后,vector的内存有时候会发生变化,这取决于size和capacity大小,当然这些都是系统来

  • c++容器list、vector、map、set区别与用法详解

    c++容器list.vector.map.set区别 list 封装链表,以链表形式实现,不支持[]运算符. 对随机访问的速度很慢(需要遍历整个链表),插入数据很快(不需要拷贝和移动数据,只需改变指针的指向). 新添加的元素,list可以任意加入. vector 封装数组,使用连续内存存储,支持[]运算符. 对随机访问的速度很快,对头插元素速度很慢,尾插元素速度很快 新添加的元素,vector有一套算法. map 采用平衡检索二叉树:红黑树 存储结构为键值对<key,value> set 采用

  • JavaScript中的普通函数和箭头函数的区别和用法详解

    最近被问到了一个问题: javaScript 中的箭头函数 ( => ) 和普通函数 ( function ) 有什么区别? 我当时想的就是:这个问题很简单啊~(flag),然后做出了错误的回答-- 箭头函数中的 this 和调用时的上下文无关,而是取决于定义时的上下文 这并不是很正确的答案--虽然也不是完全错误 箭头函数中的 this 首先说我的回答中没有错误的部分:箭头函数中的 this 确实和调用时的上下文无关 function make () { return ()=>{ consol

  • Pyecharts 动态地图 geo()和map()的安装与用法详解

    把一些地域性比较明显的数据显示在一张地图上,远比给别人一个 Excel 文件好得多. Matplotlib 中也有画地图的函数,但是是静态图,因此这里主要讲 Pyecharts 模块中的画图功能. 安装Pyecharts 方法一:pip install ... 方法二:conda install -c anaconda pyecharts 方法三:下载模块--安装 https://pypi.org/project/pyecharts/0.1.9.4/#files下载模块: 将模块放进 xx 路径

  • Linux系统关机命令之间的区别及用法详解

    Linux系统关机命令有哪些呢?良许教程网为您解答!熟悉linux的朋友应该知道我们在linux系统中常用到的关机命令有:shutdown.halt.poweroff.init:重启命令有:reboot.下面本文就主要介绍一些常用的关机命令以及各种关机命令之间的区别和具体用法. 以下是比较常用的一些关机命令 1.halt立刻关机 2.poweroff 立刻关机 3.shutdown -h now立刻关机(root用户使用) 4.shutdown -h 10 10分钟后自动关机 注:如果是通过sh

  • Java map.getOrDefault()方法的用法详解

    Map.getOrDefault(Object key, V defaultValue)方法的作用是: 当Map集合中有这个key时,就使用这个key值: 如果没有就使用默认值defaultValue. 代码示例如下: HashMap<String, String> map = new HashMap<>(); map.put("name", "cookie"); map.put("age", "18"

  • Python中几种属性访问的区别与用法详解

    起步 在Python中,对于一个对象的属性访问,我们一般采用的是点(.)属性运算符进行操作.例如,有一个类实例对象foo,它有一个name属性,那便可以使用foo.name对此属性进行访问.一般而言,点(.)属性运算符比较直观,也是我们经常碰到的一种属性访问方式. python的提供一系列和属性访问有关的特殊方法: __get__ , __getattr__ , __getattribute__ , __getitem__ .本文阐述它们的区别和用法. 属性的访问机制 一般情况下,属性访问的默认

  • Javascript中Math.max和Math.max.apply的区别和用法详解

    最近在做一个小案例的时候遇到了Math.max.apply这么一个用法,之前很少遇到过感觉挺有趣的,就记录一下. 1Math.max 语法: Math.max(n1,n2,n3,...,nX) 返回值:max() 方法可返回指定的参数中带有较大的值的那个数 var a = Math.max(1,2,3,4); console.log(a); //4 但是如果数据是放在一个数组里面,此时就不能这样调用了.这时就用到apply方法 2Math.max.apply apply() 方法调用一个函数.简

  • Asp.Net Core中服务的生命周期选项区别与用法详解

    前言 最近在做一个小的Demo中,在一个界面上两次调用视图组件,并且在视图组件中都调用了数据库查询,结果发现,一直报错,将两个视图组件的调用分离,单独进行,却又是正常的,寻找一番,发现是配置依赖注入服务时,对于服务的生命周期没有配置得当导致,特此做一次实验来认识三者之间(甚至是四者之间的用法及区别). 本文demo地址(具体见WebApi控制器中):https://gitee.com/530521314/koInstance.git (本地下载)  一.服务的生命周期 在Asp.Net Core

  • C语言 map函数的基础用法详解

    目录 map map具体操作 总结 map 有N个学生的姓名name和学号ID,要求给你一个学生的name求查找他的ID. 简单做法是定义 string name [ N ] 和 int ID[ N ] 存储信息,然后在name [ ] 中查找这个学生,找到后输出他的ID.但是这样的缺点是需要查找所有的name [ N ],时间复杂度是O( N ),效率低下. 利用 STL 中 map容器 可以快速实现查找,复杂度是O( log 2 N ). map是关联容器,它实现从键(key)到值(valu

  • Shell编程中while与for的区别及用法详解

    在shell编程中经常用到循环,常用的循环有for和while循环两种.while循环默认以行读取文件,而for循环以空格读取文件切分文件,本篇就结合现网的一些使用示例说说二者的用法和区别. 一.常用语法 1.for循环 for循环常用的语法结构有如下几种: for 变量 in seq字符串 for 变量 in `command` " " for 变量 in "$@"或"$*" for((赋值:条件:运算语句)) 2.while循环 while循

随机推荐