C++：list（用法篇+模拟实现）

文章目录

前言
一、list 的用法
- 1. list 简介
- 2. 用法代码演示
- - 1）头/尾插/删和迭代器遍历
  - 2）insert与erase
  - 3）排序sort相关
  - 4）其他相关
二、list模拟实现
- 1. 结点类模板list_node
- 2. 定义迭代器
- - 1）为什么要专门封装一个迭代器？
  - 2）迭代器类的实现
  - - （1）普通迭代器
    - - 初始化
      - operator*与operator->
      - operator++
      - operator!=
    - （2）const迭代器——参数T以及为什么有三个参数？
    - （3）迭代器代码实现
- 3. list类实现
- - 1）成员变量
  - 2）迭代器接口相关
  - 3）构造相关
  - 4）插入删除相关
  - - （1）insert与erase及其迭代器失效问题
    - （2）头插/头删/尾插/尾删
三、list与vector对比
模拟实现list完整代码

前言

今天我们一起来看看C++中stl库里list是什么样子的，以及模拟实现list~

在这里插入图片描述

一、list 的用法

1. list 简介

在这里插入图片描述

第一个参数是模板类型，第二个参数是空间配置器我们先暂时不管他。

list的在stl中就是一个双向带头循环链表，它的使用比vector简单一些。

stl这些风格接口都是一样的，他的构造也是这样。
在这里插入图片描述

因为list是链式结构，因此他的访问和遍历不会用到operator[]，而是通过迭代器来遍历，对于插入删除操作除了push_back,insert等等这些,还提供了头插头删这样的接口，因为他们不用进行数据的挪动。

2. 用法代码演示

1）头/尾插/删和迭代器遍历

#include<list>

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	lt.push_front(30);
	lt.push_front(88);

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

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

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

	lt.pop_front();
	lt.pop_front();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

2）insert与erase

