顺序容器

亦凉 2023-05-31 10:22 10阅读 0赞

本文借鉴多篇博客：  
https://www.cnblogs.com/geloutingyu/p/8284527.html  
https://www.cnblogs.com/QG-whz/p/5152963.html\#*label0  
https://blog.csdn.net/zhengqijun*/article/details/81566109  
https://blog.csdn.net/weixin\_42587961/article/details/96894152

# 1.容器概论 #

容器，置物之所也。像桶可装水，碗可盛汤，C++的容器，可以存储对象。容器有多种，用来处理不同的元素操作诉求。按照元素存储到容器中以及访问方式的差异，容器分为顺序容器与关联容器。顺序容器也称为序列式容器。序列式容器按元素插入的顺序存储元素，这些元素可以进行排序，但未必是有序的。C++本身内置了一个序列式容器array（数组），STL另外提供了vector,list,forward\_list,deque,stack,queue,priority-queue，string等等序列式容器。所有的容器都是基于模板实现的，因为容器必须保证能装得下各种各样的类型。其中，stack，queue都是基于deque来实现的，priority-queue基于heap来实现，从技术上来说它们属于容器适配器（adapter）。其中array与forward\_list是C++11添加的新容器类型。

# 2.std::array #

### 2.1.底层数据结构 ###

array的底层数据结构是固定数组。与C-style的数组类似，它的大小在定义后就不能被改变。由于array具有固定的大小，它不支持添加和删除元素或改变容器大小等其他容器拥有的操作。在定义一个array容器的时候必须指定大小：

### 2.2.内存分配策略 ###

在内存分配策略上，array也与C-style数组类似。编译器在哪里为array分配内存，取决于array定义的位置和方式。

*  若作为函数的局部对象，则将从栈上获得内存，与之对比是的vector，vector底层数据结构是动态数组，从自由存储区上分配内存：
 *  若使用new操作符分配内存，则是在自由存储区上分配内存。
 *  若作为全局变量或局部静态变量，则是在全局/静态存储区上分配的内存。

例如，在函数定义的array局部对象在栈上分配内存，与此对比的是vector，它底层数据结构为动态数组，因此在自由存储区上分配内存：

### Iterators ###

Iterators迭代器的作用是遍历array数组类中的元素。可以通过begin/end()、rbegin/rend()、cbegin/cend()、crbegin/crend()等函数进行访问。

<table> 
 <thead> 
  <tr> 
   <th>begin</th> 
   <th>Return iterator to beginning</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>end</td> 
   <td>Return iterator to end</td> 
  </tr> 
  <tr> 
   <td>rbegin</td> 
   <td>Return reverse iterator to reverse beginning</td> 
  </tr> 
  <tr> 
   <td>rend</td> 
   <td>Return reverse iterator to reverse end</td> 
  </tr> 
  <tr> 
   <td>cbegin</td> 
   <td>Return const_iterator to beginning</td> 
  </tr> 
  <tr> 
   <td>cend</td> 
   <td>Return const_iterator to end</td> 
  </tr> 
  <tr> 
   <td>crbegin</td> 
   <td>Return const_reverse_iterator to reverse beginning</td> 
  </tr> 
  <tr> 
   <td>crend</td> 
   <td>Return const_reverse_iterator to reverse end</td> 
  </tr> 
 </tbody> 
</table>

样例：

#include<array>
    #include<iostream>
    using namespace std;
    int main(){
        array<int ,5>arr={1,2,3,4,5};
        for(array<int,5>::iterator it=arr.begin();it!=arr.end();it++)cout<<*it<<" ";
        return 0;
    }

### （2）Capacity ###

array数组容器的大小是固定的。可以通过sizeof()、size()、max\_size()、empty()等函数进行检测。

<table> 
 <thead> 
  <tr> 
   <th>size</th> 
   <th>Return size</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>max_size</td> 
   <td>Return maximum size</td> 
  </tr> 
  <tr> 
   <td>empty</td> 
   <td>Test whether list is empty</td> 
  </tr> 
 </tbody> 
</table>

#include<array>
    #include<iostream>
    using namespace std;
    int main(){
        array<int ,50>arr={1,2,3,4,5};
        cout<<sizeof(arr)<<endl;
        cout<<arr.size()<<endl;
        cout<<arr.max_size()<<endl;
    
        if(!arr.empty())cout<<"非空"<<endl;
        else cout<<"空"<<endl;
        return 0;
    }

### （3）Element access ###

可以通过下标\[ \]、at()、front()、back()、data()等函数访问array容器内的元素。

