C++STL基本容器的使用

C++中有两种类型的容器：序列式容器和关联式容器

序列式容器：主要有vector、list、deque等

vector表示一段连续的内存地址，基于数组的实现；
list表示非连续的内存，基于链表实现的；
deque与vector类似，不同之处就是：对于首元素提供删除和插入的双向支持（c++标准建议：vector是那种应该在默认情况下使用的序列。如果大多数插入和删除操作发生在序列的头部或尾部时，应该选用deque）
关联式容器：主要有map和set、multimap和multiset、underodmap和underodset、priority_queue。

map是key-value形式的，set是单值。
map和set只能存放唯一的key值，而multimap和multiset可以存放多个相同的key值，（这四个都是基于红黑树实现的接口）；
underodmap和underodset是基于哈希表实现的接口。
另外，容器类自动申请和释放内存，我们无需new和delete操作。

下面详细介绍一下各种容器的用法及其接口的使用：

序列式容器
一. vector ：
vector采用一段连续的内存来存储其元素，向vector添加元素的时候，如果容量不足,vector便会重新malloc一段更大的
内存,然后把原内存中的数据memcpy到新的内存中,并free原内存块，然后将新元素加入。
vector的元素插入性能跟以下几个要素关系重大：

1. 插入的位置

   头部插入：将所有元素后移，然后将新元素插入
   中间插入：将插入点后面的元素后移，然后插入新元素  
   尾部插入：将新元素直接插入尾部

   总结：
        尾部插入无疑是最快的，头部插入最慢，中间插入次之，（尾部插入>中间插入>头部插入）
        慢的原因：在于插入前要移动后面的所有元素。删除元素也是同样的道理。

2. 保留空间大小

   如果插入元素是，空间不足将导致重新malloc以及一系列的内存拷贝。如果使用者能对容量有预期，
   那么采用reserve()来预先分配内存，将大大的提高性能。

综述，vector适用于尾部插入，但是此时无法兼顾查找的性能，因为二分查找的vector要求重新排序，
或者要求vector在插入时就保持有序，这样就无法做到尾部插入。

但是vector作为动态数组的替代，已经足够优秀。

常用接口：

头文件： #include

//1.定义和初始化

 vector<int> vec1;                           // 默认初始化，vec1为空
 vector<int> vec2(vec1);                     // 使用vec1初始化vec2
 vector<int> vec3(vec1.begin(),vec1.end());  // 使用vec1初始化vec2
 vector<int> vec4(10);                       // 10个值为0的元素
 vector<int> vec5(10,4);                     // 10个值为4的元素

//2.常用操作方法

 vec1.push_back(100);                       // 尾部添加元素
 int size = vec1.size();                    // 元素个数
 bool isEmpty = vec1.empty();               // 判断是否为空
 cout<<vec1[0]<<endl;                       // 取得第一个元素
 vec1.insert(vec1.end(),5,3);               // 从vec1.back位置插入5个值为3的元素
 vec1.pop_back();                           // 删除末尾元素
 vec1.erase(vec1.begin(),vec1.begin()+2);   // 删除vec1[0]-vec1[2]之间的元素，不包括vec1[2](左闭右开)
 cout<<(vec1==vec2)?true:false;              // 判断是否相等==、！=、>=、<=...
 vector<int>::iterator iter = vec1.begin();          // 获取迭代器首地址
 vector<int>::const_iterator c_iter = vec1.begin();   // 获取const类型迭代器
 vec1.clear();                                // 清空元素

//3.遍历

// 1. 下标法
int length = vec1.size();
for(int i=0;i<length;i++)
{
   cout<<vec1[i]<<" ";
}
cout<<endl;

// 2. 迭代器法
vector<int>::iterator iter = vec1.begin();
for(;iter != vec1.end();iter++)
{
   cout<<*iter<<" ";
}
 cout<<endl;

详细的用法请看一下我的另外一篇文章：
C++STL序列式容器—vector和list常用的接口用法以及vector和list的区别
https://blog.csdn.net/qq_37941471/article/details/81984417

二. list：
list很简单，它就是个双向链表。每一个节点的内存都是独立的。

理论上，其优点是：任何位置的插入删除元素操作都是非常快的。

    缺点是：不适合用于元素的查找，因为他只能是扫描的方式。 

单链表和双向链表的优缺点：

  1. 结构上而言：双向链表复杂，占用的空间大一点
  2. 插入和删除：双向链表简单，更实用（因为在删除和插入时，需要找到前一个prev,而双向链表不用找）
  3. 时间复杂度：双向链表O(1);单链表O(n)

既然双向链表的优点很多，为什么单链表也很重要？

  因为：单链表会在哈希表的拉链法中会用到，还有图中会用到，应用还是很广的。 
       如果单用链表时，双向链表会比较好。

vector和list的区别：
相同点：

  1. 都可以存储一组类型相同的元素
  2. 尾部插入和删除，性能差不多

