[18] C++STL容器篇之链表list

• C++STL容器篇之链表list
• • C++STL的list的底层原理
  • list的创建方式
  • list的遍历方式
  • list的一些常用的成员函数
  • 主函数测试一下

其实它的底层就是数据结构的双向链表。可以从头遍历，也可以从尾遍历的那个，但不是循环的。在STL中就把这样的一个双向链表封装成一个类，方便开发人员直接使用，避免重复造轮子。

关于list的方式，这就要看list这个类的里面有多少个构造函数了。事实就是有很多种。

以下的创建方式都是正确的：

list myList;
list myList2(3);
list myList3(myList2);

其实除了上面列举的之外还有其他的创建方式，但推荐用第一种。有必要的时候就用第三种，第二种的话就感觉没啥必要，这个就看个人需要吧，万一哪天使用到了呢。

• 第一种是只创建了一个链表，但没有节点，要使用它的时候先给他插入几个节点才能使用。
• 第二种是在一开始的时候就给链表分配了3个节点，默认初始化都是零。（数值类的是零，字符串就是空串）
• 第三种是将一个已经存在的链表赋值给新的链表。

初学者会以上的三种list的方式就差不多了，其他的可以自己到编译器上玩。

因为list不像array和vector那样是顺序的，所以不能通过中括号加下标的方式进行访问list中的数据。但是它的遍历方式还是挺多的，我知道的有四种：

• 新版for循环方式遍历
• 迭代器方式遍历
• 获取头部元素，删除头部元素，循环遍历
• 获取尾部元素，删除尾部元素，循环遍历

先说第一个，这个很简洁，根本不需要内部怎么进行，一个auto自动推断搞定，看一下具体的代码实现：

list myList2(3);
for (auto v : myList2)
{
	cout << v << 't';
}
cout << endl;

打印出来的都是零。（默认初始化为零）

第二种遍历方式是采用迭代器的方式遍历链表元素，写的时候比较长一点，看一下代码实现：

list myList;
list::iterator iter;
for (iter = myList.begin(); iter != myList.end(); iter++)
{
	cout << *iter << 't';
}
cout << endl;

第三种遍历方式有点意思的，就是用循环去遍历，打印第一个节点的元素，打印完后就把第一个节点删掉，然后用第二个节点充当第一个节点，一直循环到链表没有节点为止，这种方式的遍历，会让链表为空，前面两种方式遍历，就不会将链表的节点删除。

#include 
#include 
using namespace std;
int main()
{
	list List;
	cout << "链表的大小为：" << List.size() << endl;
	List.assign(3, 6);
	for (auto v : List)
	{
		cout << v << 't';
	}
	cout << endl;
	List.push_front(99);
	List.push_back(1001);
	cout << List.front() << endl;
	cout << List.back() << endl;
	List.insert(List.begin(), 2, 88);
	for (auto v : List)
	{
		cout << v << 't';
	}
	cout << endl;
	List.sort();
	list::iterator iter;
	for (iter = List.begin(); iter != List.end(); iter++)
	{
		cout << *iter << 't';
	}
	cout << endl;
	list result = {1,2,3};
	cout << result.size() << endl;
	List.merge(result);
	for (auto v : List)
	{
		cout << v << 't';
	}
	cout << endl;
	//1       2       3       6       6       6       88      88      99      1001
	cout << result.size() << endl;
	List.pop_front();
	List.pop_back();
	for (auto v : List)
	{
		cout << v << 't';
	}
	cout << endl;
	//2       3       6       6       6       88      88      99
	list::iterator iter1, iter2;
	iter1 = iter2 = List.begin();
	iter1++;
	advance(iter2, 5);
	iter1 = List.erase(iter1);
	iter2 = List.erase(iter2);
	for (auto v : List)
	{
		cout << v << 't';
	}
	cout << endl;
	//2       6       6       6       88      99
	cout << List.size() << 't' << *iter1 << 't' << *iter2 << endl;
	List.erase(iter1, iter2);
	cout << List.size() << endl;
	for (auto v : List)
	{
		cout << v << 't';
	}
	cout << endl;
	//2       88      99
	List.clear();
	cout << List.size() << endl;	//0
	return 0;
}

输出结果：

链表的大小为：0
6       6       6
99
1001
88      88      99      6       6       6       1001
6       6       6       88      88      99      1001
3
1       2       3       6       6       6       88      88      99      1001
0
2       3       6       6       6       88      88      99
2       6       6       6       88      99
6       6       88
3
2       88      99
0