<table> 
 <thead> 
  <tr> 
   <th>operator[ ]</th> 
   <th>Access element</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>at</td> 
   <td>Access element</td> 
  </tr> 
  <tr> 
   <td>front</td> 
   <td>Access first element</td> 
  </tr> 
  <tr> 
   <td>back</td> 
   <td>Access last element</td> 
  </tr> 
  <tr> 
   <td>data</td> 
   <td>Get pointer to first data</td> 
  </tr> 
 </tbody> 
</table>

#include<array>
    #include<iostream>
    using namespace std;
    int main(){
        array<int ,5>arr={1,2,3,4,5};
        cout<<arr[0]<<endl;
        cout<<arr.at(4)<<endl;
        cout<<arr.front()<<endl;
        cout<<arr.back()<<endl;
        cout<<arr.data()<<"=="<<&arr<<endl;
        return 0;
    }

### （4）Modifiers ###

可以使用fill()、swap()等函数对array容器整体进行操作。

#include<array>
    #include<iostream>
    using namespace std;
    int main(){
        array<int ,5>arr={1,2,3,4,5};
        arr.fill(2);//全部赋值为2
        array<int,5>arr1;
        arr1.fill(1);//全部赋值为1
        arr.swap(arr1);//能在线性时间里交换两个array的数值
        return 0;
    }

###### 总结： ######

为什么array比数组好？

*  安全，它提供了opeartor\[\]与at()成员函数，后者将进行数组越界检查、
 *  与其他容器相似，array也有自己的迭代器，因此array能够更好地与标准算法库结合起来。
 *  通过array::swap函数，可以实现线性时间内的两个数组内容的交换

### （5）Compare ###

还可以使用> < ==等符号对两个array数组容器进行比较。

#include<array>
    #include<iostream>
    using namespace std;
    int main(){
        array<int ,5>arr={1,2,3,4,5};
        arr.fill(2);//全部赋值为2
        array<int,5>arr1;
        arr1.fill(1);//全部赋值为1
    
        if(arr<arr1)cout<<"arr<arr1";
        else cout<<"arr>=arr1";cout<<endl;
    
        if(arr>arr1)cout<<"arr>arr1";
        else cout<<"arr<=arr1";cout<<endl;
    
        if(arr==arr1)cout<<"arr==arr1";
        else cout<<"arr!=arr1";cout<<endl;
    
        return 0;
    }
    /*
    arr>=arr1
    arr>arr1
    arr!=arr1
    */

### 3.forward\_list ###

##### 3.1.底层数据结构 #####

forward\_list的底层数据结构为单向链表。如C++标准所讲，forward\_list容器支持前向遍历元素序列，允许常数时间内在任意位置的插入或删除操作并进行自动的内存管理。与list的主要区别是forward\_list没有反方向的迭代器，不过也正因如此，forward\_list的每个节点都节省了迭代器大小的开销，在元素众多的时候，将比list消耗少得多的内存。

受单向链表这种特殊结构的影响，forward\_list在很多地方表现得和其他容器不同：

##### 3.2.forward\_list特殊之一：forward\_list不提供返回其大小的操作。 #####

在所有已知的STL容器中，forward\_list是唯一一个不提供size()的容器。不提供的原因在于计算一个forward\_list的长度需要线性的时间，库用户有时无法忍受这样的时间开销。其他容器提供的size()操作皆可以在常数时间内完成（在C++98时，list也是线性时间）。为了节省内存，forward\_list甚至不跟踪序列的长度，要想获得某个forward\_list对象的长度，用户需要通过distance()来计算。这带来了一些不便，但使得用户远离了size()带来的高消耗。每个容器类型都有三个与大小相关的操作：max\_size(),empty(),size(),而forward\_list只提供了前两个。

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        forward_list<int> lis={1,2,3,4,5};
        for(auto i=lis.begin();i!=lis.end();i++){
            i=lis.insert_after(i,0);
        }//每次向之后的点给插入。
    
        for(auto i=lis.begin();i!=lis.end();i++){
            cout<<*i<<endl;
        }
        return 0;
    }

接口 描述

<table> 
 <thead> 
  <tr> 
   <th>insert_after</th> 
   <th>在给定位置之后插入新元素</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>emplace_after</td> 
   <td>在给定位置之后构造新元素</td> 
  </tr> 
  <tr> 
   <td>erase_after</td> 
   <td>删除给定位置之后的元素</td> 
  </tr> 
  <tr> 
   <td>splice_after</td> 
   <td>将另一个forward_list的元素移动到本forward_list的指定位置之后</td> 
  </tr> 
 </tbody> 
