C++ STL进阶与补充（list容器）

链表的数据采用链式存储，其是一种物理存储单元上非连续的数据结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表由一系列结点构成。

节点中一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

STL中的链表是一个双向循环链表（有两个指针，一个指前面一个指后面，最后的指针指向最前的地址）。

链表可以在任意位置插入和删除元素，省去了数据移动的操作。

链表的缺点：1、容器的遍历速度不如数组，因为地址不是连续的。2、占用的空间比数组大。

链表的优点：1、采用动态存储分配，不会浪费内存，造成溢出。2、链表的插入和删除十分方便，修改指针即可，不需要移动大量元素。

链表的迭代器是双向迭代器，仅支持前移和后移。不能跳跃式访问。

STL中链表和向量是最常用的两个容器。

1、list构造函数

#include<list>
#include<iostream>
using namespace std;
void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << endl;
	}
}
void test01()
{
	list<int> l1;  //默认构造
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	printList(l1);  //遍历容器
 
	list<int> l2(l1.begin(), l1.end());  //区间方式构造
	printList(l2);
 
	//拷贝构造
	list<int> l3(l2);
	printList(l3);
}
int main()
{
	test01();
}

2、list赋值与交换

给list容器进行赋值，以及交换list容器。

#include<list>
#include<iostream>
using namespace std;
void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	list<int> l1;  
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	list<int> l2=l1;
	printList(l2);
 
	list<int> l3(l2.begin(),l2.end());
	printList(l3);
}
int main()
{
	test01();
}

3、list大小操作

对list容器的大小进行操作。

#include<list>
#include<iostream>
using namespace std;
void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	list<int> l1;  
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	printList(l1);
	if (l1.empty())
	{
		cout << "l1为空。" << endl;
	}
	else
	{
		cout << "l1不为空。" << endl;
		cout << "l1的元素个数为：" << l1.size() << endl;
	}
	//重新指定大小
	l1.resize(10);
	printList(l1);
}
int main()
{
	test01();
}

4、list插入和删除

#include<list>
#include<iostream>
using namespace std;
void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
void test01()
{
	list<int> l1;  
	//尾插
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	//头插
	l1.push_front(100);
	l1.push_front(200);
	l1.push_front(300);
	printList(l1); //300 200 100 10 20 30
	//尾删
	l1.pop_back();
	printList(l1); //300 200 100 10 20
	//头删
	l1.pop_front();
	printList(l1); //200 100 10 20
	//插入
	list<int>::iterator it=l1.begin();
	l1.insert(++it, 1000);
	printList(l1); //200 1000 100 10 20
	//删除
	it = l1.begin();
	l1.erase(it);
	printList(l1); //1000 100 10 20
	//移除10
	l1.remove(10);
	printList(l1); //1000 100 20
	//清空
	l1.clear();
	printList(l1);
}
int main()
{
	test01();
}

5、list数据存取

List不支持[]和at访问里面的数据，不支持随机访问。

6、list反转和排序

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

不支持随机访问迭代器的容器，内部会使用成员函数提供相应的算法。

#include<list>
#include<iostream>
using namespace std;
void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
bool Compare(int v1, int v2)  //通过compare制定排序规则
{
	//如果v1>v2，则为降序
	return v1 > v2;
}
void test01()
{
	list<int> l1;  
	l1.push_back(10);
	l1.push_back(50);
	l1.push_back(30);
	l1.push_back(20);
	cout << "反转前：" << endl;
	printList(l1);
	l1.reverse();
	cout << "反转后：" << endl;
	printList(l1);
	//排序
	l1.sort();
	cout << "排序后：" << endl;
	printList(l1);
	//降序排列
	l1.sort(Compare);
	printList(l1);
}
int main()
{
	test01();
}