前言

我们前面已经对string和vector进行了学习使用，以及对他们的底层进行了模拟实现！本期我们继续学习STL的另外一个容器---list。

本期内容介绍

什么是list？

list的常用接口

什么是list?

还是来看看官方的文档说明！

这里通过官方文档我们可以知道！list是一个带头双向循环的链表！在插入和删除时，时间复杂度是常量级别的！

list常用接口

在正式的开始介绍接口使用前，我们还是来了解一下类型重命名！

这里主要用到的就是上面的三个! value_type 就是T， reference 是value_type&, size_type 就是size_t

构造、拷贝构造、赋值拷贝、析构

list<int> lt1;//空构造

list<int> lt2(10, 6);//n 个 val构造

vector<int> v = { 1, 2,4,56,7,8,-1 };

list<int> lt3(v.begin(), v.end());//迭代器区间构造

list<int> lt4(lt2);//拷贝构造

这里除了介绍这些常见的外！这里在穿插一个C++11引入的一个非常好用的，初始化序列初始化！

这个在上期vector的模拟实现已经介绍了，auto ret = {1,2,3};此时的ret就是initializer_list<int>。

list<int> lt5 = { 1,2,3,4,5 };//C++11的初始化序列初始化

list<int> lt4(lt2);//拷贝构造

list<int> lt5 = { 1,2,3,4,5 };//C++11的初始化序列初始化

lt5 = lt4;//赋值拷贝

析构还是一样的：清理资源、释放空间~！

迭代器

正向

list<int> lt = { 1,2,3,4,5 };//C++11的初始化序列初始化
const list<int> clt = { 10, 20,30, 40 };

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

list<int>::const_iterator cit = clt.begin();//const正向
while (cit != clt.end())
{
	cout << *cit << " ";
	++cit;
}
cout << endl;

支持迭代器必然支持范围for,范围for就是傻傻的替换迭代器！

反向

list<int>::reverse_iterator it = lt.rbegin();//反向
while (it != lt.rend())
{
	cout << *it << " ";
	++it;
}
cout << endl;

list<int>::const_reverse_iterator cit = clt.rbegin();//const反向
while (cit != clt.rend())
{
	cout << *cit << " ";
	++cit;
}
cout << endl;

const和非const的区别主要还是权限的问题~！如果不修改建议使用const的！！！

注意：这里的迭代器需要指定类域的原因是模板的原因，模板参数不一样就是一个类，为了让迭代器用法统且不冲突，需要指定是哪个类的迭代器~！

容量

empty

list<int> lt = { 1,2,3,4,5,6,7,8,9 };
bool ret = lt.empty();
cout << ret << endl;

size

list<int> lt = { 1,2,3,4,5,6,7,8,9 };
size_t sz = lt.size();
cout << sz << endl;

元素访问

这里文档上说的很清楚：如果是空链表的话，你去取头和尾的数据是未定义的行为！！因为当链表为空时，头尾就是哨兵位的头结点，我们只是规定头结点的next指向实际链表的第一个节点，_prev指向对后一个元素，并未规定头结点的数据域存的是啥，所以如果为空链表，你去取就是未定义行为！

这和begin迭代器不一样，迭代器是返回链表的元素，这里是返回引用！

list<int> lt = { 1,2,3,4,5,6,7,8,9 };
int front = lt.front();
int back = lt.back();

cout << front << " " << back << endl;

const list<int> clt = { 10, 20,30, 40 };
int cfront = clt.front();
int cback = clt.back();

cout << cfront << " " << cback << endl;

修改

删除的这三个是涉及右值引用！在后面的C++11那一期会专门介绍~！

assign

list<int> lt = { 1,2,3,4,5,6,7,8,9,10 };
list<int> lt2;
list<int> lt3 = { 0, 2,4,6,8 };
lt.assign(5, 1);
for (auto& e : lt)
{
	cout << e << " ";
}
cout << endl;

lt2.assign(++lt3.begin(), --lt3.end());
for (auto& e : lt2)
{
	cout << e << " ";
}
cout << endl;

这个和构造函数那里很像，但是不一样！这个是已经存的你再去把他的原来内容用指定的内容替换掉！

push_front

list<int> lt = { 1,2,3,4 };
lt.push_front(0);
for (auto& e : lt)
{
	cout << e << " ";
}
cout << endl;

pop_front

list<int> lt = { 1,2,3,4 };

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

push_back

list<int> lt = { 1,2,3,4 };

