stl_list

stl容器中的list实现了带头循环双向链表，以高效地进行插入和删除操作，但随机访问的性能相对较差。

一.list的基本操作 

1.list的构造函数

list的构造函数与vector的构造函数相类似，都提供了四个接口

list<int> il1;
list<int> il2(3, 1);
list<int> il3(++il2.begin(), --il2.end());
list<int>li4(il2);

2.迭代器

在string和vector时，从功能方面我们将迭代器分为四种：

• iterator——正向迭代器
• reverse_iterator——反向迭代器
• const_iterator——只读正向迭代器
• const_reverse_iterator——只读反向迭代器

 而到list，我们不仅要从迭代器的功能来分类，还要从迭代器的性质来分类。而迭代器从性质上可以分为三种：

• random iterator——随机迭代器
• bidirectional iterator——双向迭代器
• forward iterator——单向迭代器

性质的不同表现在迭代器可以支持的操作不同：

random iterator的意思就是可以借助迭代器访问任意一个位置的元素，它可以使用+/-，++/--等操作，其底层结构就是数组，因其结构连续，迭代器类似与原生指针，+/-即可指向指定的元素位置。例如：vector、string

bidirectional iterator的意思是迭代器只支持++/--等操作，不支持+/-操作，其底层是一些内存不连续容器，其可以通过++/--的运算符重载达到下一个/上一个位置，但不可以通过+/-常数直接跳到指定位置。例如：list、map、set

forward iterator的意思就是迭代器只支持++操作，迭代器只能向前走，不能向后走。例如：forward_list（单链表）

性质的不同，导致各种容器在调用算法库中的函数时对迭代器有要求： 

对于逆置函数来说，它要求传的是双向迭代器。但是我们在之前string的时候，也使用了reverse。但是string的迭代器是随机迭代器，这是为什么呢？

其实双向迭代器支持的，随机迭代器也支持，所以reverse要求传双向迭代器只是要求迭代器要支持++以及--操作。

所以双向迭代器就像是单向迭代器的子类，不仅包含了父类(单向迭代器)的性质，也有自己特有的性质。而随机迭代器就像是双向迭代器的子类。

3.在指定位置插入删除

因为list的迭代器是双向迭代器，所以如果像在指定位置插入数据的话，是不能使用begin+N来实现的：

 我们可以借助下面的方式来实现在指定位置的插入：

list<int> il1;
il1.push_back(1);
il1.push_back(2);
il1.push_back(3);
il1.push_back(4);
il1.push_back(5);
il1.push_back(6);

int x = 0;
cin >> x;
auto iter = il1.begin();
while (x--)
{
	++iter;
}
il1.insert(iter, 100);

如果我们想要在3之前插入100，我们只需要让x==2，再++iter两次，就到了3的位置，然后再调用insert即可。

 删除指定位置的元素我们可以借助find来实现：

int y = 0;
cin >> y;
iter = find(il1.begin(), il1.end(), y);
if (iter != il1.end())
{
	il1.erase(iter);
}

4.resize

list中并没有扩容的概念，所里resize在这里只是对节点个数进行操作。

n>size，用指定数据创建节点，直到有n个节点，如果没有指定数据则使用默认值

n<size，删除节点个数，只保留前n个。

il.resize(8, 10);

il.resize(2);

il.resize(5);

5.sort

算法库中的sort要求的是random iterator，而list的是双向迭代器，所以无法调用算法库中的sort来排序

但是list不能不排序啊，所以list实现了自己的sort 

il.sort();

但是list中的sort默认排升序，如果想要排降序的话，要使用伪函数

less<int> ls;//升序
greater<int> gt;//降序

调用该函数时，就可以实现排降序

 6.test_sort

比较同样的数据，分别用vector和list来存储，比较vector采用的算法库中的sort与list自己的sort

void test_op1()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	vector<int> v;

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

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

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

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

再比较有同样数据的两个list，一种采用直接调用sort，一种采用先拷贝数据到vecor中，再使用库中的sort再将数据拷贝回来，这两种的时间消耗：

