STL链表list。

STL中的链表是一个双向循环链表。

其存储结构并非连续的内存空间，所以list的迭代器只支持前移和后移，它是双向迭代器，而不是像vector那样的随机访问迭代器。

list的优缺点

优点：

• 采用动态存储分配，不会造成内存浪费和溢出
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

缺点：

• 比数组要额外存储指向下一个节点的指针，需要额外耗费空间。
• 不支持随机访问，额外耗费较大。

与vector相比：插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

• 暂未验证

list的使用

list<T> lst; //list采用采用模板类实现,对象的默认构造形式：

list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。

list(n,elem); //构造函数将n个elem拷贝给本身。

list(const list &lst); //拷贝构造函数。

assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

assign(n, elem); //将n个elem拷贝赋值给本身。

list& operator=(const list &lst); //重载等号操作符

swap(lst); //将lst与本身的元素互换。

size(); //返回容器中元素的个数

empty(); //判断容器是否为空

resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。
			//如果容器变短，则末尾超出容器长度的元素被删除。

resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。

push_back(elem);//在容器尾部加入一个元素

pop_back();//删除容器中最后一个元素

push_front(elem);//在容器开头插入一个元素

pop_front();//从容器开头移除第一个元素

insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。，pos是迭代器

insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。pos是迭代器

insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。pos是迭代器

clear();//移除容器的所有数据

erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。

erase(pos);//删除pos位置的数据，返回下一个数据的位置。

remove(elem);//删除容器中所有与elem值匹配的元素。

front(); //返回第一个元素。

back(); //返回最后一个元素。

reverse(); //反转链表

sort(); //链表排序

• remove(elem) 是按照值匹配而移除， erase按照迭代器的指向而移除。
• list不支持随机访问，所以它没有[]或者at(index)这样的vector类似的方法。

list的迭代器

list由于是链表实现，其迭代器不能像vector的迭代器那样强大。

list的迭代器只能做简单的自增1，自减的操作

list<int> li;

for (int i = 0; i < 100; i+=2) {
    li.push_back(i);		//尾插
    li.push_front(i + 1);	//头插
}

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

it++; //正确
it--;//正确

// it += 1;错误
// it + 1;错误
// it + 3;错误

list的sort排序

所有不支持随机访问迭代器的容器，都不可以使用标准算法。

//自己实现的比较函数
bool myCompare(int &a,int &b) {
    //a > b时返回true
	return a > b;
}


void test3() {

	list<int> li;

	for (int i = 0; i < 100; i += 2) {
		li.push_back(i);		//尾插
		li.push_front(i + 1);	//头插
	}

	//遍历结果
	list<int>::iterator it = li.begin();
	for (; it != li.end(); it++)
		cout << *it << " ";
	cout << endl;

	li.sort();		//默认排序，由小到大

	it = li.begin();
	for (; it != li.end(); it++)
		cout << *it << " ";
	cout << endl;

	//由大到小排序
	li.sort(myCompare);	//传入自己实现的回调函数或者仿函数

	it = li.begin();
	for (; it != li.end(); it++)
		cout << *it << " ";
	cout << endl;

}

总结：

1. 算法<algorithm>有sort()排序算法，但是这个算法是只支持可以随机访问的容器。由于list不支持，所以其自己提供了实现函数。
2. 对于自定义的数据类型，使用list存储，如果需要进行排序，必须要自行指定排序规则。

unique() —— 去重函数

unique() 是删除容器中相邻重复的元素。

所以应当先进行排序，使用list的sort()，然后再调用unique，才能尽可能地删去重复地元素。

使用情景

• 注意list不支持随机访问、使用下标进行访问。只能从头遍历整个链表。