【初阶与进阶C++详解】第十篇：list

🏆个人主页：企鹅不叫的博客

​ 🌈专栏

• C语言初阶和进阶
• C项目
• Leetcode刷题
• 初阶数据结构与算法
• C++初阶和进阶
• 《深入理解计算机操作系统》
• 《高质量C/C++编程》
• Linux

⭐️ 博主码云gitee链接：代码仓库地址

⚡若有帮助可以【关注+点赞+收藏】，大家一起进步！

💙系列文章💙

【初阶与进阶C++详解】第一篇：C++入门知识必备

【初阶与进阶C++详解】第二篇：C&&C++互相调用（创建静态库）并保护加密源文件

【初阶与进阶C++详解】第三篇：类和对象上（类和this指针）

【初阶与进阶C++详解】第四篇：类和对象中（类的六个默认成员函数）

【初阶与进阶C++详解】第五篇：类和对象下（构造+static+友元+内部类

【初阶与进阶C++详解】第六篇：C&C++内存管理（动态内存分布+内存管理+new&delete）

【初阶与进阶C++详解】第七篇：模板初阶（泛型编程+函数模板+类模板+模板特化+模板分离编译）

【初阶与进阶C++详解】第八篇：string类（标准库string类+string类模拟实现）

【初阶与进阶C++详解】第九篇：vector

---

---

💎一、list使用

🏆1.list介绍

list是一个带头的双向循环链表。使用记得包含头文件

🏆2.list构造

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

list<int> lt1;// 无参构造
list<int> lt2(10, 5);// 用n个val构造一个list对象
list<int> lt3(lt2);// 拷贝构造
list<int> lt4(lt2.begin(), lt2.end());// 用一段区间的元素构造list
1
2
3
4

🏆3.list_iterator的使用

begin + end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置

void TestList1()
{
	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);

	lt.push_front(0);
	lt.push_front(-1);
	lt.push_front(-2);

	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

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

	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	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

🏆4.list的增删查改

push_back	尾插
pop_back	尾删
push_front	头插
pop_front	头删
insert	在pos位置插入一个元素
erase	删去pos位置的一个元素
swap	交换两个list中的元素
clear	清理list的有效元素
empty	判断容器是否为空
size	取容器有效节点的个数
front	返回list的第一个节点的元素
back	返回list的最后一个节点元素

void TestList1()
{
	list<int>lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_front(0);
	lt.push_front(-1);
	lt.push_front(-2);

	lt.erase(lt.begin());

	lt.insert(lt.begin(), 0);
}

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

🏆5.迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是在迭代器所指节点前一个位置进行插入，不会影响该节点和这个节点之后的结构，也不会导致迭代器失效，只有在删除时才会失效，并且失效的只是指被删除节点的迭代器，其他迭代器不会受到影响。

1.插入(迭代器不失效)

void TestList1()
{
	int arr[] = { 1,2,3,4,5, 6 };
	list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));

	list<int>::iterator it = lt.begin();

	lt.insert(it, 3);
}

1
2
3
4
5
6
7
8
9
10

2.删除(迭代器失效)

void TestList1()
{
	int arr[] = { 1,2,3,4,5, 6 };
	list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));

	list<int>::iterator it = lt.begin();

	while (it != lt.end())
	{
		lt.erase(it);
		++it;
	}
}

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

总结：

相比vector容器，vector容器插入数据是会导致迭代器失效，因为vector涉及增容问题，而list却不存在增容问题，所以迭代器指向的位置是有效的。删除数据会导致迭代器指向的位置是无效的，所以迭代器会失效。

**解决办法：**使用迭代器删除数据的时候，接收返回值并更新迭代器

void TestList1()
{
	int arr[] = { 1,2,3,4,5, 6 };
	list<int> lt(arr, arr + sizeof(arr) / sizeof(arr[0]));

	list<int>::iterator it = lt.begin();

	//lt.insert(it, 3);
	while (it != lt.end())
	{
		it = lt.erase(it);
	}
}

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

💎二、list模拟实现

