ToB企服应用市场:ToB评测及商务社交产业平台

标题: C++初阶学习第十一弹——探索STL奥秘（六）——深度刨析list的用法和核心点 [打印本页]

---

作者: 玛卡巴卡的卡巴卡玛    时间: 2024-6-15 04:00
标题: C++初阶学习第十一弹——探索STL奥秘（六）——深度刨析list的用法和核心点
前言：
   
在前面，我们已经学习了STL中的string和vector，现在就来讲解STL中的末了一个部门——list的使用及其相关知识点，先阐明一点，因为我们之前已经讲过了string和vector的接口函数等用法，list的这些用法与它们相差不大，以是我们讲解的重心就不再是如何使用list上，而是后面list的模拟实现和一些细节点
  目录

一、list的使用
1.1 list的简单接口函数
1.2 list的注意事项
二、list的模拟实现
三、list和vector的区别
四、总结

---

一、list的使用

1.1 list的简单接口函数

首先我们需要先明白list的底部实际上是类似一个带头双向链表的，结构如下图所示：

   因此list非常便于插入和删除数据，下面我们就先来看一下list的一些告急的接口函数
  初始化列表：

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

复制代码

通过迭代器访问元素：

1. std::list<int>::iterator it = myList.begin();
2. while (it != myList.end()) {
3.     std::cout << *it << std::endl;
4.     ++it;
5. }

复制代码

在链表尾部插入元素：

1. myList.push_back(6);

复制代码

在链表头部插入元素：

1. myList.push_front(0);

复制代码

删除元素：

1. myList.remove(3); // 删除值为3的元素
2. myList.erase(it); // 删除迭代器指向的元素

复制代码

排序链表：

1. myList.sort();

复制代码

反转链表：

1. myList.reverse();

复制代码

  上面这些就是list常常使用的一些接口函数，没啥难度，有不理解的地方可以私信我大概到网上搜一下
  1.2 list的注意事项

   

• 迭代器失效： 在list进行插入和删除操作时，不仅操作的元素地点的迭代器会失效，全部指向链表的迭代器、指针和引用都会失效。因此，在进行操作后，需要重新获取有效的迭代器。（vector的使用也要注意这个标题）
  
• 内存效率： list的内存效率相对较高，因为它不需要像数组那样连续分配内存，但是它的插入和删除操作的时间复杂度为O(1)，这是因为链表的每个元素都需要存储指向前后节点的指针。
  
• 没有容量概念： list没有容量(capacity)这个概念，它总是根据需要动态分配内存。
  
• 元素唯一性： list中的元素是不重复的，如果尝试插入已经存在的元素，该元素将被覆盖。
  
• 操作顺序： 由于list是双向链表，因此插入和删除操作会保持元素的相对顺序，即元素在链表中的位置不会改变。
  

  使用list时，应该根据详细需求选择合适的操作，并注意迭代器的管理，以确保程序的正确性。
   特别夸大一下迭代器失效的标题，list的迭代器失效标题一般只有在删除元素的时间会出现，因为它插入数据的时间都是开辟的新空间，差别数据之间一般不是连接在一起的
  二、list的模拟实现

list的模拟实现上与前面的vector和string也极为相似，这里我们主要想讲一下list的迭代器的模拟实现，首先我们要知道，因为我们期待迭代器能像指针那样发挥作用，以是它的模拟实现需要包罗以下几点：
   1. 指针可以解引用，迭代器的类中必须重载operator*()
  2. 指针可以通过->访问其所指空间成员，迭代器类中必须重载oprator->()
  3. 指针可以++向后移动，迭代器类中必须重载operator++()与operator++(int)
  至于operator--()/operator--(int)释放需要重载，根据详细的结构来决议，双向链表可以向前 移动，以是需要重载，如果是forward_list就不需要重载--
  4. 迭代器需要进行是否相等的比较，因此还需要重载operator==()与operator!=()
  list迭代器也要分为两种：正向迭代器和反向迭代器
因为list正反向迭代器的应用都要实现，以是还是比较麻烦的，下面我们直接来看一下实现

