C++STL——list

C++教学总目录

1、list简介

list是带头双向循环链表，也是模板类，使用时要指明类型，包含于头文件<list>
由于list是双向循环链表，在任意位置的插入删除的效率非常高，都是O(1)，所以list提供了头插头删和尾插尾删的接口。

2、构造函数

第一个就是默认构造函数，第二个支持用n个val来初始化链表，第三个支持迭代器区间初始化，最后一个就是拷贝构造函数了。使用如下：

string s = "hello world";
list<int> lt1;			// 默认构造函数
list<int> lt2(10, 1);	// 创建10个结点赋值为1
list<int> lt3(lt2.begin(), lt2.end()); // 同类型迭代器区间初始化
list<char> lt4(s.begin(), s.end());    // 使用string的迭代器区间初始化
list<int> lt5(lt2);     // 拷贝构造

3、迭代器

list的迭代器使用方法同vector和string。所以只要学会一种类型的迭代器使用，其他类型迭代器都会使用了。
但是list的迭代器和vector、string的迭代器有所不同。

algorithm库中有三个常用的函数：reverse、sort、find。先来看看这三个函数：



观察这三个函数，你会发现他们的模板参数取名是不同的。
实际上这三个函数并不是任何容器的迭代器都可以使用的，他们是有区别的。

迭代器有三种类型：单向迭代器、双向迭代器、随机迭代器。

从这三个函数的模板参数命名也可以看出来，find传单向迭代器就可以使用，sort需要传随机迭代器，reverse需要传双向迭代器。
基于list底层的性质，list只能是双向迭代器，所以不能使用sort对list进行排序，因为sort需要随机迭代器。
而像vertor和string底层都是指针，可以对指针++/–/+/-,所以它们的迭代器都是随机迭代器，上面三个函数都可以使用。

下面遍历list：

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
// 使用迭代器遍历list
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
	cout << *it << " ";
	++it;
}
cout << endl;

// 使用范围for遍历list——底层还是迭代器
for (auto e : lt)
{
	cout << e << " ";
}
cout << endl;

4、访问和容量函数

empty判断链表是否为空。
size返回链表中结点个数。
max_size表示链表可以存储的最多结点——不同平台下不同，没什么意义
front返回链表头结点元素
back返回链表尾结点元素

5、修改类函数

1、assign函数就是把链表中所有结点清空，然后重新初始化。

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> lt2(10, 1);
lt2.assign(lt.begin(), lt.end());
lt2.assign(10, 2);

2、push_front是头插，pop_front是头删，push_back是尾插，pop_back是尾删。

3、insert函数：支持在某个位置插入一个数据、支持在某个位置插入n个数据、支持在某个位置插入一段迭代器区间。

insert的使用这里就不介绍了，详情可以看之前的string和vector，string和vector会用这里肯定也会用。现在来思考一下list的迭代器insert之后会失效吗？

观察这段代码，it指向3，当调用insert之后，在3的前面插入了10，然后再对it所指向的元素做修改，之后打印输出我们发现3确实被改成100了。所以list这里insert之后迭代器并不会失效，因为这里插入是new一个结点然后进行前后连接。而之前vector那里可能会发生扩容，扩容后迭代器就失效了。
insert的返回值是插入新元素的迭代器。

4、erase函数：支持删除某个位置的元素、支持删除一段迭代器区间

erase之后迭代器会失效吗？答案肯定是会失效，因为指向的那个结点空间被释放了，所以迭代器失效。所以erase返回值是删除元素的下个位置。

5、swap函数就是交换两个list的值，类似前面vector和string。clear就是清除所有数据。resize也是类型vector的，开空间+初始化。

6、操作类函数

1、reverse函数就是逆置，这里其实可以直接使用算法库的reverse函数逆置，没必要在list中再实现reverse函数。

2、sort函数是用来给list中数据排序的，因为算法库中的sort函数得是随机迭代器才能使用，而list是双向迭代器，所以不能使用算法库中的sort函数，因此在list类实现了sort函数，这个函数使用的是归并排序。但是这个函数的效率非常低，如果在数据量比较大的情况下，我们可以把数据拷贝到vector中存储，然后使用算法库中的sort快排，再把数据拷回list中，这样的效率更高。

3、merge函数用来合并两个链表：

使用如下：

std::list<double> first, second;

first.push_back(3.1);
first.push_back(2.2);
first.push_back(2.9);

second.push_back(3.7);
second.push_back(7.1);
second.push_back(1.4);
first.sort();
second.sort();
first.merge(second);
cout << "first:";
for (const auto& e : first)
{
	cout << e << " ";
}
cout << endl;
cout << "second:";
for (const auto& e : second)
{
	cout << e << " ";
}
cout << endl;

调用了merge之后，将second中的所有结点合并到first链表中，second中就没有结点了。当然merge函数的使用前提是两个链表都有序。

4、unique函数用来去重：如果链表中有多个相同的数据，可以使用unique来去重

使用unique的前提也是链表必须有序。

5、remove_if是给一个函数，然后把满足条件的值全部去掉。

使用如下：

这里我们实现了一个test函数，当x<10时返回true。我们在调用remove_if时将函数地址传过去，当满足条件时——返回true时就将元素删掉。所以小于10的元素全部被去除了。

6、remove函数很简单，就是把你所给的值的元素删掉。

7、splice函数是拼接（更形象来说时转移）：支持在某个位置拼接list、支持在某个位置拼接list对象的某个结点、支持在某个位置拼接list的一段迭代器区间

使用如下：

#include <iostream>
#include <vector>
#include <string>
#include <list>

using namespace std;


int main()
{
	list<int> mylist1, mylist2;
	list<int>::iterator it;
	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++;

	// 全部转移到mylist1
	mylist1.splice(it, mylist2);
	
	for (auto e : mylist1)
	{
		cout << e << " ";
	}
	cout << endl;

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

	return 0;
}

上面的代码将mylist2中的所有结点转移到了mylist1中第一个结点的后面。

把上面调用splice的语句换成：

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

现在就变成了将mylist2中第二个结点转移到mylist1的第一个结点后面。

我们再把代码换成：

mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());

现在是把mylist1中第一个结点后面的所有结点转移到mylist1的第一个结点前面。
需要注意的是：使用splice进行转移时，可以对同一个list进行转移，但是要保证区间不能重叠，如果区间重叠就会出问题。