void test_op2()
{
	srand(time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

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

	int begin1 = clock();
	// 拷贝vector
	vector<int> v(lt2.begin(), lt2.end());

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

	// 拷贝回lt2
	lt2.assign(v.begin(), v.end());

	int end1 = clock();

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

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

 总结：

        对存储同样数据的list和vector来说，vector采取库中的sort排序效率比list用自己的sort效率高。

        对存储同样数据的两个list1和list2来说，list1采取借助vector排序的效率比直接用sort的效率高。

7.merge 

合并两个有序链表，当作参数的那个链表将变为空。

8.unique

删除链表中的重复项，只保留一个。

9.remove/remove_if 

remove就是删除链表中指定的元素 

remove if就是删除满足条件的元素 

bool is_even_numbers(const int& val)
{
	return val % 2 == 0;
}

il.remove_if(is_even_numbers);

如上，就是删除偶数

10. splice

splice其实就是剪切操作，将指定内容从指定对象复制下来，并粘贴到指定位置，且原内容就不存在了。

二.list的模拟实现

1.list的结构

list就是一个维护若干个节点连接起来的链式结构，它指向这个结构的哨兵位，所以list的成员变量其实就是一个指向链表哨兵位的指针以及一个记录节点个数的_size.

而一个一个的节点也是一个结构，里面包含了数据以及指向前一个和后一个节点的指针。

//节点
template<typename T>
struct List_node
{
	T _data;
	List_node<T>* _prev;
	List_node<T>* _next;
};

template<typename T>
class list
{
	typedef struct List_node<T> node;

private:
	node* _head;
	size_t _size;
};

2.list无参构造

初始化链表，其实就是创建一个哨兵位，其前驱指针和后续指针都指向其自己。这里的一个一个的节点也是一个类，所以我们也要显示写出其默认构造。

//节点初始化
List_node(const T& val = T())
	:_data(val)
	,_prev(nullptr)
	,_next(nullptr)
{}

list()
{
	_head = new node;
	_head->_prev = _head;
	_head->_next = _head;

	_size = 0;
}

3.push_back()

首先创建新节点，然后找到尾节点，让尾节点的next->newnode，newnode->prev指向尾节点，然后newnode->next指向_head，_head的prev指向newndoe。

void push_back(const T& val)
{
	node* newnode = new node(val);

	node* tail = _head->_next;
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;

	++_size;
}

 4.iterator

由于list的结构，其在内存中是不连续的，且数据是存储在一个一个的节点中，解引用拿不到数据而是一个节点，++到不了下一个节点，是一个随机的位置。 所以list的迭代器不能简单地用原生指针来替代，我们要对其进行封装，对运算符进行重载，使其解引用可以拿到数据，++可以走到下一个节点的位置。

//迭代器
template <typename T>
struct List_iterator
{
	typedef struct List_node<T> node;
	typedef struct List_iterator<T> Self;
	node* _node;

	List_iterator(node* node) :
		_node(node)
	{}


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

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

		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

有了迭代器我们就可以遍历链表：

5.按需实例化与const_iterator

为了方便我们可以写一个打印函数，用来打印容器，这样就不必每一次都写范围for来打印了。

template<typename Container>
void print_container(const Container& con)
{
	/*auto iter = con.begin();
	while (iter != con.end())
	{
		cout << *iter << " ";
		++iter;
	}*/

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

我们这里写可以打印任意容器：

 该容器这所以可以打印这两个容器，是因为vector和string的库中都实现了const_iterator。而我们模拟实现的list却还没有实现const_iterator，所以当打印list时就会出错。

 但是当我们不调用print_container时，编译器就不会报错。这是为什么？明明没有实现const_iterator？

这就是按需实例化。我们没有调用print_container，所以编译器就只会简单的扫描一下该函数内部有没有大的语法错误，是不会检查那些细节的。只有我们调用了该函数，对其进行了实例化，此时编译器才会仔细地检查该函数的细节。

解决这个问题，我们只需要实现const_iterator即可：

方案一：

        实现一个const_iterator类，虽然该类也可以解决问题，但是该类和iterator这个类高度重合，代码冗余

//const迭代器
template <typename T>
struct const_List_iterator
{
	typedef struct List_node<T> node;
	typedef struct const_List_iterator<T> Self;
	node* _node;

	const_List_iterator(node* node) :
		_node(node)
	{}


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

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

		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

方案二： 

我们在实现iterator类模板时多传2个模板参数，一个作为T类型的引用，一个作为T类型的指针。

template <typename T, typename Ref ,typename Ptr>
struct List_iterator

然后我们在list类模板内部typedef时，根据模板参数的不同，来实现不同的迭代器：

typedef struct List_iterator<T,T&,T*> iterator;
typedef struct List_iterator<T,const T&,const T*> const_iterator;

我们利用iterator模板生成了两个不同的类，一个被typedef成iterator，一个被typedef成const_iterator.

本质上，方案二和方案一是没有区别的，都是生成了两个不同的类，只不过一个是自己显示写出来的，一个是编译器替我们生成的。 

6.operator->

 当我们list存储的数据是一个结构体时，我们想要打印里面的值时，就不能直接使用范围for打印了：

因为AA这个结构体没有重载流插入， 我们可以重载流插入来解决这个问题

ostream& operator<<(ostream& out, AA a)
{
	out << a._a << ":" << a._b;

	return out;
}

当然也可以换一种打印方式：

 我们还可以通过重载->来实现该效果：

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

operator->返回的是T*,也就是AA*，在使用->就可以拿到AA里面的数据。

cout << iter->_a << ":" << iter->_b << endl;
//cout << iter.operator->()->_a << ":" << iter.operator->()->_b << endl;

上面的写法省略了一个->，实际上是两个->，第一个拿到T*，在对T*解引用拿到里面的数据，但是为了可读性省略了一个->。

7.insert()

insert之后迭代器不失效，因为p并没有因为插入一个节点而导致变化。

void insert(iterator p, const T& val)
{
	node* newnode = new node(val);
	
	node* prev = p._node->_prev;

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

	newnode->_next = p._node;
	p._node->_prev = newnode;

	++_size;
}

当我们实现了insert后，push_back()/push_front都可以复用insert来实现：

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

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

8.erase()

我们可以看到，erase之后p所在的节点已经被释放掉了，此时p就是一个野指针，所以erase之后，迭代器就是失效了，不要访问，如果要访问的话，就要更新p。 

我们看到标准库中的erase是返回了删除位置元素的下一个元素的迭代器。

iterator erase(iterator p)
{
	assert(p != end());

	node* prev = p._node->_prev;
	node* next = p._node->_next;

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

	delete p._node;
	p._node = nullptr;
	--_size;

	return next;
}

 pop_back()/pop_front()

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

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

9.~list()

 析构函数就是一个节点一个节点的销毁即可，我们可以借助clear来实现，clear是清楚链表中的数据，我们在析构函数中调用该函数即可，最后在释放掉哨兵位。

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

void clear()
{
	auto iter = begin();
	while (begin() != end())
	{
		iter = erase(iter);
	}
}

10.拷贝构造

实现拷贝构造我们可以先构造一个哨兵位出来，然后再向哨兵位后面尾插数据即可。

void emptyinit()
{
	_head = new node;
	_head->_prev = _head;
	_head->_next = _head;

	_size = 0;
}

list(const list<T>& t)
{
	emptyinit();

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

11.赋值运算符重载

赋值运算符重载采取现代写法

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

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