C++中list的使用

---

一、 list简介

C++ STL（Standard Template Library）中的list是一个双向链表容器，它允许在序列中的任何位置进行快速插入和删除操作。list容器中的元素不是连续存储的，而是由节点（通常包含数据和指向下一个及前一个元素的指针）组成，因此它不需要在插入或删除元素时移动其他元素。

以下是list的一些基本特点和用法：

特点

1. 双向链表：每个元素都包含指向其前一个和后一个元素的指针，这使得在任何位置进行插入和删除操作都非常高效。
2. 动态大小：list的大小可以动态变化，可以根据需要添加或删除元素。
3. 非连续存储：与数组或向量不同，list的元素不是连续存储在内存中的。

基本用法

包含头文件

使用list需要包含<list>头文件。

#include <list>
1

创建list

可以创建一个空的list，也可以在创建时初始化它。

std::list<int> myList; // 创建一个空的int类型的list
std::list<int> myList = {1, 2, 3, 4, 5}; // 创建一个包含5个元素的list
1
2

添加元素

可以使用push_back、push_front、insert等方法向list中添加元素。

myList.push_back(6); // 在list的末尾添加元素6
myList.push_front(0); // 在list的开头添加元素0
myList.insert(myList.begin(), 7); // 在list的开头插入元素7
1
2
3

删除元素

可以使用pop_back、pop_front、erase等方法从list中删除元素。

myList.pop_back(); // 删除list的最后一个元素
myList.pop_front(); // 删除list的第一个元素
myList.erase(myList.begin()); // 删除list的第一个元素（使用迭代器）
1
2
3

遍历元素

可以使用迭代器或范围基于的for循环来遍历list中的元素。

// 使用迭代器遍历
for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
    std::cout << *it << " ";
}

// 使用范围基于的for循环遍历
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
1
2
3
4
5
6
7
8
9

查找元素

可以使用find方法来查找list中的元素。

auto it = std::find(myList.begin(), myList.end(), 3); // 查找值为3的元素
if (it != myList.end()) {
    std::cout << "Found element: " << *it << std::endl;
} else {
    std::cout << "Element not found" << std::endl;
}
1
2
3
4
5
6

这只是list容器的一些基本用法，它还提供了许多其他功能和方法，如排序、合并、分割等，可以通过查阅C++ STL文档来了解更多详情。

二、 构造函数

1. 默认构造函数

这个构造函数用于创建一个空的 std::list 容器。它可以接受一个可选的分配器参数，用于指定内存分配策略。

list() //默认构造函数
std::list<int> ls; //建立一个空的list容器
1
2

2. 拷贝构造

拷贝构造用于创建一个与已存在的std::list容器x相同的副本，它会将 x中的所有元素拷贝到新的容器中。

list (const list& x) //拷贝构造
std::list<int> A={1,2,3,4};
std::list<int> copy(A);
1
2
3

3. 迭代器区间初始化

这个构造函数使用迭代器范围 [first, last) 中的元素创建一个 std::list 容器。这使你可以通过一个迭代器范围来初始化容器。同样，它也接受一个可选的分配器参数。

list (InputIterator first, InputIterator last) //用[first, last)区间中的元素构造list
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> List(vec.begin(), vec.end());
 // 从迭代器范围内的元素创建 std::list 容器
1
2
3
4

4. 插入n个值为x的数据

这个构造函数用于创建一个包含 n 个元素的 std::list 容器，并将这些元素初始化为 val。你可以通过传递不同的 val 值来创建一个包含相同值的容器。同样，也可以传递一个可选的分配器参数。

list (size_type n, const value_type& val = value_type()) //构造的list中包含n个值为val的元素
std::list<int> A(5,10);  //构建一个有五个元素，每个元素都是10的容器
1
2

5. 代码示例

#include <iostream>
#include <list>

int main()
{
    std::list<int> first;                                // 默认构造函数
    std::list<int> second(4, 100);                       // 四个元素都是100
    std::list<int> third(second.begin(), second.end());  // 迭代器区间构造
    std::list<int> fourth(third);                       //拷贝构造

    //迭代器构造函数也可以用于从数组构造：
    int myints[] = { 16,2,77,29 };
    std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));

    std::cout << "The contents of fifth are: ";
    for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
        std::cout << *it << ' ';

    std::cout << '\n';

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

三、 容量和元素访问

