C++list模拟实现

自我名言：只有努力，才能追逐梦想，只有努力，才不会欺骗自己。
喜欢的点赞，收藏，关注一下把！

库里面的list类模板，实现的是带头双向循环链表。这里我们和库实现的是一样的。

1.链表结点

这里链表结点实现的是一个模板，因为我们并不知道别人想在结点里放什么数据。

其次库里面结点指针是void*，而我们和库里面有一些细微差别，

//链表结点
template<class T>
struct __list_node
{
	__list_node* _prev;
	__list_node* _next;
	T _date;
};
//struct和class一样，也可以是类关键字，并且里面的成员变量和成员函数默认都是public的。
1
2
3
4
5
6
7
8
9

2.类模板基本框架

template<class T>
class List
{
	//每次都要写太长了，所以typedef一下
	typedef __list_node<T> node;
public:

private:
	node* —_head;
};
1
2
3
4
5
6
7
8
9
10

3.构造

template<class T>
struct __list_node
{
	__list_node* _prev;
	__list_node* _next;
	T _date;

	__list_node(const T& val)
		:_prev(nullptr)
		,_next(nullptr)
		,_date(val)
	{}
};

	//构造
	list()
	{
	//new对自定义类型会调用它的构造函数，因此，结点类必须要有一个构造
		_head = new node(T());
		_head->_prev = _head;
		_head->_next = _head;
	}

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

4.插入+普通迭代器实现

4.1尾插

	void push_back(const T& x)
	{
		node* newnode = new node(x);
		node* tail = _head->_prev;

		tail->_next = newnode;
		newnode->_prev = tail;
		newnode->_next = _head;
		_head->_prev = newnode;
	}
1
2
3
4
5
6
7
8
9
10

4.2普通迭代器实现

这使用库里面的iterator,遍历链表。

注意list遍历只能用迭代器，或者范围for(底层是迭代器)，不能用下标+[]，因为vector物理结构是数组，而list底层是一个个按需申请的结点。

接下来我们自己实现一个迭代器。遍历链表。
首先来认识认识迭代器。

std::list<int>::iterator it = It.begin();
1

链表结点是一个个申请的，而vector和stirng是一次就申请连续的空间。

由于在前面学过封装，这里我们可以把指针封装起来，并且加上运算符重载（* ，++， !=）来支持，迭代器的行为。

template<class T>
struct __lsit_iterator
{
	typedef __list_node<T> node;
	node* _pnode;
	
	T& operator*()
	{
		return _pnode->_date;
	}

	__lsit_iterator<T>& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	bool operator!=(const __lsit_iterator<T>& It)
	{
		return _pnode != It._pnode;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//迭代器
iterator begin()
{
	//这里是匿名构造，但是__list_iterator缺少了构造，所以增加一下
	return iterator(_head->_next);
}

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

普通迭代器部分模板

template<class T>
struct __lsit_iterator
{
	typedef __list_node<T> node;
	node* _pnode;

	__lsit_iterator(node* _node)
		:_pnode(_node)
	{}
	
	T& operator*()
	{
		return _pnode->_date;
	}

	__lsit_iterator<T>& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	bool operator!=(const __lsit_iterator<T>& It)
	{
		return _pnode != It._pnode;
	}
};
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

我们使用自己的iterator，结果也是正确的。这里不太懂得，可以调试一下，帮助理解。

4.3对比list和vector的iterator

iteratorr------->1.内置类型 2.行为像指针一样。
范围【begin(),end())

list，vector迭代器上层使用都是一样的。但是它们底层实现不一样。list的迭代器是自定义类型（封装+运算符重载），但vector的迭代器并不一定就是内置类型（原生指针）。

就如在linux环境和vs环境下，erase后pos位置失效不失效的问题，在linux环境下pos不失效，而vs环境下pos失效，这是因为在两个不同环境下，iterator底层实现是不一样的。linux下iterator是原生指针，vs对vector的iterator和list的iterator一样，都是指针的封装。所以iterator不一定就是指针

为什么vector和list这里都用" != “，而不是” < "呢？

这是因为，vector的物理结构（数组）可以满足" < "，但是list的物理结构并不能确定前一个结点与后一个结点位置谁大谁小，所以统一用 " != "，可以满足不同容器的迭代器。

4.4迭代器的价值

1.封装底层实现，不暴露底层的实现细节。
2.提供统一的访问方式，降低使用成本。

迭代器是一种框架，可能代码我们都会写，但是这种框架思维是最重要的。

从物理层面上看，vector和list的iterator物理结构都是指针，请问大小是几个字节呢？

vector迭代器是一个原生指针，list迭代器是一个指针类模板，类的大小是成员变量的大小+内存对齐，list迭代器我们就放一个node*指针，我们知道32位指针大小为4，64位指针大小为8；所以大小都是4/8字节。

虽然iterator变化都是指针的变化，但是它们的类型是不一样的，vector的iterator是内置类型（原生指针），list的iterator是自定义类型，编译器根据类型的不同所走的方式不同，list的iterator走的是调用函数，如++it，调用it.operator++()再把结构返回来，而vector直接使用，指针直接像后走4个字节。。这就是类型的力量。

4.5insert

