STL 上头系列——list 容器详解

传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，背后烟火，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我

🎉🎉🎉倾力打造转码社区微信公众号🎉🎉🎉

---

list 🤔

我们都知道C++ 容器机制本质上就是一个封装思想，string 是对字符串数组的封装，而 vector 是对支持动态开辟的顺序表的封装，今天的 list 也不例外他是对双向带头循环链表的封装。

这种结构的优点就在于支持双向迭代，允许常数范围内任意位置的插入与删除，在插入删除操作上效率高，但是缺陷也和双向带头循环链表一样，不支持下标的随机访问。

list 的构造函数声明如下：

list<int>a{1,2,3,4,5}
list<int>a(n)    //声明n个元素，每个元素默认为0
list<int>a(n, a)  //声明n个元素，每个元素都是a
list<int>a(iterator.begin, iterator.end)  //声明区间所指定的序列中的元素来自该区间，begin 和 end 是该区间的迭代器

1
2
3
4
5
6

list 遍历🤔

list 迭代器通过调用容器的成员函数 begin() 得到一个指向容器起始位置的 iterator，end() 函数来得到 list 端的下一位置,我们可以使用迭代器对 list 进行遍历。

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

当然也可以直接简单粗暴的范围 for 搞定：

for (auto& e : list)
	{
		cout << e << " ";
	}
1
2
3
4

list 迭代器🤔

因为 list 是链表结构，他自然不可以和 vector 一样优越的使用下标进行访问，我们仍然采用迭代器形式进行访问，他和 vector 的迭代器又有不同， vector，string 属于随机迭代器，而 list 是双向迭代器，目前的迭代器种类有 5 种：输入迭代器、输出迭代器、正向迭代器、双向迭代器、随机访问迭代器；同时也支持 rbegin() 与 rend() 的反向迭代器（也支持自己定义）。

我们自己在定义 list 迭代器时，由于数据类型的不同，我们需要定义出两种迭代器：普通迭代器和 const 迭代器，因为 const 数据类型只能由 const 迭代器进行访问。

普通迭代器非常简单：

同样的规则我们只需要将 iterator begin（）和 iterator end（）语句后加上 const再次定义出来即可。

但是！问题来了，既然考虑到了数据类型是否为 const 类型，那如果是指针类型或者引用类型时又该怎么办呢？

这时不要慌，思路很简单就是在模板+函数重载，包含进引用类型和指针类型即可：

template<class T,class Ref,class Ptr>
struct __list_itrator
{
   typedef list_node<T> Node;
   typedef __list_itrator <T,T*,T&> iterator;
   Node* node;
   Ref operator*()
   {
      return node->data;
   }//重载 & 返回到 Ref 引用类型
   Ptr operator*()
   {
      return &node->data;
   }//重载 * 返回到 Ptr 指针类型
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

const 迭代器同理 const 修饰即可。

迭代器失效🤔

list 和 vector 一样存在迭代器失效机制，但是和 vector 相比 list 情况要简单一些，删除节点后，只有指向当前节点的迭代器失效了，其前后的迭代器仍然有效，因为底层为不连续空间，只有被删除的节点才会失效。大体上的情况和解决办法参考 vector 一文 ：STL 上头系列——vector 容器详解

性能对比🤔

list 拥有一段不连续的内存空间，如果需要大量的插入和删除，使用 list 可以进行高效的操作，对比 vector 和 list，vector在尾部插入数据时不需要移动数据，list为双向循环链表也很容易找到尾部，因此两者在尾部插入数据效率相同，vector头部插入效率极其低，需要移动大量数据，正是由于在头部插入数据效率很低，所以没有提供 push_front 的方法，但是 list 相对独立的个体并不存在这种问题，因此 list 可轻松实现 push_back 和 push_front 。

总结一下：

vector 优点：

1. 适合尾插尾删，随机访问，CPU缓存命中率高

缺点：

1. 不适合头部和中部的插入删除，需要挪动数据效率低
2. 扩容有一定性能消耗，可能存在一定程度的空间浪费

list优点：

1. 任意位置插入删除效率高 （ O(1) ）
2. 支持动态开辟，按需申请释放空间

缺点：

1. 不支持随机访问
2. CPU缓存命中率低

list 实现🤔

namespace bite
{
  // List的节点类
  template<class T>
  
  struct ListNode
  {

    ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val)
    {}
    ListNode<T>* _pPre;

    ListNode<T>* _pNext;

    T _val;

  };
  //List的迭代器类

  template<class T, class Ref, class Ptr>

  class ListIterator

  {

    typedef ListNode<T>* PNode;

    typedef ListIterator<T, Ref, Ptr> Self;

