C++ STL之list的使用

首先学习list，不妨我们先来看看文档中它是怎么说明的：

C++中 list 的官方文档网址是：list文档

1.list是什么?

中文翻译:

•  list是序列式容器，允许在序列内的任何位置进行插入和删除操作，并且该容器可以前后双向迭代。
•  list容器在底层被实现为双向链表；双向链表中的每个元素存储在不同且不相关的存储位置。每个节点是通过与指向它前面元素的指针和指向它后面元素的指针进行关联的。
•  list与 forward_list 非常相似：主要区别在于 forward_list 对象是单链表，因此它们只能向前迭代，以让其更小更高效。
•  与其他序列式容器（array、vector和deque）相比，list通常在拥有迭代器的容器内任何位置插入、提取和移动元素方面表现更好
•  与这些其他序列容器相比，list 和 forward_lists 的主要缺点是它们无法直接访问元素的位置；例如，要访问列表中的第六个元素，必须从已知位置（如开头或结尾）迭代到该位置，这在这些位置之间的距离上需要线性时间。它们还消耗一些额外的内存来保存与每个元素相关联的信息

可以看到list是模板，它可以接收任何类型。

2. list成员函数的使用

1. list的构造函数

list的构造函数如上：默认构造函数、迭代器构造函数等等，list有多种初始化的方式：

1. 默认构造（空 list）：先创建空链表，后续手动添加元素 , 适合一开始不知道要存什么数据，后续动态添加的场景。

    list<int> lst;  

2. 填充构造：直接创建含 N 个相同元素的链表 , 适合需要“批量初始化相同值”的场景（比如初始化一个含5个0的链表）。

    list<int> lst(4, 3);  // → [3, 3, 3, 3]

3. 范围构造：用其他容器（如 vector）的元素初始化 list , 适合需要“复用其他容器数据”的场景（比如把 vector 里的元素转存到 list）。

//先创建一个 vector，作为数据源
vector<string> vec = {"apple", "banana", "orange"};

//范围构造：用 vector 的迭代器范围 [vec.begin(), vec.end()) 初始化 list
list<string> lst(vec.begin(), vec.end());  // → ["apple", "banana", "orange"]

4. 拷贝构造：复制另一个 list 的所有元素 , 适合需要“创建一个与现有 list 完全相同的副本”的场景（比如备份数据）。

list<double> lt1 = {1.5, 2.8, 3.2};  // → [1.5, 2.8, 3.2]

// 4. 拷贝构造：创建 lt1 的副本
list<double> lt2(lt1);  // lt2 和 lt1 内容完全相同

// 修改副本，验证原始 list 不受影响（拷贝是独立的）
lt2.pop_back();  // 删除副本的最后一个元素 → [1.5, 2.8]

2. list的遍历方式

1. 迭代器遍历

void test_list2()
{
    vector<int> v = { 1,2,3,4,5 };
	list<int> lt4(v.begin(), v.end());
    list<int>::iterator it4 = lt4.begin();
    while(it4!=lt4.end())
    {
        cout<<*it4<<" "<<endl;
        it4++;
    }
    cout<<endl;
}

输出结果:

 1 2 3 4 5

2. 范围for遍历

void test_list3()
{
	vector<int> v = { 1,2,3,4,5 };
	list<int> lt4(v.begin(), v.end());
	for(auto e:lt4)
    {
        cout<<e<<" ";
    }
	cout << endl;
}

输出结果:

 1 2 3 4 5

因为list不支持随机访问，所以不存在[]+下标进行遍历

1. 这是由  list  的 底层结构（双向链表）决定的。
2. 在 C++ STL 中， list  是双向链表的封装，其元素在内存中是分散存储的——每个元素（节点）包含数据和两个指针（分别指向前一个节点和后一个节点），而非像  vector  那样在连续的内存块中存储。
3. 这种结构导致它无法像数组或  vector  那样通过“下标”直接计算出元素的内存地址。例如，若要访问  list  的第  i  个元素，程序必须从链表的头部（或尾部）开始，通过指针逐个遍历  i  次才能定位到目标元素，这个过程的时间复杂度是 O(n)，远不如  vector  下标访问的 O(1) 高效。

因此，为了明确其设计特性（不支持高效随机访问），C++ 标准没有为  list  提供下标运算符  []  或  at()  成员函数，以此避免开发者误用它进行低效的随机访问操作。

