STL中的list容器

一. list的几点说明

1. list是带头双向循环链表，初始化有3中方式：有名，匿名，隐式类型转换
2. list与其他容器不同的是：list访问，遍历的核心是迭代器。在list中没有operator[]这个接口，想实现的话倒是可以实现，但是遍历的效率会特别低。
3. list的物理空间不连续，逻辑空间是连续的
4. list的插入（insert）和vector相似，但是不是利用[]，而是迭代器
5. swap：算法库和list中都有swap，算法库中的swap是深拷贝，效率低。list中的swap是交换哨兵位的头结点。

6. 迭代器

（1）迭代器的定义：每一种容器都有对应类型的迭代器，也就是，不同容器的迭代器也不同，其功能强弱也有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。
（2）分类
按照使用划分：迭代器，const迭代器，反向迭代器，const反向迭代器
按照功能划分：单向迭代器，双向迭代器，随机迭代器

二. 接口

1.初始化

一定要记得展开命名空间，如果不写list是哪里的，会报错

list是在标准库里面的

//常规：一个一个插入
std::list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
for (auto a : lt1)
{
	std::cout << a<<" ";
}
std::cout << std::endl;

//有名
class Pos
{
public:
	int _row;
	int _col;
	Pos(int row=0,int col=0)
		:_row(row)
		,_col(col)
	{}
	Pos(const Pos& p)
		:_row(p._row)
		,_col(p._col)
	{}
};
int main()
{
	std::list<Pos> lt1;
	Pos pos1 = (2, 3);
	lt1.push_back(pos1);
	return 0;
}

//匿名
class Pos
{
public:
	int _row;
	int _col;
	Pos(int row=0,int col=0)
		:_row(row)
		,_col(col)
	{}
	Pos(const Pos& p)
		:_row(p._row)
		, _col(p._col)
	{}
};
int main()
{
	std::list<Pos> lt1;
	lt1.push_back(Pos(2, 3));
	return 0;
}

//隐式类型转换（对于自定义类型，花括号一般是隐转）
class Pos
{
public:
	int _row;
	int _col;
	Pos(int row=0,int col=0)
		:_row(row)
		,_col(col)
	{}
	Pos(const Pos& p)
		:_row(p._row)
		, _col(p._col)
	{}
};
int main()
{
	std::list<Pos> lt1;
	lt1.push_back({ 1, 2 });
	return 0;
}

2. 构造

int main()
{
	//explicit list (const allocator_type& alloc = allocator_type());
	//无参构造
	std::list<int> lt1;
	return 0;
}

int main()
{
	//explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
	//               容器的size          用来初始化容器的值              
	std::list<int> lt1(8,3);    //n个val构造
	return 0;
}

这个样子是不对的，初始化的时候才这么写

int main()
{
	//template <class InputIterator>
	//list(InputIterator first, InputIterator last,const allocator_type & alloc = allocator_type());
	//迭代区间构造
	std::string s1("hello China");
	std::list<int> lt1(s1.begin(),s1.end());
	return 0;
}

int main()
{
	std::list<int> lt1(3, 1);
	std::list<int> lt2(lt1);
	return 0;
}

3. 迭代器的使用

正向迭代器

反向迭代器

范围for

4. emplace_back和push_back

（1）push_back可以隐式类型转换，

	std::list<Pos> lt1;
	lt1.push_back({ 1, 2 });

将实参{1,2}隐式转换为形参T即Pos类型的
（2）emplace_back不可以隐式类型转换，隐式它的形参是template <class... Args>，形参类型未知，并不知道将实参转换成什么类型。

5. insert

我们首先要找到postion，需要使用find。但list没有，只能通过算法库find来实现了。
insert和算法库的find搭配使用
（InputIterator也称作单向迭代器，只可以++）

InputIterator find (InputIterator first, InputIterator last, const T& val);

注意：对于list的insert的pos位置不会失效，在这个地方，只是在pos位置前增加节点，改变链接，pos位置并不会变成野指针。

6. swap

void swap (list& x);

int main()
{
	//void swap(list & x);
	std::list<int> lt1 = { 1,2,3,4,5 };
	std::list<int> lt2 = { 9,9,9,9,9,9 };
	lt1.swap(lt2);
	for (auto a : lt1)
	{
		std::cout << a << " ";
	}
	std::cout << std::endl;
	return 0;
}

7. resizse

void resize (size_type n, value_type val = value_type());

8.erase

注意：对于list的erase的pos位置是会失效的，删除之后，如果直接进行访问会直接报错，此时的pos已经是野指针了。

int main()
{
	std::list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
	lt.push_back(5);
	//iterator erase(iterator position);
	auto it = find(lt.begin(), lt.end(), 3);
	lt.erase(it);
	//iterator erase(iterator first, iterator last);
	lt.erase(it, lt.end());
	return 0;
}

9. remove删除

先说明一下remove和（find+erase）的区别，

void remove (const value_type& val);
iterator erase (iterator position);

remove是传值，erase是传迭代器。
remove就算没有要删除的那个值，也不会报错。

8. sort 排序

算法库有sort已经有sort了，为什么list还重新有一个sort呢？

还记得之前说，list的物理空间不连续。算法库里的sort对于物理空间是连续的(只有vector和string)能够使用，而对于list来说，物理空间并不是连续的，并不适用，所以list自己提供了一个sort进行排序。

9. unique 去重

删除链表中连续的重复元素，但是注意：一定是要先排完序再进行删除，如果没有进行排序：而直接进行去重的话，会导致去重去不完全

10. splice

int main()
{
	std::list<int> lt1(4, 9);
	std::list<int> lt2(3,8);
	//           postion,list& x
	lt2.splice(lt2.begin(),lt1);
	for (auto a : lt2)
	{
		std::cout << a << " ";
	}
	std::cout << std::endl;
	//9，9，9，9，8，8，8
	return 0;
}

int main()
{
	std::list<int> lt1(4, 9);  //9,9,9,9
	std::list<int> lt2(3, 8);  //8,8,8
	//void splice(iterator position, list& x, iterator i);
	lt2.splice(lt2.begin(), lt1,lt1.begin());
	for (auto a : lt2)
	{
		std::cout << a << " ";
	}
	std::cout << std::endl; 
	//9,8,8,8
	return 0;
}

int main()
{
	std::list<int> lt1(4, 9);  //9,9,9,9
	std::list<int> lt2(3, 8);  //8,8,8
	//void splice (iterator position, list& x, iterator first, iterator last);
	lt2.splice(lt2.begin(), lt1, lt1.begin(),lt1.end());
	for (auto a : lt2)
	{
		std::cout << a << " ";
	}
	std::cout << std::endl;
	//9,9,9,9,8,8,8
	return 0;
}