【STL】list容器

1.1 list容器基本概念

功能：将数据进行链式存储
链表（list）是一种在物理存储单元上不连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
链表的组成：一系列的节点组成
节点的组成：一个存储数据元素的数据域，另一个是存储下一个节点地址的指针域
STL中的链表是一个双向循环链表
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器

list容器的优点：

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

list容器的缺点：

• 链表灵活，但是空间（指针域）和时间遍历额外耗费比较大

list有一个很重要的性质，插入操作和删除操作，都不会造成原有list迭代器的实效，这在vector是不成立的。

总结：STL中list和vector是两个最常用的容器，各有优缺点

1.2 list构造函数

功能描述：

• 创建list容器

函数原型：

list<T> lst; //list采用采用模板类实现,对象的默认构造形式：
list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem); //构造函数将n个elem拷贝给本身。
list(const list &lst); //拷贝构造函数。

示例：

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);
	printList(l2);

	list<int> l3(l2.begin(), l2.end());
	printList(l3);

	list<int> l4;
	l4 = l3;
	printList(l4);
}

总结：list构造函数和其他STL常用的容器一样

1.3 list容器赋值和交换

功能描述：

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

函数原型：

assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem); //将n个elem拷贝赋值给本身。
list& operator=(const list &lst); //重载等号操作符
swap(lst); //将lst与本身的元素互换。

示例：

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;
	L2 = L1;
	printList(L2);

	list<int> L3;
	L3.assign(L2.begin(), L2.end());
	printList(L3);

	list<int> L4;
	L4.assign(10, 100);
	printList(L4);

	//交换
	L4.swap(L3);
	cout << "交换后：" << endl;
	printList(L3);
	printList(L4);
}

1.4 list容器大小操作

功能描述：

• 对list容器大小进行操作

函数原型：

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

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

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

​ //如果容器变短，则末尾超出容器长度的元素被删除。

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

示例：

void test01()
{
	list<int>L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);

	if (L1.empty())
	{
		cout << "L1为空" << endl;
	}
	else
	{
		cout << "L1不为空" << endl;
		cout << "L1的大小为：" << L1.size() << endl;
	}

	//重新指定大小
	L1.resize(10);
	printList(L1);

	L1.resize(2);
	printList(L1);
}

总结：

• 判断是否为空——empty（）
• 返回元素个数：size（）
• 重新指定个数——resize（）

1.6 list容器插入和删除

功能描述：

• 对list容器进行数据的插入和删除

函数原型：

push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。

示例：

void test01()
{
	list<int> L;
	//尾插
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	//头插
	L.push_front(100);
	L.push_front(200);
	L.push_front(300);
	printList(L);

	//尾删
	L.pop_back();
	printList(L);

	//头删
	L.pop_front();
	printList(L);

	//插入
	list<int>::iterator it = L.begin();//迭代器
	L.insert(++it, 1000);
	printList(L);

	//删除
	it = L.begin();
	L.erase(++it);
	printList(L);

	//移除
	L.push_back(250);
	L.push_back(250);
	L.push_back(250);
	printList(L);
	L.remove(250);//把数字250都给删了
	printList(L);

	//清空
	//L.clear();
	L.erase(L.begin(), L.end());
	printList(L);
}

总结：

• 尾插——push_back()
• 头插——push_front()
• 尾删——pop_back()
• 头删——pop_front()
• 插入——insert()
• 删除——erase()
• 移除——remove()
• 清空——clear()

1.7 list容器存取

功能描述：

• 对list容器中的数据进行存取

函数原型：

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

示例：

void test01()
{
	list<int> L;
	L.push_back(10);
	L.push_back(20);
	L.push_back(30);
	L.push_back(40);
	L.push_back(50);
	printList(L);
	cout << "第一个元素为：" << L.front() << endl;
	cout << "第二个元素为：" << L.back() << endl;
	//list容器的迭代器是双向迭代器，不支持随机访问
	list<int>::iterator it = L.begin();
	//it = it + 1;//错误 不可以跳跃访问 
	it++;//这是正确的
}

总结：

• list容器中不可以通过 [] 或者 at 方式访问数据
• 返回第一个元素——front（）
• 返回最后一个元素——back（）

1.8 list容器反转和排序

功能描述：

• 将常用的元素反转，以及将容器中的数据进行排序

函数原型：

reverse(); //反转链表
sort(); //链表排序

示例：

bool myCompare(int val1, int val2)
{
	return val1 > val2;
}

void test01()
{
	list<int> L;
	L.push_back(6);
	L.push_back(2);
	L.push_back(5);
	L.push_back(1);
	printList(L);

	//反转容器中的元素
	L.reverse();
	printList(L);

	//排序
	L.sort();//默认的排序规则——从小到大
	printList(L);

	L.sort(myCompare);//指定规则，从大到小
	printList(L);
}

总结：

• 反转——reverse（）
• 排序——sort（）（这里的sort函数是成员函数 L.sort()）

1.9 list容器的排序案例

案例描述：将Person自定义数据类型进行排序，Person中的属性有姓名、年龄和身高
排序规则：按照年龄进行升序，若果年龄相同的话按照身高进行降序

示例：

class Person
{
public:
	string m_name;
	int m_age;
	int m_height;
public:
	Person(string name, int age, int height)
	{
		m_name = name;
		m_age = age;
		m_height = height;
	}
};

bool myCompare(Person& p1, Person& p2)
{
	if (p1.m_age == p2.m_age)
	{
		return p1.m_height > p2.m_height;
	}
	else
	{
		return p1.m_age < p2.m_age;
	}
}

void test01()
{
	list<Person> L;
	//创建对象
	Person p1("张三", 15, 170);
	Person p2("李四", 18, 180);
	Person p3("王五", 27, 175);
	Person p4("老六", 18, 160);
	Person p5("老八", 15, 175);

	//存取数据
	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);

	//打印数据
	for (list<Person>::iterator it = L.begin(); it != L.end(); ++it)
	{
		cout << "姓名：" << it->m_name << " 年龄：" << it->m_age << " 身高：" << it->m_height << endl;
	}
	cout << "----------------------" << endl;
	L.sort(myCompare);//排序
	//打印数据
	for (list<Person>::iterator it = L.begin(); it != L.end(); ++it)
	{
		cout << "姓名：" << it->m_name << " 年龄：" << it->m_age << " 身高：" << it->m_height << endl;
	}
}

总结：对于自定义数据类型的排序，我们必须指出排序规则