	iterator insert(iterator pos, const T& val)
	{
		node* newnode = new node(val);
		
		node* cur = pos._pnode;
		node* prev = cur->_prev;

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

		return iterator(newnode);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.6尾插头插复用写法

	void push_back(const T& x)
	{
		//node* newnode = new node(x);
		//node* tail = _head->_prev;

		//tail->_next = newnode;
		//newnode->_prev = tail;
		//newnode->_next = _head;
		//_head->_prev = newnode;
		insert(end(), x);
	}
	
	void push_front(const T& x)
	{
		insert(begin(), x);
	}

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

5.删除+erase

5.1erase

iterator erase(iterator pos)
	{
		assert(pos != end());
		node* prev = pos._pnode->_prev;
		node* next = pos._pnode->_next;

		prev->_next = next;
		next->_prev = prev;

		delete pos._pnode;
		//返回pos下一个位置
		return iterator(next);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

5.2尾删头删复用写法

	__List_iterator<T>& operaotr--()
	{
		_pnode = _pnode->prev;
		return *this;
	}
	
	void pop_back()
	{
	//iterator没有实现--运算符重载，所以补充一下
		erase(--end());
	}
	
	void pop_front()
	{
		erase(begin());
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.析构+empty+size+clear

6.1clear

	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);
		}
	}
1
2
3
4
5
6
7
8

6.2size

//一般想法就是遍历，统计一下个数，但是我们这里可以增加一个_size成员遍历，来统计个数
//然后再返回这个变量即可
//成员变量增加一个_size,构造都要改，但是我们实现了empty_initialize(),只要修改这里就可以

	void empty_initialize()
	{
		_head = new node(T());
		_head->_prev = _head;
		_head->_next = _head;
		_size = 0;
	}
	
	size_t size() const
	{
		return _size;
	}
//插入和删除也需要相应的把_size加上。

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

6.3 empty

	bool empty() const
	{
		return _size == 0;
	}
1
2
3
4

6.4 析构

	~List()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
1
2
3
4
5
6

7.拷贝构造+赋值运算符重载

7.1拷贝构造写法