</table>

###### 3.4.迭代器失效问题 ######

指向被删除元素的迭代器，在删除之后失效。

### 4.list ###

#### 4.1.底层数据结构 ####

list同样是一个模板类，它底层数据结构为双向循环链表。因此，它支持任意位置常数时间的插入/删除操作，不支持快速随机访问。

#### 4.2.迭代器类型 ####

list的迭代器具备前移、后移的能力，所以list提供的是Bidirectional iterator(双向迭代器)。由于采用的是双向迭代器，自然也很方便在指定元素之前插入新节点，所以list很正常地提供了insert()操作与push\_back()/pop\_back()操作。在C++11中，list新增了三个接口，以支持在指定位置构造对象后插入容器中:

<table> 
 <thead> 
  <tr> 
   <th>接口（C++11新增）</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>emplace</td> 
   <td>在指定位置之前插入新构造的元素</td> 
  </tr> 
  <tr> 
   <td>emplace_front</td> 
   <td>在链表头插入新构造的元素</td> 
  </tr> 
  <tr> 
   <td>emplace_back</td> 
   <td>在链表尾插入新构造的元素</td> 
  </tr> 
 </tbody> 
</table>

###### 4.3.内存分配策略 ######

list的空间配置策略，自然是像我们普通双向链表那样，有多少元素申请多少内存。它不像vactor那样需要预留空间供新元素的分配，也不会因找不到连续的空间而引起整个容器的内存迁移。

###### 4.4.迭代器失效问题 ######

list 有一个重要性质：插入操作（insert）与接合操作（splice）都不会造成原有的list迭代器失效。这在vector是不成立的，因为vactor的插入可能引起空间的重新配置，导致原来的迭代器全部失效。list的迭代器失效，只会出现在删除的时候，指向删除元素的那个迭代器在删除后失效。

通常来说，forward\_list在使用灵活度上比不上list，因为它只能单向迭代元素，且提供的接口没有list多。然而，在内存的使用上，它是比list占优势的。当对内存的要求占首要位置时，应该选择forward\_list。

###### 一些list用法 ######

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        list<int> a;
        a.emplace(a.begin(),3);//在给定位置之前插入元素，forward_list是唯一一个在给定位置之后插入元素的。
        a.emplace_front(2);//在首部插入
        a.emplace_back(4);//在尾部插入
        cout<<a.size()<<endl;
        cout<<a.empty()<<endl;
        a.resize(10);//将现有元素调制10个，多删少补。值随机
        cout<<*--a.end()<<endl;
        a.resize(15,2);//将元素调至15个，多删少补，新添值为2
        cout<<*--a.end()<<endl;
        a.push_back(55);//在后面添加元素
        cout<<*--a.end()<<endl;
        a.insert(a.begin(),1);
        cout<<*a.begin()<<endl;
        a.insert(a.begin(),3,9);//插入3个大小为9的元素
        cout<<*a.begin()<<endl;
        a.push_front(10);//头部插入
        cout<<*a.begin()<<endl;
        a.erase(a.begin());
        cout<<*a.begin()<<endl;
        //a.erase(a.begin(),a.end());//区间删除元素
        //cout<<a.size()<<endl;
    //    a.clear();//清空
    //    cout<<a.size()<<endl;
        a.pop_front();
        cout<<*a.begin()<<endl;
        a.pop_back();
        cout<<*--a.end()<<endl;
    
        a.assign(1,33);
        cout<<*a.begin()<<endl;//给list重新定义为只有一个数字的list
        list<int> b;
        b.assign(a.begin(),a.end());//区间赋值
        cout<<*b.begin()<<endl;
        cout<<a.back()<<endl;//返回最后一个元素
        cout<<a.front()<<endl;//返回第一个值
        b.assign(1,44);
        a.swap(b);
        cout<<a.front()<<endl;
        a.merge(b);
        cout<<a.size()<<endl;
        cout<<b.size()<<endl;
        a.sort();//排序
        cout<<a.front()<<" "<<a.back()<<endl;
        a.reverse();//翻转
        cout<<a.front()<<endl;
        a.unique();//去重
        cout<<a.size()<<endl;
        b=a;
        a.splice(b.begin(),b.end());
        cout<<b.size()<<endl;
        a.splice(a.begin(),it);//(要插入的位置迭代器，要插入的元素的迭代器）
        a.splice(a.begin(),l2,it);//（要插入的位置，要插入的元素在哪个链表中，该链表中的这个元素的迭代器）
        a.splice(a.begin(),l1,it,it2)//（要插入的位置，要插入的元素在哪个链表中，插入该链表中这个位置，到这个位置范围内的元素）；
    
        return 0;
    }

