C++标准模板库(STL):vector、deque和list

青旅半醒 2022-05-09 09:06 323阅读 0赞

之所以把这几个容器写在一起，是因为他们都是序列式容器。

**序列式容器以线性序列的方式存储元素（线性结构）。它没有对元素进行排序，元素的顺序和存储它们的顺序相同。以下有几种标准的序列容器，每种容器都具有不同的特性：**

>  *  vector<T>(向量容器)是一个长度可变的序列，用来存放 T 类型的对象。必要时，可以自动增加容量，但只能在序列的末尾高效地增加或删除元素。
>  *  deque<T>(双向队列容器)是一个长度可变的、可以自动增长的序列，在序列的两端都能高效地增加或删除元素。 
>  *  list<T>(链表容器)是一个长度可变的、由 T 类型对象组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素。访问容器中任意元素的速度要比前三种容器慢，这是因为 list<T> 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。

--------------------

## **vector** ##

**       vector<T> 容器可以方便、灵活地代替数组。在大多数时候，都可以用 vector<T> 代替数组存放元素。vector<T> 在扩展容量，以及在序列内部删除或添加元素时会产生一些开销，效率低下；但大多数情况下，不会明显变慢。 为了使用 vector<T> 容器模板，需要在代码中包含头文件 vector。** **vector<T> 容器的大小可以自动增长，从而可以包含任意数量的元素。只要元素个数超出 vector 当前容量，就会自动分配更多的空间。只能在容器尾部高效地删除或添加元素（在中间添加和删除并不高效）。**

![70][]

*  **创建vector对象**

