C++初阶：STL容器list的使用与初版自实现

1. list的接口与使用

1. list对标的是数据结构中的双向带头循环链表

1.1 默认成员函数

构造与拷贝构造

//无参构造
list<int> l1;
//指定个数值构造
list<int> l2(3, 100);
//迭代器区间构造
list<int> l3(l2.begin(), l2.end());
//拷贝构造
list<int> l4(l3);
1
2
3
4
5
6
7
8

赋值重载操作符

//给正在定义的对象使用赋值，会自动调用拷贝构造
list<int> l1(3,100);

list<int> l2 = l1;

list3<int> l3;

ls = l1;
1
2
3
4
5
6
7
8

1.2 迭代器与容量相关成员函数

迭代器相关

//正向反向迭代器
list<int> l1;
l1.begin();
l1.rbegin();

//const迭代器
l1.cbegin();
l1.crbegin();
1
2
3
4
5
6
7
8

容量大小相关

//list的现容量
list<int> l1;
l1.capacity();
//list的现存储数据长度
l1.size();
//理论上的最大长度
l1.max_size();
1
2
3
4
5
6
7

1.3 存储数据操作相关成员函数

数据操作相关

//返回list的头尾元素
list<int> l1;
l1.front();
l1.back();

list<int> l2(3,10);
//给已存在list使用指定值赋值
//使用指定值
l1.assgin(4, 99);
//使用迭代器区间
l1.assgin(l2.begin(), l2.end());

//头插，头删
l1.push_front(100);
l1.pop_front();

//尾插，尾删
l1.push_back(100);
l1.pop_back();

//指定位置插入
//在指定迭代器位置之前插入一个值
l1.insert(l1.begin(), 100);
//在指定迭代器位置之前插入n个数
l1.insert(l1.begin(), 3, 100);
//在指定迭代器位置之前插入一段迭代器区间
l1.insert(l1.beign(), l2.begin(), l2.end());

//指定位置删除
//删除指定迭代器位置的值
l1.erase(v.begin());
//删除指定的一段迭代器区间
l1.erase(v.begin(), v.begin() + 2);

//将两个list的结点交换
l1.swap(l2);

//调整链表的容量大小
//n大时扩容，n小时不缩容
//将list扩容至长度为10，并将新增加的结点值赋予为10
l1.resize(10,80);

//清空list的所有结点
l1.clear();
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

1.4 其他list操作成员函数

接合/转移：splice

//list之间的接合
list<int> l1(5, 10);
list<int> l2(5, 9);

//将list2拼接到list1的指定迭代器位置
l1.splice(l1.begin() + 1, l2);

//将l1上的一个指定迭代器位置结点拼接到l2上的指定迭代器位置
l2.splice(l2.begin(), l1, l1.end() - 1);

//将l1上的一段迭代器区间拼接l2的指定位置上
l2.splice(l2.begin(), l1.begin(), l1.begin() + 2);
1
2
3
4
5
6
7
8
9
10
11
12

寻找指定值并移除：remove，去重：unique

list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
//找到list中值等于3的结点并移除
l1.remove(3);

//对list进行去重操作，只保留不同值
l1.unique();
1
2
3
4
5
6
7
8
9

排序与逆置

list<int> l1;
l1.push_back(3);
l1.push_back(2);
l1.push_back(1);

//对list进行排序
//归并排序
l1.merge();
l1.sort();

//将整个链表逆置
l1.reverse();
1
2
3
4
5
6
7
8
9
10
11
12

2. list的自实现

2.1 list的自实现功能

1. 结点与迭代器类型的定义，创建
2. 迭代器的一系列运算符的重载
3. list的默认成员函数：构造，析构，赋值重载，拷贝构造，析构
4. list的插入删除相关成员函数：push_back，pop_back，push_front，pop_front，insert，erase

复用关系

2.2 list的结点结构

//结点，struct默认成员函数为公有
template<class T>
struct ListNode
{
	//类型名
	typedef ListNode<T> Node;

	Node* _prev;
	Node* _next;
	T val;

	//构造函数：
	ListNode(T x = T())
		:val(x)
		,_prev(nullptr)
		,_next(nullptr)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.3 list的迭代器

//迭代器
template<class T>
struct __list_iterator
{
	//内置类型无法进行运算符重载
	typedef __list_iterator<T> self;
	typedef ListNode<T> Node;

	__list_iterator(Node* node)
		:_node(node)
	{}