	//拷贝构造传统写法
	List(const List<T>& it)
	{
		//由于构造+拷贝构造+赋值都要有这样写法,为了减少代码冗余
		//专门写一个empty_initialize()
		//_head = new node(T());
		//_head->_prev = _head;
		//_head->_next = _head;
		empty_initialize();

		for (auto e : it)
		{
			push_back(e);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是这样写有一个问题。
list T是泛型， 如果T放的是内置类型还好说，但如果T放的是自定义类型，这里还涉及拷贝构造和析构。因此正确写法如下。

	//拷贝构造传统写法
	List(const List<T>& it)
	{
		empty_initialize();
		
		//加个引用
		for (auto& e : it)
		{
			push_back(e);
		}
	}
1
2
3
4
5
6
7
8
9
10
11

但是这样写，还是有问题，it是const修饰的对象，范围for变量底层是迭代器，走的是const的迭代器。但是在__List_iterator 还没有实现。这里先把拷贝构造和赋值写完，就说这个问题。

在string和vector模拟实现，拷贝构造和赋值运算符重载最终都用现代写法来实现。现代写法的主要思想：就是自己的事情让别人干，然后再交换一下。

拷贝构造现代写法复用构造函数

前面实现的是一个无参构造，想要复用构造函数，必须要实现这个一段区间的构造函数。

	template <class InputIterator>
	List(InputIterator first, InputIterator last)
	{
		empty_initialize();
		while (first != last)
		{
			push_back(*first);
			++first;
		}
	}
1
2
3
4
5
6
7
8
9
10

	void swap(List<int>& x)
	{
		std::swap(_head, x._head);
		std::swap(_size,x._size);
	}

	//拷贝构造现代写法
	List(const List<T>& it)
	{
		//这里必须要申请带头结点，不然交换就会野指针，tmp析构的是就会报错
		//也不能直接给_head(nullptr)，这样tmp析构也会报错
		empty_initialize();
		List<T> tmp(it.begin(), it.end());
		swap(tmp);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

7.2赋值运算符重载

	//传统写法
	List<T>& operator=(const List<T>& it)
	{
		if (this != &it)
		{
			//this->clear()
			clear();
			for (auto& e : it)
			{
				//this->push_back(e);
				push_back(e);
			}
		}
		return *this;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

赋值运算符重载现代写法的思想：复用拷贝构造函数

	//赋值现代写法
	//it这里调用拷贝构造函数
	List<T>& operator=(List<T> it)
	{
		swap(it);
		return *this;
	}
1
2
3
4
5
6
7

虽然现在已经实现了拷贝构造和赋值运算符重载，但是迭代器没有实现const iterator 上面代码都会报错。

接下来实现const迭代器

8.const迭代器

回想一下vector实现的const迭代器

	typedef T* iterator;
	typedef const T* const_iterator;
1
2

	List<int>::iterator it = It.begin();
	//可能会以为在前面加上const 就是const迭代器了，但这样是不对的
	const List<int>::iterator it = It.begin();
1
2
3

我们知道const修饰指针有不同位置

//const修饰*p1，*p1内容不能改变，p1指针可以改变
	const T* p1
//const修饰p2，p2指针不能改变，*p2内容可以改变
	T* const p2
1
2
3
4

而const迭代器类似p1的行为，保护指向对象不能改变，迭代器本身可以修改

//不符合迭代器的行为，因为它保护迭代器 本身不能修改，那么就不能++/--迭代器
	const List<int>::iterator it = It.begin();
1
2

所以考虑一下，放在__List_iterator中；

	//iterator it
	//*it
	//++it
	T& operator*()
	{
		return _pnode->_date;
	}

	//可能还会想这样写，const修饰指针*this
	//const iterator* const this  这样*this就不会改变了
	//但是*this 是const iterator it
	//*it
	//++it 这样的话，可以解引用，但是不能++it
	const T& operator*() const
	{
		//引用赋值，必须权限缩小或者平移，所以返回类型是const
		return _pnode->_date;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

因此我们大多数人会再写一个const迭代器类

template<class T>
struct __List_iterator
{
	typedef __List_node<T> node;
	node* _pnode;

	__List_iterator(node* _node)
		:_pnode(_node)
	{}

	cosnt T& operator*()
	{
		return _pnode->_date;
	}

	__List_iterator<T>& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	__List_iterator<T>& operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}


	bool operator!=(const __List_iterator<T>& It)
	{
		return _pnode != It._pnode;
	}
};
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

但是对比普通迭代器和const迭代器，发现就只有operator*不一样，其他运算符重载都一样。
我们看库里是怎么实现iterator的。
暂时先不用管Ptr参数。

看到大佬是把普通迭代器和const迭代器实现放在一块，然后用Ref参数来做区分。

我们知道一个模板类，由于类型不同可实现不同的类。
如list < int > , list< char > 虽然用的是统一模板，但是由于类型不同，因此是不同的类。所以大佬方法是非常厉害的。

//typedef __List_iterator iterator;
//typedef __List_iterator const_iterator;
template<class T,class Ref>
struct __List_iterator
{
	typedef __List_node<T> node;
	typedef __List_iterator<T, Ref> self;
	node* _pnode;

	__List_iterator(node* _node)
		:_pnode(_node)
	{}

	Ref operator*()
	{
		return _pnode->_date;
	}
	
	//__List_iterator& operator++()
	//{
	//	_pnode = _pnode->_next;
	//	return *this;
	//}
	
	//普通迭代器和const迭代器返回类型不一样，因此typedef一下，比较方便。
	self& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	//__List_iterator& operator--()
	//{
	//	_pnode = _pnode->_prev;
	//	return *this;
	//}

	self& operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}


	//bool operator!=(const __List_iterator& It)
	//{
	//	return _pnode != It._pnode;
	//}

	bool operator!=(const self& It)
	{
		return _pnode != It._pnode;
	}
};
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

有了const迭代器，拷贝构造和赋值运算符重载就没问题了。

9.类名与类型的区别

普通类： 类名 等价于 类型
类模板： 类名 不等价于 类型

注意：在类外面 类名 != 类型 ,类里面 类名 == 类型

这样写是没有报错的，但是不建议这样写。如果别人这样写，能看懂即可。

就如库里面提供的拷贝构造+赋值就是这样写的

10.对于自定义类型迭代器遍历的功能实现

list< T >，T可能是内置类型，也有可能是自定义类型，如果是自定义类型，迭代器该如何遍历呢？

struct Pos
{
	int _row;
	int _col;

	Pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{}
};

void test_list5()
{
	List<Pos> It;
	Pos p(1,1);
	It.push_back(p);
	It.push_back(p);
	It.push_back(Pos(2,2));
	It.push_back(Pos(3,3));


	List<Pos>::iterator it = It.begin();
	while (it != It.end())
	{
		//这里还这样解引用可以拿到想要的数据吗？
		cout << *it << " ";
		++it;
	}
	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

解引用有三种访问方式
1.数组------> [ ]
2.普通指针（如int *p)------> *p
3.结构的指针（pos *p）-------> p----->

	List<Pos>::iterator it = It.begin();
	while (it != It.end())
	{
		//cout << *it << " ";
		//1.
		cout << (*it)._row << ":" << (*it)._col << endl;
		//2.
		cout << it->_row << ":" << it->_col << endl;
		++it;
	}
	cout << endl;
1
2
3
4
5
6
7
8
9
10
11

第一种方法，调用it.operator*，返回的是一个Pos对象，

第二种方法，需要调用it.operator->，因此给迭代器增加一个operator->()函数

	T* opearotr->()
	{
		//返回的是结点数据的地址
		return &_pnode->_date;
	}	
1
2
3
4
5

对于T是自定义类型，迭代器遍历，推荐it->_row这样的。

再看一个问题

void print_List(const List<Pos>& lt)
{
	List<Pos>::const_iterator it = lt.begin();
	while (it != lt.end())
	{
		//const迭代器，数据不能修改
		it->_row++;
		cout << it->_row << ":" << it->_col << endl;

		++it;
	}
	cout << endl;
}

void test_list7()
{
	List<Pos> It;
	Pos p(1, 1);
	It.push_back(p);
	It.push_back(p);
	It.push_back(Pos(2, 2));
	It.push_back(Pos(3, 3));


	List<Pos>::iterator it = It.begin();
	while (it != It.end())
	{
		//普通迭代器，对于数据可以修改
		it->_row++;
		cout << it->_row << ":" << it->_col << endl;
		++it;
	}
	cout << endl;

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

注意运行结果，const迭代器竟然也能支持it->_row++了。这不符合const迭代器。

因此再次修改一下迭代器，但是我们的普通迭代器和const迭代器实现在一块，所以这里我们给__List_iterator第三个参数Ptr

	Ptr operator->()
	{
		return &_pnode->_date;
	}
1
2
3
4

11.迭代器完整代码

//typedef __List_iterator iterator;
//typedef __List_iterator const_iterator;
template<class T,class Ref,class Ptr>
struct __List_iterator
{
	typedef __List_node<T> node;
	typedef __List_iterator<T,Ref,Ptr> self;
	node* _pnode;

	__List_iterator(node* _node)
		:_pnode(_node)
	{}

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

	//++it
	self& operator++()
	{
		_pnode = _pnode->_next;
		return *this;
	}

	//it++
	//int是一个占位符，为了把前置++和后置++ 分开
	self operator++(int)
	{
		self tmp(*this);
		_pnode = _pnode->next;
		return tmp;
	}

	//--it
	self& operator--()
	{
		_pnode = _pnode->_prev;
		return *this;
	}

	//it--
	self operator--(int)
	{
		self tmp(*this);
		_pnode = _pnode->_prev;
		return tmp;
	}
	

	bool operator!=(const self& It)
	{
		return _pnode != It._pnode;
	}
	
	bool operator==(const self& It)
	{
		return _pnode == It._pnode;
	}
};
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

注意观察我们的迭代器和List模拟实现，成员变量都有node*（指针）。

List我们实现了析构函数释放所有结点，而迭代器我们并没有实现析构函数。那迭代器这里默认生成的析构会不会释放结点呢？

析构函数和构造函数一样，如果不写，默认生成的析构函数，对内置类型不处理，对自定义类型调用它的析构。

如果我们List我们不写析构，编译器默认生成的析构，敢不敢轻易释放指针所指向的结点呢？
我们的编译器非常尽责，默认生成的析构，对自定义类型调用它的析构，对内置类型不敢轻易处理。所以对于指针不敢轻易释放所指向的结点。

因此对于List，我们需要析构的时候释放所有结点，所以自己写了个析构。而迭代器我们没写析构，那编译器默认生成的析构，对这个指针指向的结点也不会释放。因为这个结点是链表的，迭代器只是借助结点的指针帮助去访问或修改数据。所以也不能自己写一个析构去把这个结点释放。

不是说有指针就需要去析构，一定要具体问题具体分析。

并且iterator我们也没有实现拷贝构造和赋值。使用的是默认生成的属于浅拷贝就够用了，这是因为默认生成的析构并不会释放指针所指向的结点，所以够用。

在类与对象中也总结过，需要写析构，就需要自己写拷贝构造和赋值。

12.vector与list对比

12.1vector优缺点总结

优点
1.下标随机访问
2.尾插尾删效率高
3.cpu高速缓存命中高（因为vector物理结构是一段连续的数组）

缺点
1.前面部分插入删除效率低O(N)
2.扩容有销毁，还存在一定空间浪费

12.2list优缺点总结

优点
1.按需申请释放，无需扩容
2.任意位置插入删除O(1)

缺点
1.不支持下标随机访问
2.cpu高速缓存命中低（list物理结点是一个个按需申请的结点）

vector与list就像左右手一样，属于互补配合的关系。

13.迭代器失效问题

我们现在已经模拟实现了string，vector，list。
vector----->insert/erase (失效)
list-------->erase（失效）

string似乎从来没提过失效还是不失效的问题。那么string到底失效不失效呢？

stirng底层和vector一样，都是连续的空间。空间不够需要扩容，因此string也失效。

string------>insert/erase（失效），但是一般不关注string的失效。

vector的insert/erase给的是迭代器，string的insert/erase常用接口更多都是下标支持，迭代器支持用的很少。所以即使扩容或者删除对下标没什么影响。

自此关于list模拟实现内容结束了，有些接口没有实现，有兴趣可以实现一下。