首先，list的底层空间不是连续的，不能直接通过偏移量访问指定位置（如lt.begin() + 5会报错）。其次，insert操作不会导致迭代器失效，因为list的插入操作不需要扩容，插入后迭代器仍指向有效的逻辑位置。相反，erase操作会导致迭代器失效，删除后需要用返回值更新迭代器以避免野指针。最后，在删除元素时（如删除偶数），应通过erase返回的迭代器更新循环变量，确保迭代器有效。

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

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

	//list的空间不是连续的，+5 并不能找到list中第5个位置，这样写编译器会报错的
	//lt.insert(lt.begin() + 5, 10);

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

	lt.insert(it, 89);

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

	//对于insert，迭代器不会失效，因为插入数据list不牵扯扩容，it所指向的逻辑位置也不发生改变
	//库里的没找到会返回last的位置

	it = find(lt.begin(), lt.end(), 3);
	if (it != lt.end())
	{
		lt.insert(it, 30);

		// insert以后，it不失效
		*it *= 100;
	}
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//但是对于erase，使用过后迭代器会失效
	it = find(lt.begin(), lt.end(), 2);
	if (it != lt.end())
	{
		lt.erase(it);

		// erase以后，it失效，她的空间已经没了，就是一个野指针
		//*it *= 100;
	}
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//要解决这个问题，可以拿iterator做返回值接收，更新it的值
	it = lt.begin();
	
	//还是我们的老朋友，删除list中偶数
	while (it != lt.end())
	{
		if (*it % 2 == 0)
		{
			//就是这里
			it = lt.erase(it);
		}
		else
			it++;

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

3）排序sort相关

由于list的迭代器是双向的，不能直接用标准库的sort（因为那是针对随机访问迭代器设计的快排），所以list自带了sort方法，它内部用的是归并排序。接着，代码还演示了两种反转方式：你可以用标准库的reverse函数，也可以直接用list的reverse方法。二者效果相同。
在这里插入图片描述

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

	//库中的sort不可以，因为库中的排序是快排，迭代器的种类是随机，而这里迭代器的种类是双向
	//sort(lt.begin(), lt.end());

	//因此库中提供了一种底层为归并排序的排序
	lt.sort();
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

	//list中还有类似逆置，交换这样的，库中和这里的都可以用
	reverse(lt.begin(), lt.end());
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;

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

当然，list中的排序我们是不建议用的，要对list中的数据进行排序，我们应该将其转化成vector，然后调用快排，最后在拷贝回去。

下面这是一段性能测试的代码：
可以看到，越大数据下快排性能越好

void test_op()
{
	srand(time(0));
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	list<int> lt1;
	list<int> lt2;

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

	// 拷贝到vector排序，排完以后再拷贝回来
	int begin1 = clock();
	// 先拷贝到vector
	for (auto e : lt1)
	{
		v.push_back(e);
	}

	// 排序
	sort(v.begin(), v.end());

	// 拷贝回去
	size_t i = 0;
	for (auto& e : lt1)
	{
		e = v[i++];
	}

	int end1 = clock();

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

	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

4）其他相关

第一是remove，它用来删除链表中指定的值，找到了就删，找不到就不做任何操作。这个操作比较简单直接。

第二个是unique，它用来去除链表中的重复元素，但通常需要先排序，这样可以确保去重更高效。unique只会保留相邻元素中的一个，所以排序是去重前的重要一步。

第三个是splice，它用来将一段结点转移到另一个结点的后面。splice有几种用法，可以转移整个list、单个元素或一段区间的元素。splice不会创建新元素，而是直接在链表节点间重新链接，效率很高。

void test04()
{
	int myints[] = { 17,89,7,14 };
	/*std::list<int> mylist(myints, myints + 4);

	//remove是删除特定的值，找到了就删除，没找到就什么也不干
	mylist.remove(890);

	for (auto e : mylist)
	{
		cout << e << " ";
	}
	cout << endl*/;

	//unique是去重，一般要先排序，这要去重效率高
	//mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,
	 15.3,  72.25, 72.25, 73.0,  73.35

	//mylist.unique();           //  2.72,  3.14, 12.15, 12.77
	 15.3,  72.25, 73.0,  73.35



	std::list<int> mylist1, mylist2;
	std::list<int>::iterator it;

	// set some initial values:
	for (int i = 1; i <= 4; ++i)
		mylist1.push_back(i);      // mylist1: 1 2 3 4

	for (int i = 1; i <= 3; ++i)
		mylist2.push_back(i * 10);   // mylist2: 10 20 30

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

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

	it = mylist1.begin();
	++it;                         // points to 2

	//转移是从iterator的位置，转移另一个list （整个/第i个位置/一个迭代区间）
	// 全部转移
	mylist1.splice(it, mylist2);

	// 部分转移
	//mylist1.splice(it, mylist2, ++mylist2.begin());
	//mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());

	//转移自己
	//mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());

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

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

二、list模拟实现

1. 结点类模板list_node

首先，要写出一个list，就需要先写出它的每一个结点的构成，这里的结构是我们之前学过的双向链表，为了泛用性，list的结点数据可以是任意类型的数据，因此我们需要写成类模板。

与双向链表一样，我们这里有三个变量分别是_next（后继）, _prev（前驱）, val（值），
并利用初始化模板将其初始化

template<class T>
struct list_node
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _val;

	list_node(const T& val = T())
		:_next(nullptr)
		,_prev(nullptr)
		,_val(val)
	{}
};

2. 定义迭代器

1）为什么要专门封装一个迭代器？

list不想string和vector，它们两个的底层是由数组实现的，它们的迭代器就是其原生指针，因为原生指针就可以满足迭代器的行为。

迭代器所需要做到的行为如下：
*：解引用获取迭代器对应的值，类似与指针解引用获得值
!=：如：判断迭代器到没到end（）等应用
++/--：迭代器迭代到下一个地点

对于vector来说，他的迭代器可以完美符合以上几点，因为vector底层空间是连续的，是数组，就像这样：

在这里插入图片描述

但是，对于list还能这样吗？
答案是不能，因为list底层不是连续的，*it并不是对应的值，而是一个结点,++it并不能让it指向下一个结点，因为空间是不连续的，++后指到哪里谁也不知道。

因此现有的迭代器的行为不符合我们的预期，我们期望的是迭代器表层使用的方式是一致的，因此我们写一个类，封装迭代器,用运算符重载来改变迭代器的行为，使他符合我们的预期。

2）迭代器类的实现

（1）普通迭代器

初始化

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

operator*与operator->

我们先不关心它的返回值，我们先来让他符合我们的预期。

我们想让*返回的不是它的结点，而是结点中的值。
我们想让->返回的是T类型值（结构体）的地址。
注意：
在这里插入图片描述

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

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

operator++

我们想让operator++能到下一个结点的位置，--同理，因此需要让_node = _node->next，而不是指针地址的++,因为结点与结点之间空间是不连续的。

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

operator!=

我们想让迭代器的对应的结点与结点比较，而不是迭代器本身。

bool operator!= (const self& it)
{
	return _node != it._node;
}

bool operator== (const self& it)
{
	return _node == it._node;
}

（2）const迭代器——参数T以及为什么有三个参数？

在学习list迭代器的封装时，我们发现了一个很神奇的现象，就是迭代器的模板参数居然有3个！！！

这是为什么呢？

有T在这个地方我们都能理解，因为迭代器的类型就是T，也就是我们list的类型，那为什么还要这个Ref和Ptr呢？

其实原因都是const迭代器搞的鬼。

我们在实现const的版本的时候，遇到一些非常坑的问题。

首先，这样设计const迭代器可以吗？
// typedef const __list_iterator<T> const_iterator;
答案是不可以，因为这样设计const迭代器是不行的，因为const迭代器期望指向内容不能修改
这样设计是迭代器本身不能修改，我们迭代器本身是要++的，不能改变的是它的值。

第二个问题，我们发现，const迭代器与普通迭代器的不同仅仅是因为迭代器所指向的值不能修改，那const迭代器不就是重载operator*的时候加一个const吗？
//typedef __list_const_iterator const_iterator;
但是问题是，这样设计太冗余了，有大量重复的代码，改变的仅仅是operator*前加const以及函数名字。

因此我们的解决方法是：增加一个模板参数Ref，它的作用是typedef定义const_iterator的时候，传得参数有一个是const与普通迭代器不一样，而operator*的返回值就使用Ref.
而Ref就是T的引用，与返回值保持一致.

像这样：

那么，第三个参数Ptr是什么呢？

类似于operator*，在对自定义类型解引用的方式还有->。

比如我们下面有一个类：

class A
{
public:
	A(int a = 0, int b = 0)
		: _a(a)
		, _b(b)
	{}

	int _a;
	int _b;
};

我们想对这个类用迭代器遍历它的值有两种方式：

通过重载的operator*解引用，然后.出A类的_a和_b.
通过operator->直接访问到_a和_b.

在这里插入图片描述

而对于const对象，我们就不能直接调用operator->，因为会造成权限放大，所以我们引入了第三个模板参数Ptr表示T类型的指针，用它来区别const对象和普通对象。
因此operator->的返回值就成了Ptr。
在这里插入图片描述

实际上，传不同的模板参数，就是生成了不同的模板，我们这样写其实就是让编译器帮我们写了之前那个冗余的写法，是我们代码更简洁，可读性更高~

（3）迭代器代码实现

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)
	{}

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

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

	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& it)
	{
		return _node != it._node;
	}

	bool operator== (const self& it)
	{
		return _node == it._node;
	}

};

