当前位置：首页 > news >正文

【c++丨STL】list的使用

news 2024/11/14 18:26:27

🌟🌟作者主页：ephemerals__

🌟🌟所属专栏：C++、STL

前言

之前我们已经学习了string、vector两个容器的使用方法及模拟实现，今天跟大家介绍list的使用方法。

到了这个阶段，我们应该认识到：在STL中，尽管容器各异，但同名接口的功能往往是相似的。因此，在我们掌握了少数几个容器的使用方法后，对于未曾接触过的其他容器，只要了解其底层数据结构，就基本能够上手使用它们。

list简介

list是STL中的一种容器，用于表示链表结构，底层实现是一个双向带头循环链表。如果你对双向带头循环链表不太了解，可以参阅这篇文章：

【数据结构】双向带头循环链表（c语言）（附源码）_c语言双向环链表初始化-CSDN博客

list在插入和删除操作方面非常高效，但在遍历和随机访问方面可能不如数组或者vector高效。因此，在选择容器时，需要根据具体的应用场景和需求进行权衡。

我们在使用list时，需要引头文件<list>，并且该容器定义在命名空间std当中。

list相关接口查阅：

list - C++ Reference

一、list的默认成员函数

list显示实现的默认成员函数有三个：分别是构造函数、析构函数和赋值重载。

构造函数(constructor)

c++11下，list共有六个构造函数，其中较为常用的有如下五种：

函数原型	功能说明
list();	无参构造（忽略空间配置器），创建一个空链表
list(size_type n, const value_type& val);	用n个val值构造一个list对象
list(const list& x);	拷贝构造，用一个对象构造另一个对象
list(InputIterator first,InputIterator last);	迭代器区间构造
list(initializer_list<value_type> il);	初始化器构造（大括号赋值）

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;//无参构造list<int> l2(5, 3);//n个val值构造list<int> l3(l2);//拷贝构造list<int> l4(l2.begin(), l2.end());//迭代器区间构造list<int> l5({ 1,2,3,4,5 });//初始化器构造cout << "l1: ";print(l1);cout << "l2: ";print(l2);cout << "l3: ";print(l3);cout << "l4: ";print(l4);cout << "l5: ";print(l5);return 0;
}

析构函数

释放动态分配的内存空间，在对象声明周期结束时自动调用。

赋值重载

将新内容分配给已经存在的容器，替换其当前内容，并相应地修改其大小。较为常用的赋值重载有两个：

函数原型	功能说明
list& operator= (const list& x);	两个list容器之间的赋值
list& operator= (initializer_list<value_type> il);	用初始化器给容器赋值

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;list<int> l2({ 1,2,3,4,5 });l1 = l2;//将l2赋值给l1print(l1);l1 = { 5,4,3,2,1 };//初始化器赋值print(l1);return 0;
}

二、list的迭代器接口

迭代器接口在string和vector中的使用方法大致相同，这里就不多介绍。

由于list元素的内存地址是不连续的，因此在迭代器的实现上，它与vector和string存在较大差异。我们将在list模拟实现的部分中对此进行深入探讨。

我们在这里重点讲一下迭代器的功能分类：

迭代器的功能分类

根据功能强弱，迭代器可以分为以下三种：

1. 单向迭代器：它仅支持在容器中进行从头到尾的遍历操作，重载了“++”运算符。

2. 双向迭代器：它支持从头到尾的遍历和从尾到头的遍历，重载了“++”和“--”运算符。

3. 随机迭代器：顾名思义，它不仅支持双向的遍历，还支持随机位置的访问，重载了“++”“--”“+”“-”等运算符。

这三种迭代器的功能是向下兼容的，即随机迭代器具有双向迭代器的功能，而双向迭代器具有单向迭代器的功能。

为什么会有这样的分类呢？其实这是由底层数据结构的实现导致的。

有些数据结构元素的内存地址连续，还能够支持双向遍历，并且遍历效率高，那么就可以支持随机迭代器（例如string、vector）；有些数据结构能够支持双向遍历，但是随机访问的效率低下，那就支持双向迭代器（例如list）；有些数据结构只能做到从前向后访问元素，那么就只能支持单向迭代器（例如单链表forward_list）。

所以我们在使用string、vector的迭代器时，可以使用“+”“-”操作符进行随机访问；而对于list，就只能通过“++”“--”来移动迭代器指向的位置。

三、list的容量接口

三个容量接口当中，前两个比较常用，我们重点介绍一下：

empty