1. #include <iostream>
2. using namespace std;
3. #include <assert.h>
4. namespace zda
5. {
6.         // List的节点类
7.         template<class T>
8.         struct ListNode
9.         {
10.                 ListNode(const T& val = T())
11.                         : _prev(nullptr)
12.                         , _next(nullptr)
13.                         , _val(val)
14.                 {}
16.                 ListNode<T>* _prev;
17.                 ListNode<T>* _next;
18.                 T _val;
19.         };
21.         //正向迭代器
22.         template<class T, class Ref, class Ptr>
23.         class ListIterator
24.         {
25.                 typedef ListNode<T> Node;
26.                 typedef ListIterator<T, Ref, Ptr> Self;
28.                 // Ref 和 Ptr 类型需要重定义下，实现反向迭代器时需要用到
29.         public:
30.                 typedef Ref Ref;
31.                 typedef Ptr Ptr;
32.         public:
33.                 //
34.                 // 构造
35.                 ListIterator(Node* node = nullptr)
36.                         : _node(node)
37.                 {}
39.                 //
40.                 // 具有指针类似行为
41.                 Ref operator*()
42.                 {
43.                         return _node->_val;
44.                 }
46.                 Ptr operator->()
47.                 {
48.                         return &(operator*());
49.                 }
51.                 // 迭代器支持移动
52.                 Self& operator++()
53.                 {
54.                         _node = _node->_next;
55.                         return *this;
56.                 }
58.                 Self operator++(int)
59.                 {
60.                         Self temp(*this);
61.                         _node = _node->_next;
62.                         return temp;
63.                 }
65.                 Self& operator--()
66.                 {
67.                         _node = _node->_prev;
68.                         return *this;
69.                 }
71.                 Self operator--(int)
72.                 {
73.                         Self temp(*this);
74.                         _node = _node->_prev;
75.                         return temp;
76.                 }
78.                 // 迭代器支持比较
79.                 bool operator!=(const Self& l)const
80.                 {
81.                         return _node != l._node;
82.                 }
84.                 bool operator==(const Self& l)const
85.                 {
86.                         return _node != l._node;
87.                 }
89.                 Node* _node;
90.         };
92.         //反向迭代器
93.         template<class Iterator>
94.         class ReverseListIterator
95.         {
96.         public:
97.                 typedef typename Iterator::Ref Ref;
98.                 typedef typename Iterator::Ptr Ptr;
99.                 typedef ReverseListIterator<Iterator> Self;
100.         public:
101.                 // 构造
102.                 ReverseListIterator(Iterator it)
103.                         : _it(it)
104.                 {}
106.                 // 具有指针类似行为
107.                 Ref operator*()
108.                 {
109.                         Iterator temp(_it);
110.                         --temp;
111.                         return *temp;
112.                 }
114.                 Ptr operator->()
115.                 {
116.                         return &(operator*());
117.                 }
119.                 // 迭代器支持移动
120.                 Self& operator++()
121.                 {
122.                         --_it;
123.                         return *this;
124.                 }
126.                 Self operator++(int)
127.                 {
128.                         Self temp(*this);
129.                         --_it;
130.                         return temp;
131.                 }
133.                 Self& operator--()
134.                 {
135.                         ++_it;
136.                         return *this;
137.                 }
139.                 Self operator--(int)
140.                 {
141.                         Self temp(*this);
142.                         ++_it;
143.                         return temp;
144.                 }
146.                 // 迭代器支持比较
147.                 bool operator!=(const Self& l)const
148.                 {
149.                         return _it != l._it;
150.                 }
152.                 bool operator==(const Self& l)const
153.                 {
154.                         return _it != l._it;
155.                 }
157.                 Iterator _it;
158.         };
159. }

复制代码

三、list和vector的区别

   1、恣意位置插入删除时：list可以随意插入删除，但是vector恣意位置的插入删除效率低，需要挪动元素，尤其是插入时有时间需要异地扩容，就需要开辟新空间，拷贝元素，释放旧空间，效率很低
     2、访问元素时：vector支持随机访问，但是list不支持随机访问       3、迭代器的使用上：vector可以使用原生指针，但是list需要对原生指针进行封装       4、空间使用上：vector使用的是一个连续的空间，空间使用率高，而list使用的是琐屑的空间，空间使用率低    四、总结

      以上就是学习list的一些重点内容和根本操作，这些内容固然是不全的，剩下有很多内容需要自己再去学习一下，后期我也会有针对的再加一些内容进来      感谢大佬观看，创作不易，还请各位大佬一键三连！！！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4