服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C++中list的使用与模拟实现

C++中list的使用与模拟实现

2022-12-06 14:11莓关系 C/C++

list相较于vector来说会显得复杂,它的好处是在任意位置插入,删除都是一个O(1)的时间复杂度,下面这篇文章主要给大家介绍了关于C++中list的使用与模拟实现的相关资料,需要的朋友可以参考下

一、list的介绍以及使用

1.1 list的介绍

1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代（所谓的常熟范围内，就是时间复杂度为O(1)）

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

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

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

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

这一段关于list的特性，需要能够与vector对比理解。

1.2 list的使用

1.2.1 list的构造

构造函数（ (constructor)） 接口说明
list() 构造空的list
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> l1; // 构造空的l1
    std::list<int> l2(4, 100); // l2中放4个值为100的元素
    std::list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
    std::list<int> l4(l3); // 用l3拷贝构造l4
    // 以数组为迭代器区间构造l5
    int array[] = { 16,2,77,29 };
    std::list<int> l5(array, array + sizeof(array) / sizeof(int));
    // 用迭代器方式打印l5中的元素
    for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
        std::cout << *it << " ";
    std::cout << endl;
    // C++11范围for的方式遍历
    for (auto& e : l5)
    {
        std::cout << e << " ";
    }
    std::cout << endl;
    return 0;
}

1.2.2 list iterator的使用

函数声明 接口说明
begin +
end		 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin +
rend		 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

注意：

1、begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动

2、rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

?
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
#include <iostream>
#include <list>
using namespace std;
void print_list(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }
    cout << endl;
}
int main()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    // 使用反向迭代器逆向打印list中的元素
    for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

1.2.3 list capacity

函数声明 接口说明
empty 检测list是否为空，是返回true，否则返回false
size 返回list中有效节点的个数

1.2.4 list element access

函数声明 接口说明
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用

1.2.5 list modifiers

函数声明 接口说明
push_front 在list首元素前插入值为val的元素
pop_front 删除list中第一个元素
push_back 在list尾部插入值为val的元素
pop_back 删除list中最后一个元素
insert 在list position 位置中插入值为val的元素
erase 删除list position位置的元素
swap 交换两个list中的元素
clear 清空list中的有效元素

这里就不用代码的形式展示了

1.2.6 list的迭代器失效

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

?
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
#include <iostream>
#include <list>
using namespace std;
void TestListIterator1()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
        l.erase(it);
        ++it;
    }
}
// 改正
void TestListIterator()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    auto it = l.begin();
    while (it != l.end())
    {
        l.erase(it++); // it = l.erase(it);
    }
}

二、list的模拟实现

2.1 模拟实现list

这是本章的重中之重。

?
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
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
#include <iostream>
#include <assert.h>
using std::cout;
using std::endl;
namespace zjx
{
    // 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>
    struct ListIterator
    {
        typedef ListNode<T>* PNode;
        typedef ListIterator<T, Ref, Ptr> Self;
    public:
        ListIterator(PNode pNode = nullptr)
        {
            _pNode = pNode;
        }
        //ListIterator(const Self& l);
 
        Ref operator*()
        {
            return _pNode->_val;
        }
 
        Ptr operator->()
        {
            return &_pNode->_val;
        }
 
        Self& operator++()
        {
            _pNode = _pNode->_pNext;
            return *this;
        }
 
        Self operator++(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pNext;
            return tmp;
        }
 
        Self& operator--()
        {
            _pNode = _pNode->_pPre;
            return *this;
        }
 
        Self& operator--(int)
        {
            Self tmp(*this);
            _pNode = _pNode->_pPre;
            return tmp;
        }
 
        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }
 
        bool operator==(const Self& l)
        {
            return _pNode == l._pNode;
        }
 