3. list类实现

1）成员变量

对于每一个链表，我们需要直到它的哨兵位，还有它的大小。

private:
	Node* _head;
	size_t _size;

2）迭代器接口相关

前面我们定义了迭代器类，现在我们要用它获取begin()与end()。

对于带头双向循环链表来说，begin()是第一个位置的元素，也就是哨兵位的下一个，end()是最后一个元素的下一个位置，也就是又回到了哨兵位。

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

iterator begin()
{
	//这里做了隐式类型转换
	return _head->_next;
	//也可以写成这样
	//return iterator(head->_next);
}

iterator end()
{
	//这里做了隐式类型转换
	return _head;
	//也可以写成这样
	//return iterator(head);
}

const const_iterator begin() const
{
	return _head->_next;
}

const const_iterator end() const
{
	return _head;
}

3）构造相关

构造函数：

void empty_init()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	_size = 0;
}

list()
{
	empty_init();
}

拷贝构造：
这里依然沿用vector那里拷贝构造的思想，复用push_back来做到深拷贝。

list(const list<T>& lt)
{
	empty_init();

	for (auto& e : lt)
	{
		push_back(e);
	}
}

赋值重载
使用现代写法。

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

T& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

析构函数
复用clear，再把头结点清理掉。

对于clear来说，vector的空间要释放必须完全释放，所以它只清理值，不回收空间，而list结点之间不连续，因此可以直接回收空间，当然，哨兵位是不动的。

