C++

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

2020-05-21  本文已影响0人  潘雪雯

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

  1. 封装链表，以链表形式实现，不支持[]运算符。
  2. 对随机访问的速度很慢(需要遍历整个链表)，插入数据很快(不需要拷贝和移动数据，只需改变指针的指向)。
  3. 新添加的元素，list可以任意加入。
  1. 封装数组，使用连续内存存储，支持[]运算符。
  2. 对随机访问的速度很快，对头插元素速度很慢，尾插元素速度很快
  3. 新添加的元素，vector有一套算法。
  1. 采用平衡检索二叉树:红黑树
  2. 存储结构为键值对<key,value>
  1. 采用平衡检索二叉树:红黑树
  2. set中不包含重复的数据
  1. 采用hash算法加快查找过程，但需要更多内存存放hash桶元素，是一种采用空间换取时间的策略。

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

vector

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

vector<数据类型> vector容器名称
vector<int> vecInt;         //一个存放int的vector容器。
vector<float> vecFloat;         //一个存放float的vector容器。
vector<string> vecString;       //一个存放string的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>**

//正向遍历
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(idx);     //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
vector[idx];    //返回索引idx所指的数据，越界时，运行直接报错

list

list.push_back(elem);      //在容器尾部加入一个元素
list.pop_back();                  //删除容器中最后一个元素
list.push_front(elem);         //在容器开头插入一个元素
list.pop_front();                  //从容器开头移除第一个元素

list.front();                        //返回第一个元素。
list.back();                       //返回最后一个元素。
list.begin();                     //返回容器中第一个元素的迭代器。
list.end();                        //返回容器中最后一个元素之后的迭代器。
list.reverse();                 //反转链表，

deque

deque在功能上合并vector和list

stack

stack.push(elem);   //往栈头添加元素
stack.pop();             //从栈头移除第一个元素
stack.top();            //返回最后一个压入栈元素，即返回栈顶元素

queue

stack.push(elem);   //往队尾添加元素
stack.pop();             //从队头移除第一个元素

其他操作同deque容器。

priority_queue

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

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

一、通过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<T1,T2,less<T1> >  mapA;  //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less<T1>函数对象。
map<T1,T2,greater<T1>> mapB;   //该容器是按键的降序方式排列元素。

总结

image.png
容器时间复杂度 image.png
  1. vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却是不固定的。
  2. 如果有大量释放操作的话，vector花的时间更少，这跟二者的内部实现有关。
  3. deque支持头部的快速插入与快速移除，这是deque的优点。

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

上一篇 下一篇

猜你喜欢

热点阅读