1. empty()

判断容器中元素是否为空，为空返回true否则false。

2. size()

返回容器中元素个数。

3. max_size()

返回列表容器可以容纳的最大元素数。

3. back()

返回对列表容器中最后一个元素的引用。
与成员list:：end不同，该函数返回的迭代器刚好经过该元素，它返回的是直接引用。
在空容器上调用此函数会导致未定义的行为。

4. front()

返回对列表容器中第一个元素的引用。
与向同一元素返回迭代器的成员list:：begin不同，此函数返回一个直接引用。
在空容器上调用此函数会导致未定义的行为。

5. 代码示例

#include <iostream>
#include <list>

int main()
{
    std::list<int> Mylist;
    Mylist.push_back(1);//在最后插入一个元素，后面会详细说明
    Mylist.push_back(2);
    Mylist.push_back(3);
    Mylist.push_back(4);
    std::cout << "Mylist中元素个数为：" << Mylist.size() << std::endl;
    std::cout << "Mylist是否为空：" << Mylist.empty() << std::endl;
    std::cout << "Mylist首元素为：" << Mylist.front() << std::endl;
    std::cout << "Mylist最后一个元素为：" << Mylist.back() << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

四、 增删查改

1. push_back()

在列表容器的末尾，在其当前最后一个元素之后添加一个新元素。

#include <iostream>
#include <list>

int main()
{
    std::list<int> Mylist;
    Mylist.push_back(1);
    Mylist.push_back(2);
    //输出list中的元素
    for (const auto e : Mylist)
        std::cout << e << " ";
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. push_front()

在列表的开头，即当前第一个元素之前插入一个新元素。

#include <iostream>
#include <list>

int main()
{
    std::list<int> Mylist;
    Mylist.push_back(1);
    Mylist.push_back(2);
    //输出list中的元素
    for (const auto e : Mylist)
        std::cout << e << " ";
    std::cout << std::endl;

    Mylist.push_front(3);
    Mylist.push_front(4);
    for (const auto e : Mylist)
        std::cout << e << " ";
    std::cout << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. emplace_back()

用法和push_back一样，作用也一样，就是在特定情况下效率比push_back高
这里不详细介绍他的原理了，后面会专门写一篇有关右值引用的博客，在内篇文章中我们会探讨这个问题。

1. 在列表末尾的当前最后一个元素的正后方插入一个新元素。这个新元素是使用args作为其构造参数就地构造的。
2. 该元素是通过调用allocator_traits:：construct和转发的args就地构造的。
3. 存在一个类似的成员函数push_back，它可以将现有对象复制或移动到容器中

4. emplace_front()

用法和push_front一样，作用也一样，就是在特定情况下效率比push_front高
这里不详细介绍他的原理了，后面会专门写一篇有关右值引用的博客，在内篇文章中我们会探讨这个问题。

1. 在列表的开头，即当前第一个元素之前插入一个新元素。这个新元素是使用args作为其构造参数就地构造的。
2. 该元素是通过调用allocator_traits:：construct和转发的args就地构造的。
3. 存在一个类似的成员函数push_front，它将现有对象复制或移动到容器中。

5. pop_back()

删除list容器中的最后一个元素。

#include <iostream>
#include <list>

int main()
{
    std::list<int> Mylist;
    Mylist.push_back(1);
    Mylist.push_back(2);
    Mylist.push_back(3);
    Mylist.push_back(4);
    Mylist.pop_back();
    //输出list中的元素
    for (const auto e : Mylist)
        std::cout << e << " ";
    std::cout << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6. pop_front()

删除list容器中的第一个元素

#include <iostream>
#include <list>
int main()
{
    std::list<int> Mylist;
    Mylist.push_back(1);
    Mylist.push_back(2);
    Mylist.push_back(3);
    Mylist.push_back(4);
    Mylist.pop_front();
    Mylist.pop_front();
    //输出list中的元素
    for (const auto e : Mylist)
        std::cout << e << " ";
    std::cout << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

7. insert()

1. 通过在指定位置的元素之前插入新元素来扩展容器。这有效地将list大小增加了插入的元素数量。
2. 与其他标准序列容器不同，list和forward_list对象经过专门设计，可以有效地在任何位置插入和删除元素，即使是在序列的中间。
3. 参数确定插入了多少个元素以及将它们初始化为哪些值：

#include <iostream>
#include <list>
#include <vector>

int main()
{
    std::list<int> mylist;
    std::list<int>::iterator it;

    // set some initial values:
    for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5

    it = mylist.begin();
    ++it;       // it points now to number 2           ^

    mylist.insert(it, 10);                        // 1 10 2 3 4 5

    // "it" still points to number 2                      ^
    mylist.insert(it, 2, 20);                      // 1 10 20 20 2 3 4 5

    --it;       // it points now to the second 20            ^

    std::vector<int> myvector(2, 30);
    mylist.insert(it, myvector.begin(), myvector.end());
    // 1 10 20 30 30 20 2 3 4 5
    //               ^
    std::cout << "mylist contains:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

8. erase()

1. 从列表容器中删除单个元素（位置）或一系列元素（[第一个，最后一个））。这有效地减少了容器的大小，减少了被销毁的元素的数量。
2. 与其他标准序列容器不同，list和forward_list对象经过专门设计，可以有效地在任何位置插入和删除元素，即使是在序列的中间。

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;
    std::list<int>::iterator it1, it2;

    // set some values:
    for (int i = 1; i < 10; ++i) mylist.push_back(i * 10);

    // 10 20 30 40 50 60 70 80 90
    it1 = it2 = mylist.begin(); // ^^
    advance(it2, 6);            // ^                 ^
    ++it1;                      //    ^              ^

    it1 = mylist.erase(it1);   // 10 30 40 50 60 70 80 90
    //    ^           ^

    it2 = mylist.erase(it2);   // 10 30 40 50 60 80 90
    //    ^           ^

    ++it1;                      //       ^        ^
    --it2;                      //       ^     ^

    mylist.erase(it1, it2);     // 10 30 60 80 90
    //        ^

    std::cout << "mylist contains:";
    for (it1 = mylist.begin(); it1 != mylist.end(); ++it1)
        std::cout << ' ' << *it1;
    std::cout << '\n';

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

9. clear()

从列表容器中删除所有元素（已销毁），并使容器的大小为0。

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;
    // set some values:
    for (int i = 1; i < 10; ++i) mylist.push_back(i * 10);
    // 10 20 30 40 50 60 70 80 90
    std::cout << mylist.size() << std::endl;
    mylist.clear();
    std::cout << mylist.size() << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

10. swap

1. 用x的内容交换容器的内容，x是另一个相同类型的列表。尺寸可能不同。
2. 在调用该成员函数之后，该容器中的元素是调用之前在x中的元素，而x的元素是在此中的元素。所有迭代器、引用和指针对于交换的对象仍然有效。
3. 请注意，存在一个具有相同名称的非成员函数swap，该函数使用与该成员函数类似的优化重载该算法。
4. 容器分配器是否也被交换没有定义，除非在这种情况下，适当的分配器特性明确指示它们应该传播。

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist1,mylist2;
    // set some values:
    for (int i = 1; i < 10; ++i)
    {
        mylist1.push_back(i * 10);// 10 20 30 40 50 60 70 80 90
        mylist2.push_back(i);//1 2 3 4 5 6 7 8 9 
    }
    for (auto e : mylist1)
        std::cout << e << " ";
    std::cout << std::endl;
    for (auto e : mylist2)
        std::cout << e << " ";
    std::cout << std::endl;

    mylist1.swap(mylist2);//交换元素
    for (auto e : mylist1)
        std::cout << e << " ";
    std::cout << std::endl;
    for (auto e : mylist2)
        std::cout << e << " ";
    std::cout << std::endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

五、迭代器

1. begin()

返回一个迭代器，该迭代器指向list容器中的第一个元素。
请注意，与返回对第一个元素的引用的member-list:：front不同，此函数返回指向它的双向迭代器。
如果容器为空，则不应该解引用返回的迭代器值。

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist1;
    // 1 2 3  4 5
    for (int i = 1; i <= 5; i++) mylist1.push_back(i);
    std::list<int>::iterator it = mylist1.begin();
    std::cout << *it << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. end()

返回一个迭代器，该迭代器指向list容器中最后一个元素的下一个元素。
因此它不指向任何元素，不能执行解引用操作。
由于标准库的函数所使用的范围不包括其end迭代器所指向的元素，因此此函数经常与list:：begin结合使用，以指定一个包括容器中所有元素的范围。
如果容器为空，此函数将返回与list:：begin相同的值。

因为end返回的迭代器指向最后一个元素的下一个元素，所以不能解引用，那只需要让这个迭代器先--再解引用，那得到的就是最后一个元素

#include <list>

int main()
{
    std::list<int> mylist1;
    // 1 2 3  4 5
    for (int i = 1; i <= 5; i++) mylist1.push_back(i);
    std::list<int>::iterator it = mylist1.end();
    std::cout << *(--it) << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

3. rbegin()

返回一个反向迭代器，指向容器中的最后一个元素（即其反向开头）。
反向迭代器向后迭代：增加它们会将它们移向容器的开头。
rbegin指向成员端将指向的元素之前的元素。
请注意，与返回对同一元素的引用的member-list:：back不同，此函数返回一个反向双向迭代器。

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist1;
    // 1 2 3  4 5
    for (int i = 1; i <= 5; i++) mylist1.push_back(i);
    std::list<int>::reverse_iterator it = mylist1.rbegin();
    std::cout << *(it) << std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. rend()

返回一个反向迭代器，该迭代器指向列表容器中第一个元素之前的理论元素（被视为其反向端）。
list:：rbegin和list:：rend之间的范围包含容器的所有元素（按相反顺序）。

因为rend返回的迭代器指向第一个元素的前一个元素，所以不能解引用，那只需要让这个迭代器先--再解引用，那得到的就是第一个元素

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist1;
    // 1 2 3  4 5
    for (int i = 1; i <= 5; i++) mylist1.push_back(i);
    std::list<int>::reverse_iterator it = mylist1.rend();
    std::cout << *(--it) << std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

5. cbegin()、cend()、crbegin()、crend()

cbegin()、cend()、crbegin()、crend()所代表的含义分别和begin()、end()、rbegin()、rend()一样，唯一的区别是前者是const版本的，只能读，不能修改，而后面的读写都可以。
以begin()和cbegin()为例：
可以看到begin是可以修改的，（it）++之后再输出it就从1变成2了。

cbegin直接报错了。

六、 操作函数

1. splice()

splice函数用于两个list容器之间的拼接，其有三种拼接方式：

1. 将整个容器拼接到另一个容器的指定迭代器位置。
2. 将容器当中的某一个数据拼接到另一个容器的指定迭代器位置。
3. 将容器指定迭代器区间的数据拼接到另一个容器的指定迭代器位置。

#include <iostream>
#include <list>
using namespace std;

int main()
{
	list<int> lt1(4, 2);
	list<int> lt2(4, 6);
	lt1.splice(lt1.begin(), lt2); 
	//将容器lt2拼接到容器lt1的开头
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2 

	list<int> lt3(4, 2);
	list<int> lt4(4, 6);
	lt3.splice(lt3.begin(), lt4, lt4.begin()); 
	//将容器lt4的第一个数据拼接到容器lt3的开头
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl; //6 2 2 2 2 

	list<int> lt5(4, 2);
	list<int> lt6(4, 6);
	lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); 
	//将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
	for (auto e : lt5)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2. unique()

不带参数的版本（1）从容器中每个连续的相等元素组中删除除第一个元素外的所有元素。
请注意，只有当一个元素与紧挨在它前面的元素进行比较时，它才会从列表容器中删除。因此，此函数对排序列表特别有用。

#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist1;
    mylist1.push_back(4);
    for (int i = 1; i <= 5; i++) mylist1.push_back(5);
    mylist1.push_back(4);
    for (int i = 1; i <= 5; i++) mylist1.push_back(5);
    mylist1.unique();
    for (auto e : mylist1)
        std::cout << e << " ";

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3. remove()

从容器中删除所有与值相等的元素。这将调用这些对象的析构函数，并按删除的元素数量减少容器大小。
与成员函数list:：erase（使用迭代器）按位置擦除元素不同，此函数（list:：remove）按元素的值删除元素。

#include <iostream>
#include <list>

int main() {
    std::list<int> myList1 = { 1,2,3,4,5,3 };
    myList1.remove(3);
    for (int num : myList1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4. remove_if()

这个成员函数用于根据给定的谓词函数 pred 移除满足特定条件的元素。
谓词函数 pred 接受一个参数（参数类型同*迭代器返回的类型相同）并返回一个布尔值，用于判断是否需要移除该元素。如果谓词返回 true，则该元素将被移除。
从容器中删除Predicate pred返回true的所有元素。这将调用这些对象的析构函数，并通过移除的元素数量来减少容器大小。
函数为每个元素调用pred（*i）（其中i是该元素的迭代器）。列表中返回true的任何元素都将从容器中删除。

#include <iostream>
#include <list>

bool judge(int num)
{
    return num % 2 == 0;
}
int main() {
    std::list<int> myList1 = { 1,2,3,4,5,6,7,8,9 };
    myList1.remove_if(judge);
    for (int num : myList1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5. merge()

C++标准库中的std::list的merge函数要求两个列表在合并前都已经是排序的。如果两个列表不是有序的，那么merge函数的结果将是不确定的，因为它会按照元素的大小顺序来合并两个列表。

1. 第一个成员函数用于将另一个列表 x 合并到当前列表中，合并后的列表会按照升序排列。

#include <iostream>
#include <list>

int main() {
    std::list<int> myList1 = { 1, 3, 5 };
    std::list<int> myList2 = { 2, 4, 6 };

    myList1.merge(myList2); // 将 myList2 合并到 myList1 中

    std::cout << "myList1 after merge: ";
    for (int num : myList1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 第二个成员函数不仅可以将两个list合并，还能指明排序方法。上面是升序，我们可以弄成降序

6. sort()

对列表中的元素进行排序，改变它们在容器中的位置。

1. 默认升序

int main() {
    std::list<int> myList1 = { 3,1,5,4,2,3 };
    myList1.sort();
    for (int num : myList1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10

2. 可以指定如何排序，比如这里我们让它降序
   

7 . reserve()

颠倒列表容器中元素的顺序

#include <iostream>
#include <list>

int main() {
    std::list<int> myList1 = { 1,2,3,4,5 };
    myList1.reverse();
    for (int num : myList1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

七、 sort排序效率测评

list容器虽然有一个排序的sort函数，但我们一般是不会使用的，因为效率太低了。
现在我们使用下面的代码来测试vector和list排序的性能，看一下结果。
现在产生1000000个随机数，分别放到vector和list中，然后list调自己提供的sort，vector调库里面的sort，我们来对比一下它们的运行时间：

多运行几次，可以发现虽然每次时间都不太一样，但是vector的排序总是比list快很多。

void test_op1()
{
	srand(time(0));
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	list<int> lt1;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		lt1.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());// vector排序
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();//list排序
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

既然如此，那我们就比点有可比性的。我们先分别向两个list中都插入1000000个随机数。然后一个是先把list的数据拷贝到vector中，利用vector排序完之后再拷贝回list中，另一个是直接调用list的成员函数sort进行排序，比比谁快。
可以看到还是前者快，所以一般不用list的sort因为效率太低了。

void test_op1()
{
	srand(time(0));
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);
	list<int> lt1;
	list<int> lt2;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt2.push_back(e);
		lt1.push_back(e);
	}
	// 拷贝到vector排序，排完以后再拷贝回来
	int begin1 = clock();
	// 先拷贝到vector
	for (auto e : lt1)
	{
		v.push_back(e);
	}
	// 排序
	sort(v.begin(), v.end());
	// 拷贝回去
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}

	int end1 = clock();

	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

八、 list迭代器失效问题

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

当使用 std::list 进行删除操作时，可能会导致迭代器失效。如下：

int main() {
	std::list<int> myList = { 1, 2, 3, 4, 5 };

	auto it = myList.begin();
	++it; // Move the iterator to the second element

	myList.erase(it); // Erase the second element

	for (auto num : myList) {
		std::cout << num << " ";
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但如果此时再次*it就会出问题，这就是迭代器失效导致的。

在上面的示例中，当我们在第二个元素位置处使用 erase 函数删除元素后，迭代器 it 就会失效，因为它指向的元素已经被删除。如果我们尝试使用失效的迭代器，可能会导致未定义的行为。

要修正这个问题，可以使用 erase 函数的返回值，它会返回一个指向下一个有效元素的迭代器：

#include <iostream>
#include <list>

int main() {
	std::list<int> myList = { 1, 2, 3, 4, 5 };

	auto it = myList.begin();
	++it; // Move the iterator to the second element

	it = myList.erase(it); // Erase the second element and update the iterator

	for (auto num : myList) {
		std::cout << num << " ";
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17