C++中的List容器用法详解

C++中的List容器用法详解

在C++标准模板库（STL）中，list 是一种高效的、双向的、动态的容器，它允许在任何位置快速插入和删除元素。list 容器在内部通过节点来存储数据，每个节点都包含数据部分和指向前后节点的指针。这种设计使得 list 在进行插入和删除操作时具有较高的效率，因为只需要修改指针的指向，而不需要移动元素。

List 的特点

std::list 是 C++ 标准模板库（STL）中的一个容器，它具有以下特点：

1. 双向链表：list 是一个双向链表，每个元素都包含一个数据部分和两个指针，分别指向下一个元素和上一个元素。这种结构使得在链表的任何位置插入或删除元素都非常高效。

2. 动态大小：list 容器的大小是动态的，可以随着元素的添加和删除而自动调整。它不需要预先分配固定大小的内存。

3. 不连续内存分配：与数组或 std::vector 不同，list 的元素不存储在连续的内存块中。每个元素都是独立分配的，这使得 list 在处理大量数据时能够提供更好的内存利用率和性能。

4. 高效插入和删除：由于其链表结构，list 在任何位置插入或删除元素的时间复杂度都是常数时间（O(1)），这比 std::vector 在中间位置插入或删除元素的线性时间（O(n)）要快得多。

5. 不支持随机访问：由于 list 是一个链表，它不支持像数组或 std::vector 那样的随机访问。访问 list 中的元素需要从头开始遍历，因此其时间复杂度为线性时间（O(n)）。

6. 迭代器支持：list 提供了双向迭代器，这意味着可以从两个方向遍历 list，但不支持随机访问迭代器。

7. 内存管理：list 的内存管理是自动的，当元素被插入时，list 会自动分配内存；当元素被删除时，list 会自动释放内存。

8. 不支持直接访问：不能通过索引直接访问 list 中的元素，必须使用迭代器。

9. 不支持 at() 方法：list 不提供 at() 方法来访问元素，因为这需要随机访问能力，而 list 不支持随机访问。

10. 不支持 [] 运算符：与 at() 方法类似，list 也不支持 [] 运算符来访问元素，原因同上。

11. 不支持 resize() 方法：list 不提供 resize() 方法来改变容器的大小，因为 list 的大小是动态的，且不连续分配内存。

12. 不支持 reserve() 方法：list 不提供 reserve() 方法来预分配内存，因为 list 的内存分配策略是自动的。

list 的这些特点使得它在需要频繁插入和删除操作的场景中非常有用，但在需要快速随机访问的场景中则不如 std::vector 或数组高效。

List 的重要接口用法介绍

1.创建和初始化List

在C++中，可以使用多种方式创建和初始化 list 容器：

list

• (1)
  空容器构造函数(默认构造函数)构造一个没有元素的空容器。
• (2)
  构造一个包含n个元素的容器。每个元素都初始化为val。
• (3)
  构造一个包含与[first,last)范围相同数量元素的容器，每个元素以相同的顺序从该范围内的相应元素构造。
• (4)
  构造了一个包含 x 中每个元素副本的容器，元素顺序与 x 中的顺序相同。

#include <iostream>
#include <list>

int main() {
    // (1)创建一个空的list
    std::list<int> mylist;
	
	// (2)创建一个有n个空间每个空间都存val的list
	std::list<int> mylist2(5,10);
	// 使用初始化列表创建list
    std::list<int> mylist3 = {1, 2, 3, 4, 5};

	// (3)创建一个包含一些整数的数组
	int arr[] = { 10, 20, 30, 40, 50 };
	// 创建一个指向数组的迭代器范围
	int* first = arr;
	int* last = arr + sizeof(arr) / sizeof(arr[0]);
	// 使用迭代器范围创建一个list
	std::list<int> mylist3(first, last);
	
    // (4)使用另一个list初始化
    std::list<int> mylist4(mylist2);

    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

2.插入元素

push_back

• 在 list 容器的末尾添加了一个新元素，位于其当前的最后一个元素之后。val 的内容被复制（或移动）到新元素中，就是尾插个节点

	std::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
1
2
3
4

---

push_fornt

• 就是头插个节点

    std::list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
1
2
3
4

---

insert

• (1)
  就是指定位置的元素之前进行插入新元素
• (2)
  选择插入位置进行单个或者多个元素的插入
• (3)
  进行[first,last)范围的插入

	std::list<int> mylist1 = { 1, 2, 3, 4, 5 }; // 初始化列表
	std::list<int>::iterator it1 = mylist1.begin(); // 获取迭代器
	// 在迭代器 it 指向的位置之前插入值为 10 的元素
	it1 = mylist1.insert(it1, 10);//(1)

	std::list<int> mylist2 = { 1, 2, 3, 4, 5 }; // 初始化列表
	std::list<int>::iterator it2 = mylist2.begin(); // 获取迭代器
	// 在迭代器 it 指向的位置之前插入 2 个值为 10 的元素
	mylist2.insert(it2, 2, 10);//(2)

	std::list<int> mylist3 = { 1, 2, 3, 4, 5 }; // 初始化列表
	std::vector<int> myvector = { 6, 7, 8 }; // 初始化向量
	std::list<int>::iterator it3 = mylist3.begin(); // 获取迭代器
	// 在迭代器 it 指向的位置之前插入 myvector 中的元素
	mylist3.insert(it3, myvector.begin(), myvector.end());//(3)

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

删除元素

pop_back

• 删除末尾元素

---

pop_font

• 删除开头元素

---

clear

• 清空整个list

mylist.pop_back(); 
mylist.pop_front(); 
mylist.clear();  
1
2
3

---

erase

• (1)
  接受一个迭代器 position ，它指向你想要删除的单个元素。这个元素会被从容器中移除，容器的大小会减一。返回值是一个迭代器，指向被删除元素之后的元素，如果 position 是容器中的最后一个元素，则返回 end() 。
• (2)
  接受一对迭代器 first 和 last ，它们定义了一个范围。这个范围内的所有元素都会被从容器中移除。返回值是一个迭代器，指向被删除范围之后的第一个元素，如果 last 是容器中的最后一个元素，则返回 end() 。

	std::list<int> mylist1 = { 1, 2, 3, 4, 5 };
	std::list<int>::iterator it = mylist1.begin();
	// 删除迭代器 it 指向的元素
	it = mylist1.erase(it);//(1)

	std::list<int> mylist2 = { 1, 2, 3, 4, 5 };
	std::list<int>::iterator it1 = mylist2.begin();
	std::list<int>::iterator it2 = mylist2.begin();
	std::advance(it2, 3); // 移动 it2 到第四个元素
	// 删除从 it1 到 it2 范围内的元素
	it1 = mylist2.erase(it1, it2);//(2)
1
2
3
4
5
6
7
8
9
10
11

遍历List

迭代器遍历

for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it) {
    std::cout << *it << " ";
}
1
2
3

