• C++ list 的使用

    目录

    1. 构造函数

    1.1 list ()

    1.2 list (size_t n, const T& val = T())

    1.3 list (InputIterator first, InputIterator last)

    2. bool empty() const

    3.  size_type size() const

    4. T& front()

     4. T& back()

    5. void push_front (const T& val)

    6. void pop_front()

    7. void push_back (const T& val)

    8. void pop_back()

    9. 迭代器

    10. iterator insert (iterator pos, const T& val)

    11.  void insert (iterator pos, size_t n, const T& val)

    12. iterator erase (iterator pos)

    13. void swap (list& x)

    14. void resize (size_t n, const T& val = T())

    15.  void clear()

    16. 下面的这些函数都很好理解 

    16.1 void remove (const T& val)

    16.2 void unique()

    16.2 void merge(list& x)

    16.3 void sort()

    16.4 void reverse()

    list 的介绍，来源：list - C++ Reference (cplusplus.com)

    1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

    2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。

    3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高 效。

    4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。

    5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)

    1. 构造函数

    1.1 list ()

    这里的 T 是模板参数，list 可以存储任意类型的数据嘛。

    通过 list 的简介，我们知道 list 的底层其实是一个带头双向循环链表 (以下简称双链表)，在定义 list 的时候，我们需要初始化一个哨兵位的头结点。哨兵位的头结点不存储有效数据。无参构造就是用来初始化哨兵位的头结点的！

    1.2 list (size_t n, const T& val = T())

    这个构造函数可以初始化一个长度为 n 的，值均为 val 的双链表。

    1. #include
    2. #include
    3.  
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt(5, 8);
    9. 	//输出：8 8 8 8 8
    10. 	for (auto e : lt)
    11. 		cout << e << " ";
    12. 	cout << endl;
    13. }

    1.3 list (InputIterator first, InputIterator last)

    这个构造函数可以用一段迭代器区间来初始化双链表。构造的区间：[first, last)。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	vector<int> arr;
    9. 	arr.push_back(1);
    10. 	arr.push_back(2);
    11. 	arr.push_back(3);
    12. 	arr.push_back(4);
    13. 	arr.push_back(5);
    14.  
    15. 	list<int> lt(arr.begin(), arr.end());
    16. 	//输出：1 2 3 4 5
    17. 	for (auto e : lt)
    18. 		cout << e << " ";
    19. 	cout << endl;
    20.  
    21. 	return 0;
    22. }

    2. bool empty() const

    判断一个链表是不是空链表！如果有有效数据，返回 true，反之返回 false。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt1;
    9. 	cout << lt1.empty() << endl; //输出：1
    10.  
    11. 	list<int> lt2(5, 8);
    12. 	cout << lt2.empty() << endl; //输出：0
    13.  
    14. 	return 0;
    15. }

    3.  size_type size() const

    这个函数可以获取双链表的长度。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt2(5, 8);
    9. 	cout << lt2.size() << endl; //输出：5
    10.  
    11. 	return 0;
    12. }

    4. T& front()

    这个函数可以获取双链表的第一个有效元素。有 const 和非 const 两个版本，支持普通对象和 const 对象的调用。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	vector<int> arr;
    9. 	arr.push_back(1);
    10. 	arr.push_back(2);
    11. 	arr.push_back(3);
    12. 	arr.push_back(4);
    13. 	arr.push_back(5);
    14.  
    15. 	list<int> lt(arr.begin(), arr.end());
    16.  
    17. 	cout << lt.front() << endl; //输出：1
    18.  
    19. 	return 0;
    20. }

     4. T& back()

    这个函数可以获取双链表的最后一个有效元素。有 const 和非 const 两个版本，支持普通对象和 const 对象的调用。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	vector<int> arr;
    9. 	arr.push_back(1);
    10. 	arr.push_back(2);
    11. 	arr.push_back(3);
    12. 	arr.push_back(4);
    13. 	arr.push_back(5);
    14.  
    15. 	list<int> lt(arr.begin(), arr.end());
    16.  
    17. 	cout << lt.back() << endl; //输出：5
    18.  
    19. 	return 0;
    20. }

    5. void push_front (const T& val)

    双链表头插元素。因为之前我们都用 C 语言实现过双链表，学习 list 的使用就非常简单啦！

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_front(4);
    11. 	lt.push_front(3);
    12. 	lt.push_front(2);
    13. 	lt.push_front(1);
    14.  
    15. 	//输出：1 2 3 4
    16. 	for (auto e : lt)
    17. 		cout << e << " ";
    18. 	cout << endl;
    19.  
    20. 	return 0;
    21. }

    6. void pop_front()

    双链表头删元素。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_front(4);
    11. 	lt.push_front(3);
    12. 	lt.push_front(2);
    13. 	lt.push_front(1);
    14.  
    15. 	//输出：1 2 3 4
    16. 	for (auto e : lt)
    17. 		cout << e << " ";
    18. 	cout << endl;
    19.  
    20.     lt.pop_front();
    21.     
    22. 	//输出：2 3 4
    23. 	for (auto e : lt)
    24. 		cout << e << " ";
    25. 	cout << endl;
    26.  
    27. 	return 0;
    28. }

    7. void push_back (const T& val)

    双链表尾插元素。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(1);
    11. 	lt.push_back(2);
    12. 	lt.push_back(3);
    13. 	lt.push_back(4);
    14.  
    15. 	//输出：1 2 3 4
    16. 	for (auto e : lt)
    17. 		cout << e << " ";
    18. 	cout << endl;
    19.  
    20. 	return 0;
    21. }

    8. void pop_back()

    双链表尾删元素。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(1);
    11. 	lt.push_back(2);
    12. 	lt.push_back(3);
    13. 	lt.push_back(4);
    14.  
    15. 	//输出：1 2 3 4
    16. 	for (auto e : lt)
    17. 		cout << e << " ";
    18. 	cout << endl;
    19.  
    20.     lt.pop_back();
    21.  
    22. 	//输出：1 2 3
    23. 	for (auto e : lt)
    24. 		cout << e << " ";
    25. 	cout << endl;
    26.  
    27. 	return 0;
    28. }

    9. 迭代器

    list 的迭代器就不是简单的原生指针了。因为他的物理空间并不连续，因此 list 的迭代器需要进行封装，使得迭代器解引用能够返回节点存储的数据，使得迭代器加加，指向下一个节点，等等。具体的操作到我们模拟实现 list 的时候再说。

    下面的图是 list 迭代器 begin() 与 end() 迭代器对应的双链表节点。

    10. iterator insert (iterator pos, const T& val)

    这个函数可以在 list 的 pos 位置处，插入一个值为 val 的元素。返回值就是返回新插入的元素的位置对应的迭代器。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(1);
    11. 	lt.push_back(2);
    12. 	lt.push_back(3);
    13. 	lt.push_back(4);
    14.  
    15. 	//在begin() 的位置插入 0 ，相当于头插
    16. 	lt.insert(lt.begin(), 0);
    17.  
    18. 	//输出：0 1 2 3 4
    19. 	for (auto e : lt)
    20. 		cout << e << " ";
    21. 	cout << endl;
    22.  
    23. 	//在end() 的位置插入 5 ，相当于尾插
    24. 	auto it = lt.insert(lt.end(), 5);
    25.  
    26. 	cout << *it << endl; //输出：5
    27.  
    28.  
    29. 	//输出：0 1 2 3 4 5
    30. 	for (auto e : lt)
    31. 		cout << e << " ";
    32. 	cout << endl;
    33.  
    34.  
    35. 	return 0;
    36. }

    11.  void insert (iterator pos, size_t n, const T& val)

    这个函数可以在 pos 位置插入 n 个值为 val 的节点。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(1);
    11. 	lt.push_back(2);
    12. 	lt.push_back(3);
    13. 	lt.push_back(4);
    14.  
    15. 	//在begin() 的 位置插入 3 个值为 0 的节点
    16. 	lt.insert(lt.begin(), 3, 0);
    17.  
    18. 	//输出：0 0 0 1 2 3 4
    19. 	for (auto e : lt)
    20. 		cout << e << " ";
    21. 	cout << endl;
    22.  
    23. 	return 0;
    24. }

    12. iterator erase (iterator pos)

    这个函数可以删除 pos 位置的双链表节点。不可以删除 end() 位置的节点，会报错的！VS2022 做了检查的。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(1);
    11. 	lt.push_back(2);
    12. 	lt.push_back(3);
    13. 	lt.push_back(4);
    14.  
    15. 	//相当于头删
    16. 	lt.erase(lt.begin());
    17.  
    18. 	//输出：2 3 4
    19. 	for (auto e : lt)
    20. 		cout << e << " ";
    21. 	cout << endl;
    22.  
    23. 	return 0;
    24. }

    13. void swap (list& x)

    这个函数可以交换两个链表。我们实现 list 的时候，list 类中维护的是哨兵位的头结点的指针，交换两个链表的指针就能实现这样的效果。仅限于我们自己实现的 list 类哈！list 实现方式多种多样！

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt1;
    9. 	lt1.push_back(1);
    10. 	lt1.push_back(2);
    11. 	lt1.push_back(3);
    12. 	lt1.push_back(4);
    13.  
    14. 	list<int> lt2;
    15. 	lt2.push_back(5);
    16. 	lt2.push_back(6);
    17. 	lt2.push_back(7);
    18. 	lt2.push_back(8);
    19.  
    20. 	lt1.swap(lt2);
    21.  
    22. 	//输出：5 6 7 8
    23. 	for (auto e : lt1)
    24. 		cout << e << " ";
    25. 	cout << endl;
    26.  
    27. 	//输出：1 2 3 4
    28. 	for (auto e : lt2)
    29. 		cout << e << " ";
    30. 	cout << endl;
    31.  
    32.  
    33. 	return 0;
    34. }

    14. void resize (size_t n, const T& val = T())

    stl 库的接口风格都很相似，list 的resize 和 vector，string 的 resize 简直一毛一样。当 n 小于双链表的长度，直接截断，当 n 大于双链表的长度，会用 val 区初始化新插入的节点。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(0);
    11. 	
    12. 	lt.resize(5, 1);
    13.  
    14. 	//输出: 0 1 1 1 1
    15. 	for (auto e : lt)
    16. 		cout << e << " ";
    17. 	cout << endl;
    18.  
    19.  
    20. 	return 0;
    21. }

    15.  void clear()

    清空链表，即释放所有链表节点。

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5.  
    6. int main()
    7. {
    8. 	list<int> lt;
    9.  
    10. 	lt.push_back(0);
    11. 	lt.push_back(1);
    12. 	lt.push_back(2);
    13. 	lt.push_back(3);
    14. 	lt.push_back(4);
    15.  
    16. 	lt.clear();
    17.  
    18.     //没有输出
    19. 	for (auto e : lt)
    20. 		cout << e << " ";
    21. 	cout << endl;
    22.  
    23.  
    24. 	return 0;
    25. }

    16. 下面的这些函数都很好理解 

    16.1 void remove (const T& val)

    移除链表中所有值为 val 的节点。

    1 2 3 3 4 5 remove(3) ：1 2 4 5。

    16.2 void unique()

    删除链表中重复的节点。

    1 2 2 3 3 4 5 1 remove(3) ：1 2 3 4 5 1。

    这个函数只能对相邻的重复的数去重。因此多用于已经排好序的 list。

    16.2 void merge(list& x)

    这个函数用于两个 list 的合并，前提是两个 list 都被排好序了！

    例如：

    list1：-1 2 3 5 8

    list2：0 1 2 4 6 7

    合并后的结果：-1 0 1 2 2 3 4 5 6 7 8。

    16.3 void sort()

    链表的排序。

    16.4 void reverse()

    链表的逆置。

  • 相关阅读:
    跨境电商独立站App
    【Transformer从零开始代码实现】（一）输入部件：embedding+positionalEncoding
    授权控制-数据库用户分类、授权(GRANT)、收权(REVOKE)
    uboot启动流程-涉及lowlevel_init汇编函数
    《白皮书》：公共服务中人脸安全解决方案
    连续10年霸榜第一？程序员「最常用」的编程语言是它？
    R中绘制以特定数值为对称的colorbar
    排序 算法（第4版）
    10.3 调试事件转存进程内存
    Linux centos7 bash编程训练__打印各类形状
  • 原文地址：https://blog.csdn.net/m0_73096566/article/details/134006740