empty函数用于判断该列表容器是否为空（即元素个数是否为0）。注意：该函数不会以任何方式修改容器。

size

size函数用于获取容器内元素的个数。

代码示例：

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l1;list<int> l2({ 1,2,3,4,5 });cout << "l1.size(): " << l1.size() << endl;cout << l1.empty() << endl;cout << "l2.size(): " << l2.size() << endl;cout << l2.empty() << endl;return 0;
}

四、list的元素访问接口

front和back

front函数返回对列表容器中第一个元素的引用，在空容器上调用此函数会导致未定义行为。

back函数返回对列表容器中最后一个元素的引用，在空容器上调用此函数会导致未定义行为。

代码示例：

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> l = { 1,2,3,4,5 };cout << l.front() << endl;cout << l.back() << endl;return 0;
}

相比vector的元素访问接口，list缺少了operator[ ]和at。是因为它们不能实现吗？当然不是，而是由于链表的特殊结构。如果实现了这两个接口，则使用时都需要遍历元素，效率的代价是很大的。

五、list的增删查改

在涉及增删查改操作的接口中，鉴于部分接口功能有所重复，博主仅挑选几个进行介绍。

push_front

push_front的功能是在容器的开头插入一个新元素，就在它当前的第一个元素之前。val的内容被复制（或移动）到插入的元素中。这有效地将容器大小增加了1。

pop_front

pop_front的功能是删除列表容器中的第一个元素，有效地将其大小减小1。这将破坏被删除的元素。

push_back

push_back的作用是在容器的末尾插入一个新元素。val的内容被复制（或移动）到新元素中。这有效地将容器大小增加了1。

pop_back

pop_back的作用是删除容器中的最后一个元素，有效地将容器大小减少一个。这将破坏被删除的元素。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1 = { 1,2,3,4,5 };cout << "原链表：";print(l1);l1.push_back(0);cout << "尾插：";print(l1);l1.push_front(0);cout << "头插：";print(l1);l1.pop_back();cout << "尾删：";print(l1);l1.pop_front();cout << "头删：";print(l1);return 0;
}

insert和erase

insert用于指定位置插入元素（需要使用迭代器指定）。该函数支持单个元素插入、n个val值插入、迭代器区间插入以及初始化器插入。操作结束后，该函数会返回新插入部分首元素的迭代器。

erase的作用是删除指定位置的元素或区间（需要使用迭代器指定）。操作结束后，函数返回删除部分的后一个位置的迭代器（防止迭代器失效）。

代码举例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 1,2,3,4,5 };l.insert(++l.begin(), 0);//在第二个位置插入一个元素print(l);l.erase(----l.end());//删除倒数第二个元素print(l);return 0;
}

swap

swap的功能是交换两个list容器的内容。当然，也有一个非成员函数的swap支持list的交换：

resize

resize的功能是调整容器的大小，使其包含n个元素。

如果n小于当前容器的大小，则内容将被减少到前n个元素，并删除超出的元素（销毁它们）

如果n大于当前容器的大小，则通过在末尾插入所需的元素来扩展内容，以达到n的大小。如果指定了val，则将新元素初始化为val的副本，否则调用其构造函数来初始化元素。

注意：这个函数通过插入或删除元素来改变容器的实际内容。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;list<int> l2;l1.resize(10);l2.resize(10, 5);print(l1);print(l2);list<int> l3({ 1,2,3,4,5 });print(l3);l3.resize(3);print(l3);return 0;
}

clear

clear的功能是从列表容器中删除所有元素，并将容器的大小保留为0。

find

与vector相同，list并没有用于查找的函数（find），要使用STL实现的通用find完成查找。该find函数定义在算法库<algorithm>当中，用于容器元素的查找。它接受两个迭代器参数和一个值参数，表示需要查找的区间和值。如果找到了，函数会返回指向第一个查找到的元素的迭代器，否则返回尾迭代器。

六、list的其他操作接口

除了传统的成员函数外，list还提供了一些特有的与插入删除相关的操作接口供我们使用。通过学习这些接口的使用方法，我们可以初步了解仿函数的相关知识。

splice

splice的功能是剪切。它能够将容器x / 容器x的某个元素 / 容器的一部分拷贝到原容器的指定位置，并且删除x中的相应元素。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1;list<int> l2({ 1,2,3,4,5 });l1.splice(l1.end(), l2);//将l2剪切到l1的末尾cout << "l1:";print(l1);cout << "l2:";print(l2);cout << endl;l2 = { 1,2,3,4,5 };l1.splice(l1.end(), l2, l2.begin());//将l2的首元素剪切到l1的末尾cout << "l1:";print(l1);cout << "l2:";print(l2);cout << endl;l2 = { 1,2,3,4,5 };l1.splice(l1.end(), l2, ++l2.begin(), --l2.end());//将l2掐头去尾的部分剪切到l1的末尾cout << "l1:";print(l1);cout << "l2:";print(l2);cout << endl;
}