不同点：

  1. 存储顺序：

     vector ：是顺序表，表示的是一块连续的内存，元素被顺序存储；
       list : 是双向链表，在内存中不一定连续。

  2. 扩容的开销：

     vector : 当数值内存不够时，vector会重新申请一块足够大的连续内存，把原来的数据拷贝到新的内存里面
       list : 因为不用考虑内存的连续，因此新增开销比vector小。

  3. 头部或者中间的插入和删除： 

      vector ：vector需要进行元素的移动
        list : 性能比vector好
  4. 随机访问:

     vector : 直接通过下标就可以访问，时间复杂度为O(1)
       list : 需要遍历，时间复杂度为O(n)
       所以：vector的随机访问效率更高

总而言之：

     1. 已知需要存储的元素时，vector要好
     2. 如果需要任意位置插入元素，list要好

常用的接口：
头文件： #include

// 1.定义和初始化

list<int> lst1;                           // 创建空list
list<int> lst2(3);                        // 创建含有三个元素的list
list<int> lst3(3,2);                      // 创建含有三个元素为2的list
list<int> lst4(lst2);                     // 使用lst2初始化lst4
list<int> lst5(lst2.begin(),lst2.end());  // 同lst4

// 2.常用操作方法

lst1.push_back(10);                    // 末尾添加值
lst1.pop_back();                       // 删除末尾值
lst1.begin();                          // 返回首值的迭代器
lst1.end();                            // 返回尾值的迭代器
lst1.clear();                          // 清空值
bool isEmpty1 = lst1.empty();          // 判断为空
lst1.erase(lst1.begin(),lst1.end());   // 删除元素
lst1.front();                          // 返回第一个元素的引用
lst1.back();                           // 返回最后一个元素的引用
lst1.insert(lst1.begin(),3,2);         // 从指定位置插入个3个值为2的元素
lst1.rbegin();                         // 返回第一个元素的前向指针
lst1.remove(2);                        // 删除链表中所有为2的元素
lst1.reverse();                        // 反转
lst1.size();                           // 含有元素个数
lst1.sort();                           // 排序
lst1.unique();                         // 删除相邻重复元素

//3.遍历
//迭代器法
list<int>::iterator iter = lst1.begin();
for(;iter != lst1.end();iter++)
{
   cout<<*iter<<" ";
}
 cout<<endl;

详细的用法请看一下我的另外一篇文章：
C++STL序列式容器—vector和list常用的接口用法以及vector和list的区别
https://blog.csdn.net/qq_37941471/article/details/81984417

关联式容器
一. set & multiset：
set的含义是集合，它是一个有序的容器，里面的元素都是排序好的支持插入、删除、查找等操作，就像一个集合一样，所有的操作都是严格在logn时间内完成，效率非常高。set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同，set默认是自动排序的，使用方法类似list。

二. map & multimap：
c++map容器提供一个键值对(key/value)容器，map与multimap差别仅仅在于multimap允许一个键对应多个值。需要包含头文件#include。对于迭代器来说，可以修改实值，而不能修改key。map会根据key自动排序.

详细的用法请看一下我的另外一篇文章：
https://blog.csdn.net/qq_37941471/article/details/81039195

各个容器之间的性能对比：

1. vector
   变长一维数组，连续存放的内存块，有保留内存，堆中分配内存；

支持[]操作，高效率的随机访问；

在最后增加元素时，一般不需要分配内存空间，速度快；在中间或开始操作元素时要进行内存拷贝效率低；

vector高效的原因在于配置了比其所容纳的元素更多的内存，内存重新配置会花很多时间；

注：需要高效的随即存取，而不在乎插入和删除使用vector。

2. list
   双向链表，内存空间上可能是不连续的，无保留内存，堆中分配内存；

不支持随机存取，开始和结尾元素的访问时间快,其它元素都O（n）；

在任何位置安插和删除元素速度都比较快，安插和删除操作不会使其他元素的各个pointer，reference，iterator失效；

注：大量的插入和删除，而不关系随即存取使用list。

3. deque
   双端队列，在堆上分配内存，一个堆保存几个元素，而堆之间使用指针连接；

支持[]操作，在首端和末端插入和删除元素比较快，在中部插入和删除则比较慢，像是list和vector的结合；

注：关心插入和删除并关心随即存取折中使用deque。

4. set & multiset
   有序集合，使用平衡二叉树存储，按照给定的排序规则（默认按less排序—升序）对set中的数据进行排序；

set中不允许有重复元素，multiset中运行有重复元素；

两者不支持直接存取元素的操作；

因为是自动排序，查找元素速度比较快；

不能直接改变元素值，否则会打乱原本正确的顺序，必须先保存下要删除旧元素，再插入新的元素。

5. map & multimap
   字典库，一个值映射成另一个值，使用平衡二叉树存储，按照给定的排序规则对map中的key值进行排序；

map中的key值不允许重复，multimap中的key允许重复；

根据已知的key值查找元素比较快； 插入和删除操作比较慢。

赏 支付宝打赏 微信打赏

如果文章或资源对您有帮助，欢迎打赏作者。一路走来，感谢有您！