范围for遍历

	list<int> lt = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
1
2
3
4
5
6

排序List

sort

• (1)
  升序排序
• (2)
  降序排序（得需要仿函数）

	list<int> lt = { 1, 3, 2, 5, 4, 9, 8, 7, 6 };
	//排序升序
	lt.sort();
	lt.sort(greater<int>());//降序，greater<int>()//仿函数
1
2
3
4

反转List

reverse

• 反转或者说逆置list

mylist.reverse(); // 反转list中的元素顺序
1

转移List

splice

• 注意：
  转移之后lt3直接转移走，lt3里面什么都没有了就
• 吐槽：
  虽说起名字叫splice但是还是感觉transfers更贴近一点
  

	//splice （transfers） 转移
	list<int> lt2;
	lt2.push_back(1);
	lt2.push_back(3);
	lt2.push_back(5);
	lt2.push_back(4);
	lt2.push_back(2);

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

	lt2.splice(lt2.end(), lt2, lt2.begin());

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

	list<int> lt3;
	lt3.push_back(1);
	lt3.push_back(2);
	lt3.push_back(3);

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

	lt2.splice(lt2.end(), lt3);
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

	//转移之后lt3直接转移走，lt3里面什么都没有了就
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl;
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
41
42
43
44
45
46

去重

unique

• (1)
  去除list中重复的元素
• (2)
  接受一个二元谓词（ BinaryPredicate ），用于定义两个元素是否相等。默认情况下，如果两个元素相等（即它们的值相同），则认为它们是重复的。unique 函数会遍历列表，并移除所有相邻的重复元素，只保留第一个元素。新列表的大小会减小，但元素的顺序不会改变。
• 注意：
  在用去重函数之前一定要进行排序
  

	//去重 unique(得先排序)
	lt.unique();//(1)

	//(2)
	#include <iostream>
	#include <list>
	#include <algorithm> // for std::equal_to

	bool is_equal(const int& a, const int& b) {
    return a == b;
	}

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

    // 使用自定义的二元谓词来定义相等性
    mylist.unique(is_equal);

    // 打印列表以查看结果
    for (int& elem : mylist) {
        std::cout << elem << " ";
    }
    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

合并

merge

• 用于合并两个有序序列。 std::merge 函数定义在 头文件中，它接受两个有序序列的迭代器范围，并将它们合并成一个有序序列。

#include <iostream>
#include <list>
#include <algorithm> // for std::merge
#include <iterator>   // for std::ostream_iterator

int main() {
    std::list<int> list1 = {1, 3, 5, 7};
    std::list<int> list2 = {2, 4, 6, 8};
    std::list<int> merged_list;

     // 使用 std::merge 合并两个有序列表
     std::merge(list1.begin(), list1.end(),
                list2.begin(), list2.end(),
                std::back_inserter(merged_list));

     // 打印合并后的列表
     std::copy(merged_list.begin(), merged_list.end(),
               std::ostream_iterator<int>(std::cout, " "));
     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

总结

list 是C++标准模板库中非常强大的容器之一，它提供了快速的插入和删除操作，并且支持双向迭代。通过本文的介绍，你应该对 list 的基本用法有了一个大致的了解。在实际编程中，根据具体需求选择合适的容器是非常重要的，list 适合于那些需要频繁插入和删除元素的场景。

希望这篇文章能够帮助你更好地理解和使用C++中的 list 容器。如果你有任何问题或需要进一步的解释，请随时在评论区留言。

小卷王们，用你们勤劳的小手给我点点赞，蟹蟹