3. size

size 作为一个成员函数，作用是返回链表中当前元素的个数。用于快速获取链表中存储了多少个元素，比如判断链表是否为空（ if (list.size() == 0) ）、遍历前确认元素数量等。

4. assign

assign 成员函数核心是用新内容替换链表当前所有元素，有两种重载形式：

• range (1)：范围赋值

 template <class InputIterator> void assign (InputIterator first, InputIterator last); 

作用是用其他容器的迭代器范围  [first, last)  内的元素，替换链表现有内容。例如可以用  vector 、 array  甚至另一个  list  的元素来赋值。

• fill (2)：填充赋值

 void assign (size_type n, const value_type& val); 

作用是创建  n  个值为  val  的元素，替换链表现有内容。比如  lst.assign(3, 5)  会让链表变成 3 个“5”。

lt3.assign(5,3);//重新给值
for(auto e:lt3)
{
    cout<<e<<" ";
}
cout<<endl;

两者的共性是先清空链表原有元素，再写入新内容，常用于批量替换链表数据的场景。

5. push_back和push_front

void test_list4()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    
    lt.push_front(10);
    lt.push_front(20);
    lt.push_front(30);
    lt.push_front(40);
    for(auto e:lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

可以看到成功的进行了尾插和头插

6. pop_back和pop_front

void test_list5()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    
    lt.push_front(10);
    lt.push_front(20);
    lt.push_front(30);
    lt.push_front(40);
    for(auto e:lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    
    lt.pop_back();//删除需要保证有数据
    lt.pop_back();
    lt.pop_back();
    lt.pop_back();
    lt.pop_front();
    for(auto e:lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

可以看到成功的进行了尾删和头删

7. insert

 insert  成员函数核心作用是在链表的“指定位置前”插入元素，是  list  实现“任意位置高效插入”的核心接口，有三种重载形式：

• single element (1)：插入单个元素

 iterator insert (iterator position, const value_type& val); 

int main() {
    list<int> lst = {1, 3, 4};
    auto it = lst.begin();  // 指向第一个元素 1
    it = lst.insert(it, 2); // 在 1 前面插入 2，lst 变为 [2,1,3,4]
    for (int num : lst) {
        cout << num << " "; // 输出：2 1 3 4
    }
    return 0;
}

作用是在迭代器  position  指向的元素前面插入一个值为  val  的元素，返回新插入元素的迭代器。

• fill (2)：插入多个相同元素

 void insert (iterator position, size_type n, const value_type& val); 

int main() {
    list<char> lst = {'a', 'c'};
    auto it = lst.end();    // 指向末尾（c 的后面）
    lst.insert(it, 2, 'b'); // 在末尾插入 2 个 'b'，lst 变为 [a,b,b,c]
    for (char ch : lst) {
        cout << ch << " "; // 输出：a b b c
    }
    return 0;
}

作用是在  position  前插入  n  个值为  val  的元素。

• range (3)：插入其他容器的元素范围

 template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last); 

int main() {
    list<int> lst = {1, 4};
    vector<int> vec = {2, 3};
    auto it = ++lst.begin(); // 指向 4
    lst.insert(it, vec.begin(), vec.end()); // 在 4 前插入 vec 的元素，lst 变为 [1,2,3,4]
    for (int num : lst) {
        cout << num << " "; // 输出：1 2 3 4
    }
    return 0;
}

作用是在  position  前插入另一个容器（如  vector 、 array  等）的迭代器范围  [first, last)  内的所有元素。
 
核心特点：

• - 插入位置灵活：可在链表的任意位置（头、尾、中间）插入，时间复杂度为 O(1)（只要已获取目标位置的迭代器）。
• - 会扩展链表：插入后链表的  size  会增加，增加的数量等于插入的元素个数。
• - 是  list  的核心优势体现：相比  vector  等容器， list  在任意位置插入的效率极高，这也是它适合“频繁动态增删”场景的关键原因。

补充:

void test_list6()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::iterator pos = find(lt.begin(),lt.end(),2);
    if(pos!=lt.end())
    {
        //找到
        lt.insert(pos,20);
    }
    //这里pos是否会失效呢？不会失效
    //原因是list和vector的结构不同
    //因为底层空间是物理连续数组。可能扩容，导致野指针问题，不扩容，挪动数据，也导致pos意义变了
    //list insert不会失效，因为list是一个个独立节点，2前面插入数据是新增节点，pos还是指向2这个节点的，所以不会失效
}

可以看到已经成功插入

有一个问题：这里的pos会不会像vector一样会失效呢?

• 答案是不会，原因是list和vector的结构不同，vector因为底层是物理连续数组，插入时可能会扩容，导致野指针问题，不扩容，挪动数据也导致pos的失效遍历，而对于list，list的每一个节点不一定连续，插入时不需要挪动数据，insert后不会失效因为list是一个个独立的节点，这里在2的前面插入数据是插入新增的节点，pos还是指向2这个节点的，所以不会失效

8. erase

erase  函数的作用是从  list  容器中删除元素，可以删除单个元素，也可以删除一个范围内的元素。删除后，容器的大小会相应减少（减少的数量等于被删除元素的个数），并且被删除的元素会被销毁。

函数重载形式:

iterator erase (iterator position); 

• 功能：删除由迭代器  position  指向的单个元素。
• 返回值：返回一个迭代器，指向被删除元素的下一个元素。这样设计是为了在删除元素后，能继续通过迭代器遍历容器（因为被删除元素的迭代器会失效，需要用返回的新迭代器继续操作）。

iterator erase (iterator first, iterator last); 

• 功能：删除从迭代器  first （包含）到  iterator last （不包含）这个范围内的所有元素。
• 返回值：同样返回指向被删除范围之后的第一个元素的迭代器。

和其他标准序列容器（比如 std::vector 、 std::array  等）不同， list （以及 forward_list ）专门被设计为在序列的任何位置（包括中间位置）插入和删除元素都很高效。这是因为 list  是基于双向链表（ forward_list  是单向链表）实现的，链表结构在插入、删除元素时，只需要修改相邻节点的指针，不需要像数组那样移动大量元素，所以效率很高。

void test_list7()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    list<int>::iterator pos = find(lt.begin(),lt.end(),2);
    if(pos!=lt.end())
    {
        //找到
        lt.erase(pos);
    }
    //erase这里会失效，因为pos指向的节点已经被释放了，出现野指针
    cout<<*pos<<endl;
    *pos = 100;
}