### 5.vector ###

##### 5.1.底层数据结构 #####

vector的底层数据结构是动态数组，因此，vector的数据安排以及操作方式与std::array十很相似，它们间的唯一差别在于对空间的运用灵活性上。array为静态数组，有着静态数组最大的缺点：每次只能分配一定大小的存储空间，当有新元素插入时，要经历 “找到更大的内存空间”->“把数据复制到新空间” ->“销毁旧空间” 三部曲， 对于std::array而言，这种空间管理的任务压在使用它的用户身上，用户必须把握好数据的数量，尽量在第一次分配时就给数据分配合理的空间（这有时很难做到），以防止“三部曲”带来的代价，而数据溢出也是静态数组使用者需要注意的问题。而vector用户不需要亲自处理空间运用问题。vector是动态空间，随着新元素的插入，旧存储空间不够用时，vector内部机制会自行扩充空间以容纳新元素，当然，这种空间扩充大部分情况下（几乎是）也逃脱不了“三部曲”，只是不需要用户自己处理，而且vector处理得更加安全高效。vector的实现技术关键就在于对其大小的控制以及重新配置时数据移动效率。

###### 5.3.内存分配策略 ######

标准库的实现者使用了这样的内存分配策略：以最小的代价连续存储元素。为了使vector容器实现快速的内存分配，其实际分配的容量要比当前所需的空间多一些(预留空间)，vector容器预留了这些额外的存储区用于存放添加的新元素，于是不必为每个新元素进行一次内存分配。当继续向容器中加入元素导致备用空间被用光（超过了容量 capacity），此时再加入元素时vector的内存管理机制便会扩充容量至两倍，如果两倍容量仍不足，就扩张至足够大的容量。容量扩张必须经历“重新配置、元素移动、释放原空间”这个浩大的工程。按照《STL源码剖析》中提供的vector源码，vector的内存配置原则为：

如果vector原大小为0，则配置1，也即一个元素的大小。  
如果原大小不为0，则配置原大小的两倍。  
当然，vector的每种实现都可以自由地选择自己的内存分配策略，分配多少内存取决于其实现方式，不同的库采用不同的分配策略。

定义：
    #include<bits/stdc++.h>
    using namespace std;
    int main(){
        vector<int>a;
        vector<int> b(5);
        vector<int> c(10,2);
        vector<int> d(b.begin(),b.end());
        int arr[5] = {1, 2, 3, 4, 5};
        vector<int> e(arr,arr+5);
        vector<int> f(&arr[0],&arr[4]);
        return 0;
    }

#### 常用方法 ####

#include<bits/stdc++.h>
    using namespace std;
    int main(){
        vector<int>a(100,2);
        cout<<a.max_size()<<endl;
        a.resize(5);
        cout<<a.size()<<endl;
        cout<<a.capacity()<<endl;//初始化大小总是100
        a.shrink_to_fit();
        cout<<a.capacity()<<endl;
        a.assign(a.begin(),a.end());
        cout<<a.size()<<endl;
        vector<int> b(5,3);
        a.swap(b);//交换两个向量元素
        cout<<a[1]<<endl;
        return 0;
    }

##### 6.deque #####

###### 6.1.底层数据结构 ######

vector是单向开口的线性连续空间，deque则是一种双向开口的连续数据空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。当然vector也可以在头尾两端进行操作，但是其头部操作效果奇差，所以标准库没有为vector提供push\_front或pop\_front操作。与vector类似，deque支持元素的快速随机访问。deque的示意图如下：  
![在这里插入图片描述][20191024212504101.png]  
现在问题来了：如果deque以数组来实现，如何做到在头部的常数时间插入？如果是采用链表来实现，又如何做到快速随机访问？deque的内部数据结构到底如何？想必你已经猜到了，要实现如上需求，需要由一段一段的连续空间链接起来的数据结构才能满足。

###### 6.2.内存分配策略 ######

接着上面讲。deque由一段一段的连续空间所链接而成，一旦需要在deque的前端或尾端增加新空间，便配置一段定量的连续空间，并将该空间串接在deque的头部或尾部。deque复杂的迭代器架构，构建出了所有分段连续空间”整体连续“的假象。  
既然deque是由一段一段定长的连续空间所构成，就需要有结构来管理这些连续空间。deque采用一块map（非STL中的map）作为主控，map是一块小的连续空间，其中每个元素都是指针，指向一块较大的线性连续空间，称为缓冲区。而缓冲区才是存储deque元素的空间主体。示例图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70]