🏆1.list的框架

list是由节点组成，所以定义一个节点的类（使用struct，成员函数默认公有），然后list的类中成员用一个头节点的指针作为成员。

//创建一个双向节点
template <class T>
struct list_node
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _data;
	//节点初始化
	list_ndoe(const T& val = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_data(val)
	{}
};

template<class T>
class list
{
	typedef list_node<T> Node;
public:
private:
	Node* _head;//哨兵位
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

🏆2.list迭代器实现

list迭代器我们将它封装成一个类，本质是指针

2.1迭代器框架

由于迭代器分普通迭代器和const 迭代器，为了不造成代码冗余，定义三个模板参数，根据传入的模板参数确定是那种迭代器。

分别是T，（Ref）T&，（Ptr）T*,重载三个函数后，可以控制传入的模板参数来控制const类型

// __list_iterator  ->  普通迭代器
// __list_iterator  ->  const迭代器
template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef list_node<T> Node;//节点
    typedef __list_iterator<T, Ref, Ptr> self;//简化
    Node* _node;//存放节点指针
    
    __list_iterator(Node* node)
		:_node(node)
	{}
}

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

2.2迭代器–/++

后置加减需要拷贝一个tmp变量来存储原本迭代器的位置

//前置++
self& operator++()
{
    _ndoe = _node->_next;
    return *this;
}
//后置++
self operator++(int)
{
    //详情参照日期类写法
    self tmp(*this);
    _ndoe = _node->_next;
    return tmp;
}
//前置--
self& operator--()
{
    _ndoe = _node->_next;
    return *this;
}
//后置--
self operator--(int)
{
    self tmp(*this);
    _ndoe = _node->_next;
    return tmp;
}
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

2.3迭代器解引用和指针

Ref operator*()
{
    return _node->_data;//返回值的引用
}
Ptr operator->()
{
    //两种写法一样
    //return &(operator*());
    return &(_node->_data);//返回地址
}
1
2
3
4
5
6
7
8
9
10

2.4==/!=判断

bool operator!= (const self& it)
{
return _node != *it._ndoe;
}
bool operator== (const self& it)
{
return _node == *it._ndoe;
}
1
2
3
4
5
6
7
8

2.5 list类内部begin()和end()实现

两种写法