  public:

    ListIterator(PNode pNode = nullptr):_pNode(pNode)
    {}
    ListIterator(const Self& l): _pNode(l._pNode)
    {}

    T& operator*()
    {
      return _pNode->_val;
    }
    
    T* operator->()
    {
      return &*this;
    }
    
    Self& operator++()
    {
      _pNode = _pNode->_pNext;
      return *this;
    }

    Self operator++(int)
    {
      Self temp(*this);
      _pNode = _pNode->_pNext;
      return temp;
    }

    Self& operator--()
    {
      _pNode = _pNode->_pPre;
      return *this;
    }

    Self& operator--(int)
    {
      Self temp(*this);
      _pNode = _pNode->_pPre;
      return temp;
    }

    bool operator!=(const Self& l)
    {
      return _pNode != l._pNode;
    }

    bool operator==(const Self& l)
    {
      return !(*this!=l);
    }

  private:
  
    PNode _pNode;
  };
  //list类

  template<class T>

  class list
  {
    typedef ListNode<T> Node;
    typedef Node* PNode;

  public:

    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T&> const_iterator;

  public:
    // List的构造
    list()
    {
      CreateHead();
    }

    list(int n, const T& value = T())
    {
      CreateHead();
      for (int i = 0; i < n; ++i)
       push_back(value);
    }

    template <class Iterator>
    list(Iterator first, Iterator last)
    {
      CreateHead();
      while (first != last)
      {
        push_back(*first);
        ++first;
      }
    }

    list(const list<T>& l)
    {
      CreateHead();
      // 用l中的元素构造临时的temp,然后与当前对象交换
      list<T> temp(l.cbegin(), l.cend());
      this->swap(temp);
    }

    list<T>& operator=(const list<T> l)
    {
      this->swap(l);
      return *this;
    }
    
    ~list()
    {
      clear();
      delete _pHead;
      _pHead = nullptr;
    }

    // List 迭代器

    iterator begin()
    {
      return iterator(_pHead->_pNext);
    }
    
    iterator end()
    {
      return iterator(_pHead);
    }

    const_iterator begin()const

    {
      return const_iterator(_pHead->_pNext);
    }

    const_iterator end()const
    {
      return const_iterator(_pHead);
    }

    // List 容量操作

    size_t size()const
    {
      size_t size = 0;
      ListNode *p = _pHead->_pNext;
      while(p != _pHead)
      {
        size++;
        p = p->_pNext;
      }
      return size;       
    }

    bool empty()const
    {
      return size() == 0;
    }
    
    // List 访问
    T& front()
    {
      assert(!empty());
      return _pHead->_pNext->_val;
    }
    const T& front()const
    {
      assert(!empty());
      return _pHead->_pNext->_val;
    }

    T& back()
    {
     assert(!empty());
      return _pHead->_pPre->_val;
    }

    const T& back()const
    {
      assert(!empty());
      return _pHead->_pPre->_val;
    }
    
    // List 修改

    void push_back(const T& val)
    {
      insert(begin(), val);
    }

    void pop_back()
    {
      erase(--end());
    }

    void push_front(const T& val)
    {
      insert(begin(), val);
    }

    void pop_front()
    {
      erase(begin());
    }

    // 在pos位置前插入值为val的节点

    iterator insert(iterator pos, const T& val)
    {
      PNode pNewNode = new Node(val);
      PNode pCur = pos._pNode;
      // 先将新节点插入
      pNewNode->_pPre = pCur->_pPre;
      pNewNode->_pNext = pCur;
      pNewNode->_pPre->_pNext = pNewNode;
      pCur->_pPre = pNewNode;
      return iterator(pNewNode);
    }

    // 删除pos位置的节点，返回该节点的下一个位置

    iterator erase(iterator pos)
    {
      // 找到待删除的节点
      PNode pDel = pos._pNode;
      PNode pRet = pDel->_pNext;
      // 将该节点从链表中拆下来并删除
      pDel->_pPre->_pNext = pDel->_pNext;
      pDel->_pNext->_pPre = pDel->_pPre;
      delete pDel;
      return iterator(pRet);
    }

    void clear()
    {
      iterator p = begin();
      while(p != end())
      {
        p = erase(p);
      }
    }

    void swap(List<T>& l)
    {
      pNode tmp = _pHead;
      _pHead = l._pHead;
      l._pHead = tmp;
    }

  private:

    void CreateHead()
    {
      _pHead = new Node;
      _pHead->_pPre = _pHead;
      _pHead->_pNext = _pHead;
    }

    PNode _pHead;
  };

}
 
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292

今天就到这里吧，润了家人们。