> **      vector<元素类型>对象名（\[容器大小\]，\[元素初始值】）；**

vector<int> v1;  //创建一个空的vector容器 ，对象名后面不能有括号
       vector<string> v2(10, "abc"); //创建一个大小为10的容器对象，并把这十个元素全部赋值abc
       vector<string> v3(v2); //用v2来初始化v3
       vector<int> v4{ 1,2,3,6 };

*  **获取容器容量和大小**

**         分配大小（**如果通过调用 reserve() 来增加内存，任何现有的迭代器，例如开始迭代器和结束迭代器，都会失效，所以需要重新生成它们。这是因为，为了增加容器的容量，vector<T> 容器的元素可能已经被复制或移到了新的内存地址。一般不用自己扩容，因为这是自动的。**）**

> **v1.reserve(20);**

**         获取容器容量和大小（**一般容量比大小大**）**

> **容器容量：int capacity=v1.capacity();**
> 
> **容器大小：int size=v.size();**

*  **赋值函数**

**        **可以用成员函数assign()来给容器赋值。

//将5个3赋值给v1
    v1.assign(5, 3);
    //将[begin,end)区间中的元素赋值给容器，即[a,a+5)不包括a+5
    int a[5] = { 1,2,3,5,6 };
    v4.assign(a, a + 5);

*  **访问元素**

//两种访问方式 
    cout<<v1[1];
    cout << v1.at(1);

*  **对首元素和末元素的操作**

v4.push_back(2); //在容器末尾添加元素2
    v4.pop_back();   //删除容器最后一个元素，但并不会返回这个元素值
    v4.front()=2;      //获取容器第一个元素的引用，可对第一个元素进行操作
    v4.back()=2;       //获取容器最后一个元素的引用，可对最后一个元素进行操作
    v4.begin();        //获得指向首元素的迭代器（可理解为指针）
    v4.end();          //获得指向末元素后一个元素的迭代器（其实这个元素并不存在）

*  **插入和删除（中间元素）**

**        insert()和erase()函数的pos位置只能用迭代器begin()和end()来指示，不能用数字作为参数。**

v4.insert(pos, elem);   //在pos位置上插入元素elem,返回该数据的位置(指向该位置的迭代器）
    	v4.insert(pos, n, elem);//在pos位置上插入n个elem元素,无返回值
    	v4.insert(pos, begin, end);//在pos位置上插入[begin,end）区间的数据，无返回值

v4.erase(pos);  //移除pos位置上的元素，返回下一个元素的迭代器
    	v4.erase(begin,end)  //移除[begin,end）区间的数据，返回下一个元素的迭代器

--------------------

# #

## deque(双端队列） ##

** deque<T>，一个定义在 deque 头文件中的容器模板，可以生成包含 T 类型元素的容器，它以双端队列的形式组织元素。可以在容器的头部和尾部高效地添加或删除对象，这是它相对于 vector 容器的优势。当需要这种功能时，可以选择这种类型的容器。无论何时，当应用包含先入先出的事务处理时，都应该使用 deque 容器。处理数据库事务或模拟一家超市的结账队列，像这两种应用都可以充分利用 deque 容器。**

![70 1][]

> **deque的创建对象、赋值、访问和对首末元素的操作和vector一模一样（front()函数依旧是返回引用）。**
> 
> **对于插入删除也和vector一样，但是deque增加了以下函数。**

v1.push_front(1); //在双向队列最前面添加元素
    	v1.pop_back();  //删除最后一个元素
    	v1.pop_front();   //删除第一个元素

--------------------

## list（双向链表） ##

>      list<T> 容器模板定义在 list 头文件中，是 T 类型对象的双向链表。  
>   
>      list 容器具有一些 vector 和 deque 容器所不具备的优势，它可以在常规时间内，在序列已知的任何位置插入或删除元素。这是我们使用 list，而不使用 vector 或 deque 容器的主要原因。  
>   
>       list 的缺点是无法通过位置来直接访问序列中的元素，也就是说，不能索引元素。为了访问 list 内部的一个元素，必须一个一个地遍历元素，通常从第一个元素或最后一个元素开始遍历。
> 
>        list<T> 容器的每个 T 对象通常都被包装在一个内部节点对象中，节点对象维护了两个指针，一个指向前一个节点，另一个指向下一个节点。这些指针将节点连接成一个链表。通过指针可以从任何位置的任一方向来遍历链表中的元素。第一个元素的前向指针总是为 null,因为它前面没有元素，尾部元素的后向指针也总为 null。这使我们可以检测到链表的尾部。list<T> 实例保存了头部和尾部的指针。这允许我们从两端访问链表，也允许从任一端开始按顺序检索列表中的元素。  
>   
>       可以用和其他序列容器相同的方式，来获取 list 容器的迭代器。因为不能随机访问 list 中的元素，获取到的迭代器都是双向迭代器。以 list 为参数，调用 begin() 可以得到指向 list 中第一个元素的迭代器。通过调用 end()，可以得到一个指向最后一个元素下一个位置的迭代器，因此像其他序列容器一样，可以用它们来指定整个范围的元素。也可以像其他容器一样，使用 rbegin()、rend()、crbegin()、crend()、cbegin()、cend() 来获取反向迭代器和 const 迭代器。

![70 2][]

*  **创建对象、赋值**

和vector、deque一样。

*  **元素访问和首尾元素的操作**

**       ** 一样和deque有front()、back()、push\_back()、push\_front()、pop\_back()、pop\_front()。

**但是**不能像前面两个容器那样直接用\[\]和at()访问其中的元素。

*  **插入和删除**

**       insert()和erase()和前面一样，只不过多了一个remove()函数。**

list.remove(elem);  //从容器中删除所有与elem匹配的元素

## **list一些函数的应用（成员函数，不需要包含在algorithm头文件中）** ##

*  **merge()合并函数**

>    list 的成员函数 merge() 以另一个具有相同类型元素的 list 容器作为参数。两个容器中的元素都必须是**升序**。参数 list 容器中的元素会被合并到当前的 list 容器中。合并后另一个容器就为空了。

list<int> lt1{1,2,3 };//必须为升序
    	list<int> lt2{ 8,9,10};//必须为升序
    	lt1.merge(lt2);
    	for (auto lt = lt1.begin(); lt != lt1.end(); lt++)
    	{
    		cout << *lt<<"  ";
    	}//最后输出的也是升序的

*  **sort（）排序函数**

>    sort() 函数模板定义在头文件 algorithm 中，要求使用随机访问迭代器。但 list 容器并不提供随机访问迭代器(没有lt.begin()+2这样的操作）只提供双向迭代器，因此不能对 list 中的元素使用 sort() 算法。但是，还是可以进行元素排序，因为 list 模板定义了自己的 sort() 函数。

lt.sort();   //从小到大排序

*  **splice（）合并函数**

>   上面提到的merge（）函数虽可以合并，但是合并后进行了排序。有的时候不希望改变原有元素的位置，只想首尾相接。

list<int> lt1{1,5,6 };  //不一定要是升序
    	list<int> lt2{ 8,3,10};
    	lt1.splice(lt1.end(), lt2);   //将lt2插入到lt1后
    	lt1.splice(lt1.begin(), lt2); //将lt2插入到lt1前

--------------------

参考网页：[http://c.biancheng.net/stl/sequence\_container/][http_c.biancheng.net_stl_sequence_container]

[70]: /images/20220509/ed3f680c34604e279d46000a3e5dabcf.png
[70 1]: /images/20220509/650765492d6f426db4e0963b91cb0fde.png
[70 2]: /images/20220509/a1efe0703de9406fb01e80c97fd41a1b.png
[http_c.biancheng.net_stl_sequence_container]: http://c.biancheng.net/stl/sequence_container/