	//将指针进行封装
	Node* _node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3 list的结构

template<class T>
class list
{
public:
	//typedef的作用域只在类域中
	typedef __list_iterator<T> iterator;
	typedef ListNode<T> Node;
	
private:
	Node* Head;
};
1
2
3
4
5
6
7
8
9
10
11

2.4 list迭代器的运算符重载

1. ++，–

self& operator++()
{
	_node = _node->_next;

	return *this;
}

self operator++(int)
{
	self tmp(_node);
	_node = _node->_next;

	return tmp;
}

self operator--(int)
{
	self tmp(_node);
	_node = _node->_prev;

	return tmp;
}

self& operator--()
{
	_node = _node->_prev;

	return *this;
}
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

2. 解引用，!=，==

//后续可能存在值的修改
T& operator*()
{
	return _node->val;
}

//直接使用beign()的返回值作为参数
//形成中间临时变量，临时变量具有常性
//直接传引用会导致权限的放大
//self生成拷贝，self&权限放大
bool operator!=(const self& it)
{
	return _node != it._node;
}

bool operator==(const self& it)
{
	return _node == it._node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.5 list的成员函数

1. 构造

void init_empty()
{
	Head = new Node;
	Head->_next = Head;
	Head->_prev = Head;
}

list()
{
	init_empty();
}
1
2
3
4
5
6
7
8
9
10
11

2. 迭代器

//单参数的构造函数，支持隐式类型转换
iterator begin()
{
	return Head->_next;
}

iterator end()
{
	return Head;
}
1
2
3
4
5
6
7
8
9
10

3. 随机插入删除

void insert(iterator pos, T val)
{
	//在pos之前插入
	Node* cur = pos._node;
	Node* pre = cur->_prev;
	Node* newnode = new Node(val);

	newnode->_prev = pre;
	newnode->_next = cur;

	cur->_prev = newnode;
	pre->_next = newnode;
}

//指定删除会导致，迭代器失效，野指针
iterator erase(iterator pos)
{
	//会进行优化，直接使用end()返回的指针进行优化
	assert(pos != end());

	//删除当前位置
	Node* cur = pos._node;
	Node* pre = cur->_prev;
	Node* next = cur->_next;

	pre->_next = next;
	next->_prev = pre;

	delete cur;

	return next;
}
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

4. 头插，头删，尾插，尾删

void push_back(T val)
{
	insert(end(), val);
}

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

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

void pop_front()
{
	erase(begin());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5. clear与swap

void swap(list<T> s)
{
	std::swap(Head, s.Head);
}

void clear()
{
	while (begin() != end())
	{
		pop_back();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

6. 拷贝构造，赋值，析构

//没有写const迭代器
list(list<T>& s)
{
	//链接环状链表
	init_empty();
		
	//没有const迭代器
	for (auto e : s)
	{
		push_back(e);
	}
}

list<T>& operator=(list<T> s)
{
	swap(s);

	return *this;
}

~list()
{
	clear();

	delete Head;
	Head = nullptr;
}
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

3. const迭代器，operator->运算符重载与模板参数的应用

3.1 const迭代器

1. 我们对list容器的数据结构对象进行修开操作时，除开list提供的接口外，想要进行对指定位置的结点进行修改，需要先从链表中拿到这一结点位置信息，而我们只能通过迭代器访问遍历的方式做到这一操作。
2. 想要修改或者访问list的某一结点都是通过迭代器的方式进行的，而list的插入删除操作等接口也是通过迭代器从而实现的。
3. 当list被const进行修饰，其不想内部的数据被修改，即对我们仅开放只读权限时，我想要对list进行遍历，普通的迭代器因为类型不匹配的原因我们无法进行调用。
4. 因此，我们需要专门创建支持this指针指向内容被const修饰的迭代器，即只有访问权限无法对其指向进行更改操作的迭代器。
5. const迭代器的其他操作行为都与普通相同，只是operator*操作符重载返回的值是const修饰的无法更改，所以我们独立去编写一份相似度极高的代码是非常低效的。
6. 解决方式采用引入新的模板参数来做operator*返回值类型的区分。

template<class T, class Ref>
struct __list_iterator
{
	typedef __list_iterator<T, Ref> self;
	typedef ListNode<T> Node;
	
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}

	//const T&/T&
	//根据不同的模板参数，返回类型也不同
	Ref operator*()
	{
		return _node->val;
	}
	
	//其他操作与普通迭代器相同
	//......
};

//增加const迭代器后的list容器
template<class T>
class list
{
public:
	//同一模板，传递模板参数不同，得到的迭代器不同
	typedef __list_iterator<T, T&> iterator;
	typedef __list_iterator<T, const T&> const_iterator;

	//const迭代器
	//const修饰的变量，表示其值不想不被改变
	const_iterator begin() const
	{
		return Head->_next;
	}

	const_iterator end() const
	{
		return Head;
	}
	
	void init_empty()
	{
		Head = new Node;
		Head->_next = Head;
		Head->_prev = Head;
	}

	list()
	{
		init_empty();
	}

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
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

7. 创建const迭代器后，拷贝构造可以直接使用const修饰的参数，提高效率。

3.2 迭代器的operator->运算符重载

1. operator->运算重载的意义：当list存储的结点数据为自定义类型，且自定义类型其自身并没有重载流插入运算符，我们又要对其结点内部的值进行访问与打印时，迭代器重载的operator->就可以让我们来进行自定义结点内部数据的访问。

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_iterator<T, Ref, Ptr> self;
	typedef ListNode<T> Node;
	
	Node* _node;

	__list_iterator(Node* node)
		:_node(node)
	{}
	
	//返回结点的数据的地址，间接达到对自定类型结点内部数据的访问
	//const迭代器中对值的访问都要用const修饰，添加新的模板参数
	Ptr operator->()
	{
		return &_node->val;
	}
	
	//其他操作与普通迭代器相同
	//......
};

//list结构
template<class T>
class list
{
public:
	//同一模板，传递模板参数不同，得到的迭代器不同
	typedef __list_iterator<T, T&, T*> iterator;
	typedef __list_iterator<T, const T&, const T*> const_iterator;

private:
	Node* Head;
};

struct A
{
	int _aa;
	int _bb;

	A(int aa = 1, int bb = 1)
		:_aa(aa)
		,_bb(bb)
	{}
};

zyc::list<A> l1;

l1.push_back(A());
l1.push_back(A(2,3));
l1.push_back(A(2,2));

auto it = l1.begin();
//operator->的调用被编译器优化为一个箭头
//原本调用逻辑：it->->_aa，it.operator->()._aa
//优化调用
cout << it->_aa << 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
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