remove

remove的功能是删除指定值的元素。

该函数从容器中删除比较结果为val的所有元素。这将调用这些对象的析构函数，并按删除元素的数量减少容器大小。

与erase不同，erase根据元素的位置删除元素，该函数根据元素的值删除元素。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 1,2,3,2,4,2,2,5 };print(l);l.remove(2);//删除所有的2print(l);return 0;
}

remove_if

remove_if用于删除list容器中满足特定条件的所有元素（特定条件由我们设定）。

该函数的参数是一个谓词（Predicate），如果容器中的某元素使得该谓词返回true，就将该元素删除。

这里简单介绍一下谓词：

之前我们在c语言部分使用qsort函数时，需要显示写一个比较函数用于确定排序的规则，谓词的功能就相当于我们显示写的比较函数。

谓词可以是以下几种形式之一：

1. 返回值为bool类型的函数指针

2. 仿函数（重载了函数调用操作符"()"的类，且该重载函数的返回值是bool类型）

3. Lambda表达式（c++11之后支持）

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

由于我们已经使用过函数指针，在接下来的代码示例当中，我们就尝试写一个仿函数来表示谓词。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}//仿函数
class f
{
public:bool operator()(int value){return value < 10;//将小于10的元素确定为true}
};int main()
{list<int> l = { 20,1,5,9,15,17 };l.remove_if(f());//删除所有小于10的元素print(l);return 0;
}

unique

unique函数的功能是删除所有与它的前一个元素满足某特定关系（特定关系可由我们设定）的元素。当然，该特定关系也是使用谓词表示。当我们没有显示设置特定关系，那么该特定关系就是两元素相等，也就是说我们没有传参时，函数的功能是删除所有相邻的重复元素（保留一个重复的元素，不会全部删除）。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1 = { 1,1,2,3,3,4,4,4,5,5,6,7,8,8 };//有序序列l1.unique();print(l1);list<int> l2 = { 2,2,1,2,2 };//无序序列，无法直接删除所有重复元素l2.unique();print(l2);return 0;
}

对于一个无序list序列，如果想要删除所有的重复元素，那么就需要先对list进行排序，然后再调用unique函数。

merge

merge的作用是合并两个有序链表，注意两个容器都应是有序状态。

这实际上删除了x中的所有元素，但不是销毁其中元素，而是将节点的指针互相连接，最后全部并入到原容器中。

该函数可以接受一个特定的谓词（comp）来执行元素之间的比较操作。

函数执行后，等价元素的相对位置不变（即原容器的在前，x的在后）。

如果x就是原容器，那么函数什么也不做。

代码示例：

#include <iostream>
#include <list>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l1 = { 1,3,5,7,9 };list<int> l2 = { 2,4,6,8,10 };l1.merge(l2);//合并cout << "l1:";print(l1);cout << "l2:";print(l2);return 0;
}

sort

sort用于排序list容器。当然，我们也可以传入一个谓词来确定排序规则，否则默认升序。

它的底层是一个优化的归并排序，意味着等价元素相对位置不变。

说起sort，博主在这里补充一点：与通用find函数相同，STL实现了一个通用的排序函数sort，参数是随机迭代器构成的迭代器区间，用于容器排序。

为什么要实现一个成员函数版的sort呢？直接使用算法库中的通用sort不行吗？刚才博主已经提到，list支持的是双向迭代器，并不具备随机迭代器的功能，所以list无法使用通用的sort函数完成排序，会发生报错。所以说list的成员函数当中，实现了一个排序函数sort。

接下来我们尝试使用该函数：

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 5,1,7,2,4,8,0,3 };l.sort();//排序print(l);return 0;
}

由于list底层是一个链表，所以对于排序这种需要重复调整元素顺序的算法，它的效率不是很高。如果要对list排序，建议将list的内容拷贝给vector，然后进行排序，最后拷贝回list。

reverse

reverse的功能是反转链表。

代码示例：

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;void print(list<int>& l)
{for (auto& e : l){cout << e << ' ';}cout << endl;
}int main()
{list<int> l = { 1,2,3,4,5 };l.reverse();//反转print(l);return 0;
}