map本身也是一块固定大小的连续空间，当缓冲区数量增多，map容不下更多的指针时，deque会寻找一块新的空间来作为map。

6.3.deque的迭代器  
为了使得这些分段的连续空间看起来像是一个整体，deque的迭代器必须有这样的能力：它必须能够指出分段连续空间在哪里，判断自己所指的位置是否位于某一个缓冲区的边缘，如果位于边缘，则执行operator-- 或operator++时要能够自动跳到下一个缓冲区。因此，尽管deque的迭代器也是Ramdon Access Iterator 迭代器，但它的实现要比vector的复杂太多。SGI版本的STL deque实现思路可以看侯捷的《STL源码剖析》。

6.4.迭代器失效问题  
在deque容器首部或者尾部插入元素不会使得任何迭代器失效。  
在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。  
在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

### 7.容器适配器 ###

stack，也称为栈，是一种先进后出的数据结构。STL中的statck是一种容器适配器。所谓的容器适配器，是以某种容器作为底部容器，在底部容器之上修改接口，形成另一种风貌。stack默认以双端队列deque作为底部容器。stack没有提供迭代器，通过push/pop接口对栈顶元素进行操作。

queue，也称为队列，是一种先进先出的数据结构，它同样也是一种容器适配器。它的底部容器默认为deque。同样，queue也没有提供迭代器，通过push向队尾压入元素，pop从队首弹出元素。

priority-queue，优先队列，是一种拥有权值观念的队列，例如在以整数大小作为衡量的权值定义下，priority-queue总是弹出最大的数。priority-queue的底部数据结构默认是max-heap，大顶堆。

### 8.总结 ###

<table> 
 <thead> 
  <tr> 
   <th>容器</th> 
   <th>底层数据结构</th> 
   <th>元素访问方式</th> 
   <th>插入或删除元素效率</th> 
   <th>迭代器失效情况</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>array</td> 
   <td>固定大小的数组</td> 
   <td>支持快速随机访问</td> 
   <td>不能添加或删除元素</td> 
   <td>通常不会发生迭代器失效，除非对象已经被销毁，则原来的迭代器全部失效</td> 
  </tr> 
  <tr> 
   <td>vector</td> 
   <td>可动态增长的数组</td> 
   <td>支持快速随机访问</td> 
   <td>尾部可高效插入/删除元素</td> 
   <td>若插入操作引起内存重新分配，则全部迭代器失效；否则插入点/删除点之后的迭代器失效;</td> 
  </tr> 
  <tr> 
   <td>list</td> 
   <td>双向链表</td> 
   <td>只支持元素的双向顺序访问 在list的任何位置可高效插入/删除元素 插入操作后指向容器的迭代器有效；</td> 
   <td>删除操作指向其他位置的迭代器有效</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>deque</td> 
   <td>双端队列</td> 
   <td>支持快速随机访问</td> 
   <td>首尾可高效插入/删除元素</td> 
   <td>情况较多，见上面分析</td> 
  </tr> 
  <tr> 
   <td>forward_list</td> 
   <td>单向链表</td> 
   <td>只支持元素的单向顺序访问 在链表的任何位置可高效插入/删除元素</td> 
   <td>插入操作后指向容器的迭代器有效；删除操作指向其他位置的迭代器有效</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>string</td> 
   <td>只存储字符元素的动态数组</td> 
   <td>支持快速随机访问</td> 
   <td>尾部可高效插入/删除元素</td> 
   <td>若插入操作引起内存重新分配，则全部迭代器失效；否则插入点/删除点之后的迭代器失效;</td> 
  </tr> 
  <tr> 
   <td>stack</td> 
   <td>默认deque</td> 
   <td>先进后出，</td> 
   <td>只能访问栈顶元素</td> 
   <td>---- 没有迭代器</td> 
  </tr> 
  <tr> 
   <td>queue</td> 
   <td>默认deque</td> 
   <td>先进先出，</td> 
   <td>只能访问队首元素</td> 
   <td>---- 没有迭代器</td> 
  </tr> 
  <tr> 
   <td>priority-queue</td> 
   <td>默认max-heap</td> 
   <td>先进先出，</td> 
   <td>只能访问队首元素</td> 
   <td>---- 没有迭代器</td> 
  </tr> 
 </tbody> 
</table>

[20191024212504101.png]: /images/20230531/5284fb8e532243e7b07334e7b54b7e66.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpemlfZ2hx_size_16_color_FFFFFF_t_70]: /images/20230531/e2c0551240c445689c57863e60e2c8f0.png