    public:
        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()
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        //构造函数
        list(int n, const T& value = T())
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
            for (int i = 0; i < n; i++)
            {
                push_back(value);
            }
        }
 
        template <class Iterator>
        list(Iterator first, Iterator last)
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }
 
        //拷贝构造函数
        list(const list<T>& l)
        {
            //用迭代器先构造出来一个
            list tmp(l.begin(), l.end());
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
            std::swap(_pHead, tmp._pHead);
        }
 
        list<T>& operator=(list<T> l)
        {
            std::swap(_pHead, l._pHead);
            return *this;
        }
 
        ~list()
        {
            clear();
            delete _pHead;
            _pHead = nullptr;
        }
        //List Iterator
        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 Capacity
        size_t size()const//这个函数右边的const是用来限定this指针的。原本的this指针，不可以改变指向，可以改变所知的内容。
                          //但若要对所指向的内容加以限定的话，那就在函数的右边加上const，表示此函数的隐藏的参数，也就是this指针，被加以const限定。
        {
            size_t count = 0;
            const_iterator cur = begin();
            while (cur != end())
            {
                count++;
                cur++;
            }
            return count;
        }
        //list为空返回1，否则返回0
        bool empty()const
        {
            return size() == 0;
        }
 
        // List Access
 
        T& front()
        {
            return begin()._pNode->_val;
        }
 
        const T& front()const
        {
            return begin()._pNode->_val;
        }
 
        T& back()
        {
            return _pHead->_pPre->_val;
        }
 
        const T& back()const
        {
            return _pHead->_pPre->_val;
        }
 
        // List Modify
 
        //void push_back(const T& val)
        //{
        //    insert(begin(), val);
        //}
        void push_back(const T& val)
        {
            Node* tail = _pHead->_pPre;
            Node* newnode = new Node(val);
            tail->_pNext = newnode;
            newnode->_pPre = tail;
            newnode->_pNext = _pHead;
            _pHead->_pPre = newnode;
        }
 
        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 next = pos._pNode;
            PNode prev = next->_pPre;
            PNode newnode = new Node(val);
            newnode->_pNext = next;
            newnode->_pPre = prev;
            prev->_pNext = newnode;
            next->_pPre = newnode;
            return iterator(newnode);
        }
 
         删除pos位置的节点，返回该节点的下一个位置
 
        iterator erase(iterator pos)
        {
            assert(pos != end());
            PNode next = pos._pNode->_pNext;
            PNode prev = pos._pNode->_pPre;
            delete pos._pNode;
            prev->_pNext = next;
            next->_pPre = prev;
            return iterator(next);
        }
 
        void clear()
        {
            iterator cur = begin();
            while (cur != end())
            {
                erase(cur++);
            }
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
 
        //void swap(list<T>& l);
 
    private:
 
        void CreateHead()
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        PNode _pHead;
    };
 
};
class Date
{
private:
    int _year;
    int _month;
    int _day;
public:
    Date(int year = 0, int month = 0, int day = 0)
        :_year(year),
        _month(month),
        _day(day)
    {
    }
    void print()
    {
        std::cout << _year << " " << _month << " " << _day << std::endl;
    }
};
int main()
{
    using namespace zjx;
    list<Date> it;
    it.push_back(Date(2022, 5, 16));
    it.push_back(Date(2022, 5, 17));
    it.push_back(Date(2022, 5, 18));
    it.push_back(Date(2022, 5, 19));
    it.push_back(Date(2022, 5, 20));
    for (auto e : it)
    {
        e.print();
    }
    cout << endl;
    list<int> a1(5, 2);
    for (auto e : a1)
    {
        cout << e << " ";
    }
    cout << endl;
    list<Date> a2(it);
    for (auto e : a2)
    {
        e.print();
    }
    cout << endl;
    int arr[] = { 1,2,3,4,5,6,7,8,9 };
    list<int> a3(arr, arr + 9);
    for (auto e : a3)
    {
        cout << e << " ";
    }
    cout << endl;
    a1 = a3;
    for (auto e : a1)
    {
        cout << e << " ";
    }
    cout << endl;
 
    cout << "a3的元素的个数 = " << a3.size() << endl;
 
    list<int> a4;
    cout << a4.empty() << endl;
    const auto ans1 = a3.front();
    auto ans2 = a3.back();
    cout << "ans1 = " << ans1 << " " << "ans2 = " << ans2 << endl;
    a3.push_front(30);
    a3.pop_back();
    a3.pop_front();
    a3.pop_front();
    for (auto e : a3)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

函数右边的const是用来限定this指针的。原本的this指针，不可以改变指向，可以改变所知的内容。

但若要对所指向的内容加以限定的话，那就在函数的右边加上const，表示此函数的隐藏的参数，也就是this指针，被加以const限定。

vector缺陷:

连续的物理空间，是优势，也是劣势。优势:支持高效随机访问。

劣势:

1、空间不够要增容，增容代价比较大。

2、可能存在一定空间浪费。按需申请，会导致频繁增容，所以一般都会2倍左右扩容。

3、头部或者中部插入删除需要挪动数据，效率低下list很好的解决vector的以上问题:

1、按需申请释放空间。

2、list任意位置支持O(1)插入删除。

const对象会自动找到const修饰的函数

总结

到此这篇关于C++中list的使用与模拟实现的文章就介绍到这了,更多相关C++ list讲解内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/qq_54178958/article/details/124772365

  • C++
  • list

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 qt5.9 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图