可以看到我们erase时不用一个迭代器来接收时报错了，原因是erase时这里pos会失效，因为pos指向的节点已经被释放了，出现野指针

当我们用pos来接收时：

这里说明了erase返回的迭代器是指向删除节点的下一个节点

9. clear

clear  函数的功能是清空  list  容器中的所有元素，这些被删除的元素会被销毁，最终容器的大小变为 0。clear  可以看作是 erase  函数的一种特殊情况，即删除 list  中从第一个元素到最后一个元素的所有元素（等价于 erase(begin(), end()) ）。

void test_list8()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.clear();
}

可以看到已经清空

那么我们知道list是带头双向循环链表，那么头节点被删除了吗？

答案是没有，我们看下面的测试：

void test_list8()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.clear();
    //但是头节点没有清，还可以插入
    lt.push_back(10);
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;   
}

可以看到头节点没有清楚，这里我们还能正常插入

10. swap

 swap  函数用于交换两个同类型  list  容器的内容。交换后，当前容器的元素变为另一个容器  x  之前的元素， x  的元素变为当前容器之前的元素。两个容器的大小可以不同。

void swap (list& x); 

• 参数为另一个同类型的  list  引用，返回值为  void 。

 关键特性:

1. 迭代器、引用和指针的有效性：交换后，两个容器的迭代器、引用和指针仍然有效，且指向交换后对应容器中的元素。
2. 非成员函数版本：存在同名的非成员函数  swap ，其行为与该成员函数一致，且经过优化。
3. 分配器的交换：除非分配器特性明确指示需要传播，否则容器的分配器是否交换是未定义的。
    

void test_list9()
{
	list<int> lt;
	list<int> lt1;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt1.push_back(10);
	lt1.push_back(20);
	lt1.push_back(30);
	lt1.push_back(40);
	lt.swap(lt1);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}

可以看到已经交换成功了

11. sort

sort  函数的作用是对  list  容器中的元素进行排序，会改变元素在容器内的位置。整个排序操作不会涉及元素对象的构造、析构或者拷贝，只是在 list  容器内部移动元素的位置。
 
函数重载形式:

void sort(); 

• 功能：使用元素的默认比较方式（通常是  operator< ，即按升序）对  list  中的元素进行排序。