lt.push_back(-5);
for (auto& e : lt)
{
	cout << e << " ";
}
cout << endl;

pop_back

list<int> lt = { 1,2,3,4 };

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

insert

list<int> lt = { 1,2,3,4 };
lt.insert(lt.begin(), 0);//在pos位置插入一个val

lt.insert(++lt.begin(), 5, -1);//在pos位置插入n个val

vector<int> v = { 90, 98, 23,34,56 };
lt.insert(lt.begin(), v.begin(), v.end());//在pos位置插入一个迭代器区间

erase

list<int> lt = { 1,2,3,4 };
lt.erase(lt.begin());//删除pos位置的元素

lt.erase(++lt.begin(), lt.end());//删除一段迭代器区间

resize

由于是链表，所以不用考虑扩容的问题！这里的resize就要变成了尾插和尾插了！

list<int> lt = { 1,2,3,4 };

lt.resize(3);//相当于尾删，只保留前n个元素

lt.resize(10, 0);//相当于尾插到节点数目为10，不够的就是0

swap

还是和前面的两个容器的一样，他这里的是对list对象的属性进行交换！

list<int> lt1 = { 1,2,3,4 };
list<int> lt2 = { 10,20,30,40 };

lt1.swap(lt2);

clear

list<int> lt = { 1,2,3,4 };

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

其他操作

splice

splice是粘结，结合的意思！这个接口的作用是转移链表的元素！重载了三个：

将一个链表的数据转移到另一个链表的pos位置

将一个链表的i位置的元素转移到另一个链表的pos位置

将一个链表的一个迭代器区间转移到另一个链表的pos位置

list<int> lt1 = { 1,2,3,4,5,6,7,8,9 };
list<int> lt2 = { 0, -1,-2 };

lt1.splice(lt1.begin(), lt2);//在pos位置，将x转移过来

lt2.splice(lt2.end(), lt1, ++lt1.begin());//在pos位置将x的i位置的一个元素转移过来

lt2.splice(++lt2.begin(), lt1, ++lt1.begin(), --lt1.end());//在pos位置将x的一段迭代器区间给转移过来

remove

这个函数的作用是：删除所有特定的值！

list<int> lt = { 2,3,2,2,2,4,5,6,1,2 };
lt.remove(2);
print(lt);

remove_if

这个函数的作用是删除符合条件的元素，这里的形参可以是一个对象，也可以是一个函数指针！

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

struct single_digit
{
	bool operator() (const int& val)
	{
		return val < 10;
	}
};

void test_list7()
{
	list<int> lt = { 2,3,2,2,2,4,5,6,1,2,21,11,23 };

	lt.remove_if(is_odd);
	print(lt);

	lt.remove_if(single_digit());
	print(lt);
}

unique

一看名字就知道这是去重的，但是这个去重是去重连续相邻的重复元素！

list<int> lt = { 2,3,2,2,2,2,4,5,6,1,2,21,11,23 };

lt.unique();
print(lt);

merge

这接口的作用就是：合并两个链表！但注意：这两个链表必须是有序的！！！！

list<int> lt1 = { 1,3,7,8,9 };
list<int> lt2 = { 2,4,5,7,9 };

lt1.merge(lt2);
print(lt1);
print(lt2);//此时lt2是空的

sort

这个接口的作用是：对链表进行排序！它的底层是归并排序！

list<int> lt = { 1,3,2,1,-1,7,8,9 };

lt.sort();
print(lt);

但是这个效率就很，，，不太好~！不是归并不行，是链表排序不太行！

OK，举个例子：

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

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

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

这个代码是将同样的数据插入到一个vector和一个list，分别对他们排序，看他们排序花费的时间！

差了两倍多！！！再来看一个：

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

这个代码是：先将两个链表插入相同的数据，在将一个放到vector中排序，然后再拷回来，一个是直接调用链表的sort！

直接差了4倍！所以，list的这个sort效率真不咋地，建议少用~！

reverse

这个函数的作用就是反转链表！

list<int> lt = { 1,2,3,4,5,6,7,8 };
lt.reverse();
print(lt);

非成员函数swap

有这个接口的原因和前面的几个容器一样！防止调到标准库里面的那个！

list<int> lt1 = { 1,2,3};
list<int> lt2 = { 10,20,30, 50};

swap(lt1, lt2);
print(lt1);
print(lt2);

OK，本期内容就分享到这里，我们下期再见~！

结束语：不要因为别人的三言两语就打破你的深思熟虑！