~list()
{
	clear();

	delete _head;
	_head = nullptr;
}

void clear()
{
	iterator it = begin();

	while (it != end())
	{
		it = erase(it);
	}

	_size = 0;
}

4）插入删除相关

（1）insert与erase及其迭代器失效问题

insert任意位置插入
逻辑完全就是双链表的逻辑，先开辟出新结点空间，在改变对应的指向。

insert无法对pos进行断言，哪里插入都可以。

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

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

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

	++_size;

	return newnode;
}

因为list空间是不连续的，因此这里也不用扩容，对于insert来说，迭代器不失效。

erase删除任意位置的数据

erase需要对pos位置进行断言，pos不能改变我们的头结点，而end()就是头结点。

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

	return next;
}

因为删除了这一个结点，而迭代器又指向这个结点空间，因此erase后迭代器会失效，是铁铁的野指针！

（2）头插/头删/尾插/尾删

逻辑与vector一样，直接复用insert与erase就好。

void push_back(const T& x)
{
	/*Node* newnode = new Node(x);

	newnode->_next = head;
	newnode->_prev = head->_prev;
	head->_prev->_next = newnode;
	head->_prev = newnode;*/

	insert(end(), x);
}

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

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

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

三、list与vector对比

下面是 vector 和 list 的对比表格，涵盖了它们的主要特性和性能：

特性	`vector`	`list`
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率 O(1)	不支持随机访问，访问某个元素效率 O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度 O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为 O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针，对原生态指针（节点指针）进行封装	迭代器封装了节点指针
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问

总结

vector 更适合需要频繁随机访问和对存储效率要求较高的场景，但在插入和删除时性能较低。
list 更适合需要频繁插入和删除操作的场景，尤其是在中间位置进行操作时效率高，但不支持随机访问。

模拟实现list完整代码

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;

namespace jyf
{

	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

		list_node(const T& val = T())
			:_next(nullptr)
			,_prev(nullptr)
			,_val(val)
		{}
	};

	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)
		{}

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

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

		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& it)
		{
			return _node != it._node;
		}

		bool operator== (const self& it)
		{
			return _node == it._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()
		{
			//这里做了隐式类型转换
			return _head->_next;
			//也可以写成这样
			//return iterator(head->_next);
		}

		iterator end()
		{
			//这里做了隐式类型转换
			return _head;
			//也可以写成这样
			//return iterator(head);
		}

		const const_iterator begin() const
		{
			return _head->_next;
		}

		const const_iterator end() const
		{
			return _head;
		}


		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}

		list()
		{
			empty_init();
		}

		list(const list<T>& lt)
		{
			empty_init();

			for (auto& e : lt)
			{
				push_back(e);
			}
		}

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

		T& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		~list()
		{
			clear();

			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			iterator it = begin();

			while (it != end())
			{
				it = erase(it);
			}

			_size = 0;
		}

		void push_back(const T& x)
		{
			/*Node* newnode = new Node(x);

			newnode->_next = head;
			newnode->_prev = head->_prev;
			head->_prev->_next = newnode;
			head->_prev = newnode;*/

			insert(end(), x);
		}

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

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

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

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

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

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

			++_size;

			return newnode;
		}

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

			return next;
		}

		size_t size()
		{
			return _size;
		}

	private:
		Node* _head;
		size_t _size;
	};

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

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

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

		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

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

	class A
	{
	public:
		A(int a = 0, int b = 0)
			: _a(a)
			, _b(b)
		{}

		int _a;
		int _b;
	};

	void test_list02()
	{
		list<A> lt;
		lt.push_back(A(1, 1));
		lt.push_back(A(2, 2));
		lt.push_back(A(3, 3));
		lt.push_back(A(4, 4));

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

		it = lt.begin();
		while (it != lt.end())
		{
			cout << it->_a << " " << it->_b << endl;
			++it;
		}
		cout << endl;


	}

	void test_list03()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(5);
		lt.push_front(6);
		lt.push_front(7);
		lt.push_front(8);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		lt.pop_front();
		lt.pop_back();

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

		lt.clear();
		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		lt.push_back(40);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

		cout << lt.size() << endl;
	}

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

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

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

		list<int> lt2;
		lt2.push_back(10);
		lt2.push_back(20);
		lt2.push_back(30);
		lt2.push_back(40);

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

		lt1 = lt2;

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