c++-list

---

前言

---

一、list介绍及使用

1、list介绍

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

2、list使用

2.1 list构造函数的使用

void Test01()
{
	//使用explicit list (const allocator_type& alloc = allocator_type());构造空的lt1
	list<int> lt1;
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	//使用explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
	//构造lt2，并且在lt2中放10个5.
	list<int> lt2(10, 5);
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

	//template 
	//list(InputIterator first, InputIterator last,const allocator_type & alloc = allocator_type());
	//使用上面的模板生成的迭代器区间构造函数，来构造lt3。
	list<int> lt3(lt2.begin(), lt2.end()); 
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl;
	//使用上面的模板生成的迭代器区间构造函数，以数组为迭代器区间构造lt4
	int array[] = { 34,32,9,23 };
	list<int> lt4(array, array + sizeof(array) / sizeof(int));
	for (auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;

	//使用list (const list& x);拷贝构造函数来构造lt4
	list<int> lt5(lt3);
	for (auto e : lt5)
	{
		cout << e << " ";
	}
	cout << endl;

	//使用迭代器来遍历lt4中的元素
	list<int>::iterator it = lt4.begin();
	while (it != lt4.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
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

2.2 list iterator的使用

void Test02()
{
	int array[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));

	//使用正向迭代器正向遍历list中的元素
	list<int>::iterator it = lt1.begin();
	while (it != lt1.end())
	{
		//可以通过迭代器改变元素的值
		(*it) = (*it) * 2;
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//使用反向迭代器逆向遍历list中的元素
	list<int>::reverse_iterator rit = lt1.rbegin();
	while (rit != lt1.rend())
	{
		//可以通过迭代器改变元素的值
		(*rit) = (*rit) * 2;
		cout << *rit << " ";
		//对rit++，迭代器向前移动
		++rit;
	}
	cout << endl;

	//使用const修饰的正向迭代器正向遍历list中的元素
	const list<int> lt2(array, array + sizeof(array) / sizeof(array[0]));
	list<int>::const_iterator cit = lt2.cbegin();
	while (cit != lt2.cend())
	{
		//不可以通过迭代器改变元素的值
		//(*cit) = (*cit) * 2;
		cout << *cit << " ";
		++cit;
	}
	cout << endl;

	//使用const修饰的反向迭代器逆向遍历list中的元素
	list<int>::const_reverse_iterator crit = lt2.crbegin();
	while (crit != lt2.crend())
	{
		//不可以通过迭代器改变元素的值
		//(*crit) = (*crit) * 2;
		cout << *crit << " ";
		//对rit++，迭代器向前移动
		++crit;
	}
	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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

2.3 list capacity的使用

void Test03()
{
	int array[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));
	list<int> lt2;
	cout << lt1.empty() << endl;
	cout << lt2.empty() << endl;
	cout << lt1.size() << endl;
	cout << lt2.size() << endl;
	cout << lt1.max_size() << endl;
	cout << lt2.max_size() << endl;

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

2.4 list modifiers的使用

list插入和删除：

void Test04()
{
	int array[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));
	lt1.push_front(0);
	lt1.push_back(10);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	lt1.pop_front();
	lt1.pop_back();
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

insert /erase：

void Test05()
{
	int array[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));
	// 获取链表中的第二个结点
	list<int>::iterator pos = ++lt1.begin();
	cout << *pos << endl;

	//在pos前插入值为4的元素
	lt1.insert(pos, 4);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	//在pos前插入5个值为6的元素
	lt1.insert(pos, 5, 6);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	//在pos前插入[v.begin(), v.end())区间的元素
	vector<int> v1(3,5);
	lt1.insert(pos, v1.begin(), v1.end());
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	//可以看到上面的插入中，都是在元素2之前插入元素，说明在list中，insert之后迭代器没有失效。

	// 删除pos位置上的元素
	lt1.erase(pos);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	//删除list中的[begin, end)区间中的元素，及删除list中的所有元素
	lt1.erase(lt1.begin(), lt1.end());
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

resize/swap/clear：

void Test06()
{
	int array[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));

	list<int> lt2;
	//将lt2中包含5个3，
	lt2.resize(5, 3);
	//如果resize()中的第一个参数小于lt2的size时，则会将lt2的元素减少为n个，即将后面的元素都删除
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	lt2.resize(2, 3);
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

	//交换lt1和lt2中的元素
	lt1.swap(lt2);
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;

	//将lt2中的元素清空
	lt2.clear();
	cout << lt2.size() << 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

2.5 list使用算法库中的find模板生成find方法

我们可以看到list库中并没有提供find方法，所以当list想要使用find方法查找元素时，就需要使用算法库中的find模板生成find方法。

void Test07()
{
	int array[] = { 1,2,3,4,5,6,7,8,9 };
	list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));
	//find返回的是指向元素的迭代器。如果没有查找到元素，find返回lt1.end()迭代器。
	list<int>::iterator pos = find(lt1.begin(), lt1.end(), 3);
	if (pos != lt1.end())
	{
		//在元素3前面插入30.
		lt1.insert(pos, 30);
	}
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

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

2.6 list中的sort方法

我们看到算法库中也提供了sort函数模板，但是为什么list库中还要单独实现一个sort函数呢？
这是因为算法库中的sort函数模板中需要传入一个RandomAccessIterator迭代器，即随机迭代器。而我们看到list的迭代器为bidirectional iterator，即双向迭代器，而sort方法需要传入随机迭代器，所以list使用不了。



我们看到算法库中的reverse模板中需要一个BidirectionalIterator，即双向迭代器，所以list可以使用reverse函数模板。

迭代器功能分类：
(1). 单向 ++
(2). 双向 ++ –
(3). 随机 ++ – + -
如果函数模板中要求为随机迭代器，就只能传随机迭代器；如果要求为双向迭代器，则可以传双向迭代器和随机迭代器，因为随机迭代器是特殊的双向迭代器。如果要求为单向迭代器，则可以传单向迭代器、双向迭代器和随机迭代器。

虽然list中提供了sort函数，但是list自己提供的sort函数性能不行，一般都不会使用。
下面我们让list使用自己提供的sort和vector使用算法库提供的sort(快排)进行性能测试。可以看到在Release版本下vector使用算法库提供的sort函数的效率更高一些。

void Test08()
{
	srand(time(0));
	const int N = 100000;
	vector<int> v;
	v.reserve(N);

	list<int> lt1;

	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		lt1.push_back(e);
	}

	int begin1 = clock();
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();
	int end2 = clock();

	cout << "vector sort: " << end1 - begin1 << endl;
	cout << "list sort: " << end2 - begin2 << 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

所以当我们想要将list中的元素进行排序时，可以先将list中的元素都拷贝到vector中，然后vector使用算法库中的sort排序，排完序后再将元素拷贝到list中，这样来提升list排序的性能。可以看到在Release版本下，使用上面的方法来对list中的元素进行排序可以大大提升list排序的性能。

void Test09()
{
	srand(time(0));
	const int N = 1000000;
	vector<int> v;
	v.reserve(N);

	list<int> lt1;
	list<int> lt2;
	for (int i = 0; i < N; ++i)
	{
		auto e = rand();
		lt1.push_back(e);
		lt2.push_back(e);
	}
	
	//将lt1拷贝到vector中排序
	int begin1 = clock();
	for (auto e : lt1)
	{
		v.push_back(e);
	}
	sort(v.begin(), v.end());
	//排完序后将元素再拷贝到lt1中
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}
	int end1 = clock();

	//使用list中提供的sort进行排序
	int begin2 = clock();
	lt2.sort();
	int end2 = clock();

	cout << "vector sort: " << end1 - begin1 << endl;
	cout << "list sort: " << end2 - begin2 << 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

二、list模拟实现

1、查看list源码的大致实现思路

我们知道list的底层实现是一个带头结点的双向循环链表。

可以看到list的源码中先定义了一个__list_node结构体来表示链表的结点。然后又定义了一个__list_iterator结构体来实现list的迭代器。最后又定义了一个list类来表示list。

2、模拟实现list

我们模拟实现list也按照list库中的办法来实现。
所以我们先定义一个struct list_node结构体来表示链表的结点。因为list_node里面的内容都是公开可访问的，所以我们使用struct来定义list_node，而不是使用class来定义list_node。并且因为该链表的结点中的_next和_prev指针域和_data数据域以后可能存任意类型的数据，所以我们使用模板来定义list_node这个结构体。

接下来我们再来定义list类，因为list类中的一些成员变量或成员函数是私有的，所以我们使用class来定义list。因为list中以后可能存任意类型的数据，所以我们实现list类时也需要用到模板，直接实现list模板类即可。
我们在list类中定义了一个_head成员变量，这个就是list的头结点，并且我们将头结点的_next指针域和_prev指针域都指向自己，表示该list为空的状态。

接下来我们实现list类的成员函数push_back，但是在实现这个函数之前我们需要先将list_node结构体的构造函数写好，这样才可以在list中添加新结点时直接将新结点的数据初始化。

然后再实现push_back函数，因为list是双向循环链表，所以在该链表的尾部插入新结点，其实就是在头结点之前插入新结点。

我们测试发现push_back方法成功插入新结点。


接下来我们再实现list类的迭代器。我们在前面看list源码知道了list的迭代器实现是又创建了一个__list_iterator结构体来实现，所以我们也再创建一个struct __list_iterator结构体用来实现list的迭代器。因为迭代器在使用时需要++向后移动，还需要*来得到数据，所以我们需要实现struct __list_iterator的一些操作符的重载函数。这样当迭代器进行++时，迭代器就会指向下一个结点，当解引用迭代器时，就将迭代器指向的结点的_data返回。判断迭代器是否相等就是判断两个迭代器指向的结点是否为同一个。这个迭代器就是自定义类型对原生指针的封装，模拟指针的行为，即该结构体的构造函数接收一个node * 的参数，因为node里面不是只有一个数据，需要将node的迭代器使用自定义类型对原生指针进行封装，即该迭代器内部封装了node * 类型的指针。

然后我们在list类中将__list_iterator< T >重命名为iterator，然后在begin函数中返回_head->_next结点的指针，因为list为双向循环链表，所以begin就是头结点的下一个结点，而end为有效数据的下一个结点，所以end就指向_head头结点。这时我们就可以使用list的迭代器来遍历list中的元素了，也可以使用范围for来遍历list的元素。


在测试代码中我们发现it = lt1.begin()调用了__list_iterator的拷贝构造函数，并且该拷贝构造函数为浅拷贝，但是为什么没有出错呢？是因为在__list_iterator结构体中没有实现析构函数，因为该类只负责提供iterator，即只是提供一个类似于指针的迭代器，在__list_iterator中并没有动态申请空间创建对象，而是只封装了对node * 指针的一些操作，而释放node结点的事需要list类中实现。

当我们实现了struct __list_iterator结构体中的前置++运算符重载函数后，我们继续将后置++运算符重载函数和前置 --和后置 --等的运算符重载函数也一并实现了。

上面的迭代器是没有被const修饰的迭代器，当我们在下面的情况中使用迭代器时就会出现错误。这是因为发生了权限放大，list类的成员函数begin中的this没有被const修饰，而lt被const修饰了，所以发生了权限放大。

所以我们在list类中又写了begin和end函数的const修饰的版本，但是我们知道const修饰的迭代器是不可以改变list中元素的值的，而我们实现的const修饰的迭代器却可以改变list中元素的值，这是因为我们使用const修饰begin和end函数，其实const修饰的是this指针，即相当于iterator begin(const list* this)，所以此时this指针指向的list的_head不能改变，但是在begin中并没有改变_head的值，而是将_head和_head->_next当作参数传给了__list_iterator结构体的构造函数然后创建了__list_iterator类型的对象。然后我们看到在__list_iterator中的 * 操作符的重载函数返回的是一个T类型的引用，所以才可以使用*it修改_data的值。

那么如果我们像下面一样使用typedef const iterator const_iterator;来重命名一个const_iterator呢？
这样其实更错误，因为这样定义了const_iterator之后，迭代器就不能++了，因为iterator被const修饰了，即T* const it，it为指针，it的内容不可以修改了，那么it迭代器就不可以向后移动了，而const T* it中，it的值可以修改，但是*it的内容不可以修改。

所以我们再根据__list_iterator结构体实现一个__list_const_iterator结构体，然后在这个结构体的*操作符重载函数中返回一个const T&的引用当作返回值，这样当使用const_iterator迭代器时就不可以通过迭代器修改list的元素的值了。

我们发现上面的__list_iterator和__list_const_iterator结构体中就只有operator*()函数的返回值不同，所以我们可以将这两个结构体合并为一个。我们通过模板参数来实现。我们给__list_iterator结构体的模板中新加一个Ref参数，当迭代器iterator不被const修饰时，就传入T&，当迭代器iterator被const修饰时，就传入const T&。
通过上面的操作我们知道了：
(1). 迭代器要么就是原生指针。
(2). 迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为。

下面我们自己实现一个AA结构体，然后使用list来存储AA结构体类型的数据，然后我们使用迭代器遍历list中的AA对象，并且使用cout<<来打印，但是因为我们没有在AA结构体中实现<<操作符的重载函数，所以我们没有办法直接打印AA的内容。我们可以通过解引用迭代器，然后使用.来访问AA的成员变量。


既然我们知道迭代器返回的其实就是一个指针，那么我们为什么不直接使用->符号来访问AA的成员变量呢，而是要先解引用迭代器，然后再使用.来访问AA的成员变量。这是因为我们只实现了迭代器结构体__list_iterator的*操作符的重载函数，而没有实现该结构体的->操作符的重载函数。所以下面我们来实现->的重载函数。


在使用->符访问AA的成员变量时，其实应该是两个->，因为第一个->是调用->符的重载函数，第二个->是通过地址访问_a1，但是为了增强可读性，省略了一个。

我们发现const_iterator迭代器使用->操作符的重载函数可以修改list中元素的值，这是肯定不正确的，所以接下来我们实现const版本的->操作符重载函数，禁止const_iterator迭代器使用->操作符的重载函数修改list中元素的值，所以又要加一个模板参数。

此时我们就可以看到const_iterator迭代器使用->操作符的重载函数不能修改list中元素的值了。

下面我们来实现insert和erase函数。
insert为在当前位置的前面插入元素，所以我们可以这样实现。当实现了insert后，头插尾插就可以复用insert函数来实现了。并且我们看到库里面的insert函数返回了一个迭代器，该迭代器指向刚被插入的元素。

下面我们来实现erase函数。然后我们再复用erase函数来实现头删和尾删。我们看到在库里面的erase函数也返回了一个迭代器，并且该迭代器指向被删除的结点的下一个结点。
我们需要注意的是在erase之后迭代器必定失效，因为pos指向的结点已经被释放了。

我们在上面相当于写了三个类，这三个类都是使用模板来实现的。而类名加模板参数才是真正的类型，即list< int >才是真正的类型，其中list为类名，int为模板参数。
我们模拟实现的list迭代器创建了一个__list_iterator结构体来实现，我们可以查看VS下的vector的迭代器类型，因为VS下vector的迭代器不是靠原生指针实现的，我们可以看到VS下的vector迭代器的类型更加复杂。


下面我们来实现list类的析构函数，析构函数就是将list创建的list结点全部都释放。在实现析构函数之前我们可以先实现clear函数，clear函数也是释放list创建的全部结点，只不过clear函数不会释放头结点。
下面是复用erase函数实现的clear函数，将除了头结点的其它结点全部释放。

还可以使用下面的方法来实现clear，我们在上面说了erase之后it迭代器会失效，那么为什么在这里it迭代器没有失效呢？
这是因为后置++中，我们使用传值返回，所以erase(it++)其实delete释放的是it的拷贝，即erase中delete的是tmp迭代器指向的node结点，而此时it迭代器已经指向下一个元素结点了。


当实现了clear函数后，此时list中就只有头结点了，所以我们实现list类的析构函数是可以复用clear函数，然后再将list的头结点delete就可以了。

下面我们再来实现迭代器区间构造函数，因为迭代器区间构造函数就不会调用list的默认构造函数将_head头结点进行初始化了，所以我们在迭代器区间构造函数中还要将_head头结点进行初始化，这里我们封装一个empty_init函数用来初始化_head头结点，我们在list的默认构造函数和迭代器区间构造函数中都调用这个empty_init函数。

下面我们来实现list类的拷贝构造函数，因为有时候会调用拷贝构造函数来构造一个新list对象，所以拷贝构造函数也需要调用empty_init函数来将_head头结点进行初始化。

如果在拷贝构造函数中没有初始化头结点，则就会出现异常。这是因为lt2对象就是调用拷贝构造函数来创建的，而拷贝构造函数中并没有进行_head头结点的初始化，即根本没有申请头结点的空间，所以头结点的的next和prev都不可访问，因为根本没有申请空间。


上面我们使用正常的方法来实现拷贝构造函数，下面我们使用一种比较简便的方法来实现拷贝构造函数。
调用迭代器区间构造函数创建一个临时对象tmp，此时tmp对象就是lt对象的副本，然后我们调用swap函数交换this和tmp的_head头结点，然后this就变为了lt对象的副本了，而此时tmp指向的_head头结点就是this原来的数据，而因为tmp为临时对象，所以出了拷贝构造函数tmp对象就会调用析构函数而销毁了。然后我们测试发现程序又出现了异常，这还是因为拷贝构造函数没有初始化_head头结点。


当我们将头结点初始化之后，发现程序就可以正常运行了。

下面我们再来使用同样的方法实现赋值运算符重载函数，需要注意的是赋值运算符重载函数的形参不能为引用，如果为引用的话就会出现问题。下面我们先写正确的赋值运算符重载函数。
因为赋值运算符重载函数重载函数的形参为传值传参，所以在lt2=lt1时调用赋值运算符重载函数时会先调用拷贝构造函数创建临时对象lt，而lt就是拷贝lt1对象创建的，然后调用swap函数将this指向的对象的头结点和lt对象的头结点进行交换，则此时this指向的对象就和lt1对象的内容一致了，而lt临时对象的内容就是lt2对象原来的内容，因为lt对象为临时对象，所以当出了赋值运算符重载函数时，lt对象就会调用析构函数销毁，即lt对象的析构函数就将lt2对象原来的结点都销毁了。

下面我们来看为什么赋值运算符重载函数的形参不可以使用引用。我们可以看到此时lt2=lt1调用赋值运算符重载函数后，发现并不是将lt1对象的内容赋值给lt2对象了，而是交换了lt2对象和lt1对象的内容。这是因为当赋值运算符重载函数的形参为引用时，就不会调用拷贝构造函数来创建临时变量lt，所以此时swap(lt)函数其实就是交换了lt2对象和lt1对象的内容。


但是如果当我们在赋值运算符重载函数中使用下面的方法时，就可以将赋值运算符重载函数的参数设为传引用传参了，即当需要交换时，我们先创建一个临时对象tmp，并且这个临时对象tmp拷贝lt1的内容，即为lt1的副本，然后我们使用swap函数交换tmp和lt2对象的头结点，这样lt2就为lt1的副本了，即和lt1的内容一样了。

下面为list类模拟实现的代码。

#pragma once
#include
#include
#include
#include
using namespace std;
namespace dong
{
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _data;

		//因为T可能为任意类型，所以我们创建一个T类型的匿名对象，然后调用该类型的默认构造参数对该匿名对象进行初始化。
		list_node(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{

		}
	};

	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* n)
			:_node(n)
		{

		}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const self& s)
		{
			return _node != s._node;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
	};

	/*template
	struct __list_const_iterator
	{
		typedef list_node node;
		typedef __list_const_iterator self;
		node* _node;

		__list_const_iterator(node* n)
			:_node(n)
		{

		}

		const T& operator*()
		{
			return _node->_data;
		}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_data;
			return tmp;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const self& s)
		{
			return _node != s._node;
		}
		bool operator!=(const self& s)
		{
			return _node != s._node;
		}
	};*/

	template<class T>
	class list
	{
		typedef list_node<T> node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<T, const T&, const T*> const_iterator;
		iterator begin()
		{
			/*iterator it(_head->_next);
			return it;*/
			//上面的代码会先调用__list_iterator的构造函数，然后return返回时又调用__list_iterator的拷贝构造函数。

			//所以我们返回一个匿名对象，编译器会进行优化，将构造+拷贝构造优化为 -> 构造
			return iterator(_head->_next);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		const_iterator end() const
		{
			return const_iterator(_head);
		}
		void empty_init()
		{
			//初始化头结点
			_head = new list_node<T>;
			_head->_next = _head;
			_head->_prev = _head;
		}
		list()
		{
			empty_init();
		}
		template <class Iterator>
		list(Iterator first, Iterator last)
		{
			//先初始化头结点
			empty_init();
			while(first != last)
			{
				push_back(*first);
				++first;
			}
		}

		//原始方法
		//list(const list& lt)
		//{
		//	empty_init();
		//	for (auto e : lt)
		//	{
		//		push_back(e);
		//	}
		//}

		//下面使用现代方法实现拷贝构造函数
		void swap(list<T>& tmp)
		{
			std::swap(_head, tmp._head);
		}
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void push_back(const T& x)
		{
			先找到尾结点，即头结点的上一个结点
			//node* tail = _head->_prev;
			创建新结点,并且调用list_node的构造函数对该结点进行初始化
			//node* new_node = new node(x);

			在头结点前插入新结点
			//tail->_next = new_node;
			//new_node->_prev = tail;
			//_head->_prev = new_node;
			//new_node->_next = _head;

			//end()就是有效结点的下一个结点，所以在end()前插入一个结点就是在list最后插入一个结点。
			insert(end(), x);
		}

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

		iterator insert(iterator pos, const T& x)
		{
			node* cur = pos._node;
			node* prev = cur->_prev;
			node* new_node = new node(x);

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

			return iterator(new_node);
		}

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

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

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

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				//erase每次会返回指向下一个结点的迭代器，所以每次都会更新it迭代器。
				//it = erase(it);

				//还可以使用这种方法来实现clear
				erase(it++);
			}
		}

		list<T>& operator=(list<T>& lt)
		{
			swap(lt);
			return *this;
		}
	private:
		//list的头结点
		list_node<T>* _head;
	};


	void Test01()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

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

	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//(*it) *= 2;
			cout << *it << " ";
			++it;
		}
		cout << endl;


	}

	struct AA
	{
		int _a1;
		int _a2;
		AA(int a1 = 0, int a2 = 0)
			:_a1(a1)
			, _a2(a2)
		{

		}

	};

	void Test02()
	{
		list<AA> lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));

		list<AA>::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << *it << " ";
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
			cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;
			//本来应该是两个->，但是为了增强可读性，省略了一个->
			cout << it->_a1 << ":" << it->_a2 << endl;

			++it;
		}
		cout << endl;

	}


	void print_list01(const list<AA>& lt)
	{
		list<AA>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//(*it) *= 2;
			cout << it->_a1 << " " << it->_a2 << endl;
			++it;
		}
		cout << endl;
	}


	void Test03()
	{
		list<AA> lt;
		lt.push_back(AA(1, 1));
		lt.push_back(AA(2, 2));
		lt.push_back(AA(3, 3));
		print_list01(lt);
	}

	void Test04()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.insert(++(lt1.begin()), 5);

		lt1.push_back(10);
		lt1.push_front(0);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		lt1.erase(++(lt1.begin()));
		lt1.pop_back();
		lt1.pop_front();
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void Test05()
	{
		char array[] = "abcdef";
		list<int> lt1(array, array + sizeof(array) / sizeof(array[0]));

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

	}

	void Test06()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt2(lt1);
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;
		
	}

	void Test07()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.push_back(5);

		list<int> lt2;
		lt2.push_back(10);
		lt2.push_back(20);
		lt2.push_back(30);
		cout << "lt2=lt1前，lt1和lt2的值" << endl;
		cout << "lt1:";
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << "lt2:";
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;
		lt2 = lt1;
		
		cout << "lt2=lt1后，lt1和lt2的值" << endl;
		cout << "lt1:";
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << "lt2:";
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		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
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
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495