template <class Compare> void sort (Compare comp); 

• 功能：通过传入一个自定义的比较函数（或函数对象） comp ，按照自定义的规则对  list  中的元素进行排序。

void test_list10()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(30);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.sort();
    for(auto e : lt)
    {
        cout<<e<<" ";
    }//默认排升序
    //排降序
    greater<int> g;
    lt.sort(g);
    cout<<endl;
}

可以看到已经排好序，但是list里的sort效率低，一般很少用

效率测试对比：

这段代码通过对比  std::vector  和  std::list  的排序效率，得出以下结论：

• 容器选择与排序接口差异： std::vector  使用全局的  sort  算法（ sort(v.begin(), v.end()) ），而  std::list  因为其迭代器不支持随机访问，所以使用自身的成员函数  lt.sort() （全局  sort  算法无法用于  list ，如代码中注释的  sort(lt.begin(), lt.end())  会报错）。
• 效率表现：在测试数据量  N = 10000  时， list  的排序耗时（17 单位时间）比  vector  的排序耗时（31 单位时间）更短。这体现了  std::list  自身的  sort  成员函数在其链表结构上的优化效果，也反映出不同容器的底层结构（ vector  是动态数组， list  是双向链表）对排序效率的影响。

12. unique

即”删除”序列中所有相邻的重复元素(只保留一个)。此处的删除，并不是真的删除，而是指重复元素的位置被不重复的元素给占领了(详细情况，下面会讲)。由于它”删除”的是相邻的重复元素，所以在使用unique函数之前，一般都会将目标序列进行排序。

void test_list11()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(1);
    lt.push_back(4);
    lt.push_back(30);
    lt.push_back(4);
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
    lt.sort();
    lt.unique();//去重
    for(auto e : lt)
    {
        cout<<e<<" ";
    }
    cout<<endl;
}

可以看到已经成功去重

13. remove

remove  函数用于从 list  容器中删除所有值等于指定 val  的元素。被删除的元素会调用析构函数，容器大小会减少被删除元素的数量。

void remove (const value_type& val); 

• 参数为要删除的元素值，返回值为  void 。

 与 erase 函数的区别:

函数	删除依据	操作方式
erase	元素的位置（迭代器）	通过迭代器指定位置或范围删除
remove	元素的值	通过值匹配删除所有相等元素

void test_list12()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	lt.remove(2);
	lt.remove(4);

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

可以看到移除成功

3. 容器的迭代器的分类

使用功能的角度：

• 正向、反向、const正向、const反向

容器底层结构的角度：

• 单链表迭代器/哈希表迭代器是单向，只能用++
• 双向链表迭代器/map迭代器是双向，它们能++/–
• string/vector/deque迭代器/map迭代器是随机，支持随机访问，它们能用++/–/+/-等

struct input iterator taa {};//只写迭代器
struct output iterator taa {};//只读迭代器
struct forward iterator tag : public input iterator tag {};//单向迭代器
struct bidirectional_iterator_tag : public forward iterator tag {};//双向迭代器
struct random access_iterator_tag : public bidirectional iterator_tag {};//随机迭代器

可以看到继承关系，单向迭代器也是只写迭代器，双向迭代器也是单向迭代器，随机迭代器也是双向迭代器

sort要用需要满足随机迭代器才能使用：

reverse要满足是双向链表迭代器才能使用：

4. 容器算法迭代器之间的关系:

容器在不暴露容器底层实现细节情况下，提供了统一的方式去访问修改容器中存储的数据，这个方式就是迭代器，迭代器是容器和算法之间的胶合剂，一些算法想要去访问容器的成员就通过迭代器去访问

5. 总结:

本文系统介绍了C++标准库中的list容器，主要包含以下内容：1. list的基本特性：作为双向链表实现的序列容器，支持高效任意位置插入删除操作，但不支持随机访问；2. 常用操作：详细讲解了构造函数、遍历方式(size/iterator/range-for)、元素操作(push/pop/insert/erase/clear/swap)等核心功能；3. 特殊算法：包括sort、unique、remove等专用成员函数的使用方法及效率特点；4. 迭代器特性：分析了list迭代器失效问题，并与vector进行对比；5. 底层实现：解释了list作为带头双向循环链表的结构特点。通过代码示例和性能分析，阐明了list的适用场景和操作注意事项。