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内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！