iterator begin()
{
    //写法一
    //return iterator(_head->_next);
    //写法二,隐式类型转换
    return _head->_next;
}
iterator end()
{
    return iterator(_head);
}
const_iterator begin()
{
    //写法一
    //return iterator(_head->_next);
    //写法二,隐式类型转换
    return const_iterator(_head->_next);
}
const_iterator end()
{
    return const_iterator(_head);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

🏆3.list构造函数和赋值

默认构造函数

list()
{
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;
}
1
2
3
4
5
6

使用除默认构造外的其他构造函数时，_head还没有生成，所以我们包装一个生成 _head的函数

//当使用其他构造函数的时候,_head还不存在，需要手动构造一个
void empty_init()
{
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;
}

1
2
3
4
5
6
7
8

迭代器区间构造,复用empty_init()

template<class InputIeraterator>
list(InputIeraterator frist, InputIeraterator last)
{
    empty_init();
    while (frist != last)
    { 
        push_back(*frist);
        ++frist;
    }
}
1
2
3
4
5
6
7
8
9
10

拷贝构造,复用迭代器区间构造，函数重载后直接swap

void swap(list<T>& lt)
{
    std::swap(_head, lt._head);
}

//拷贝构造（现代写法）
//lt2(lt1)
list(const list<T>& lt)
{
    empty_init();
    list<T> tmp(l1.begin(), lt.end());
    swap(tmp);
}

//拷贝构造（传统写法）
lt2(lt1)
//list(const list& lt)
//{
//	_head = new Node();
//	_head->_next = _head;
//	_head->_prev = _head;
//	for (auto e : lt)
//	{
//		push_back(e);
//	}
//}
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

赋值，形参会自己调用析构函数清理空间

//lt2 = lt1
list<T>& operator=(list<T> lt)
{
    if (this != &lt)// 防止自己给自己赋值
    {
        swap(lt);
    }
    return *this;
}
1
2
3
4
5
6
7
8
9

🏆4.list的析构函数和clear()

clear(),通过迭代器遍历list，一个一个删除节点，注意迭代器更新

析构函数，利用claer()析构即可

~list()
{
    claer();
    delete _head;
    _head = nullptr;
}
void claer()
{
    iterator it = begin();
    while (it != end())
    {
        //需要用一个临时变量储存该节点的迭代器，避免迭代器失效
        it = erase(it);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🏆5.list增删查改

void push_back(const T& x)
{
    Node* tail = _head->_prev;
    Node* newnode = new Node(x);
    tail->_next = newndoe;
    newnode->_prev = tail;
    newnode->_next = _head;
    _head->_prev = newnode;
}
void push_front(const T& x)
{
    insert(begin(), x);
}
void pop_back()
{
    erase(--end());
}
void pop_front()
{
    erase(begin());
}
iterator erase(iterator pos)
{
    assert(pos != end());
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
}
//插入-在pos位置之前
iterator  insert(iterator pos, const T& x)
{
    Node* newndoe = new Node(x);
    Node* cur = pos._node;
    Ndoe* prev = cur->_prev;
    prev->_next = newnode;
    newnode->prev = prev;
    cur->_prev = newnode;
    newnode->_next = cur;
    return iterator(newnode);
}
//返回第一个节点的指针
T front()
{
	assert(_head->_next != _head);
	return _head->_next->_data;
}
//返回最后一个节点的指针
T back()
{
	assert(_head->_next != _head);
	return _head->_prev->_data;
}
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

🏆6反向迭代器（迭代器适配）

反向迭代器，跟正向迭代器相比除了++/–时方向不相等，其他操作基本一致，并且正向迭代器begin()位置上对印的是rend(), end()位置上对应rbegin()。

所以我们封装适配一下生成string,vector,list,deque对应的反向迭代器。

template<class Iterator, class Ref, class Ptr>
    struct Reverse_iterator
    {
        //拿正向迭代器封装
        Iterator _it;
        //Ref(T&), Ptr(T*)
        typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
	//利用正向迭代器构造反向迭代器
        Reverse_iterator(Iterator it)
            :_it(it)
            {}
	//为了对称返回的迭代器即将指向的下一个位置的数据
        //
        Ref operator*()
        {
            Iterator tmp = _it;
            return *(--tmp);
        }

        Ptr operator->()
        {
            return &(operator*());
        }

        Self& operator++()
        {
            --_it;
            return *this;
        }

        Self& operator--()
        {
            ++_it;
            return *this;
        }

        bool operator!=(const Self& s)
        {
            return _it != s._it;
        }
    };
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

在需要改变的类里面添加如下代码,即可反向打印代码：

//反向迭代器适配支持
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

//调用反向迭代器的构造函数
reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
reverse_iterator rend()
{
    return reverse_iterator(begin());
}
const_reverse_iterator rbegin()const
{
    return const_reverse_iterator(end());
}
const_reverse_iterator rend()const
{
    return const_reverse_iterator(begin());
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

其他模拟实现可以直接调用反向迭代器，在所需的类里面加上上述代码即可

💎三、list和vector对比

	vector	list
底层结构	动态顺序表，一段连续的空间	带头双向循环链表
随机访问	支持，时间复杂度是O(1)	不支持，时间复杂度是O(N)
插入和删除	效率低，时间复杂度是O(N)	效率高，时间复杂度是O(1)
空间利用率	底层是连续的空间，不容易造成内存碎片化	底层动图开辟，小结点容易造成内存碎片，空间利用率低
迭代器	原生指针	堆原生态指针进行封装
迭代器失效	插入和删除会造成，所以最后每次操作后堆迭代器重新赋值	插入数据不会，删除数据会造成迭代器失效
使用场景	需要高存储效率，支持随机访问，不关心插入删除效率	大量插入删除操作，不关心随机访问

---