1.list容器简介

  list是序列容器,允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作,并在两个方向进行迭代。list容器是一个双向循环链表。

  •  list容器与vector容器区别:

   ①list中空间是随机的,通过指针域保存下一个成员地址;vector容器空间是连续的;
   ② list容器数据插入和删除方便,能合理的利用空间;vector容器则是没法实时分配资源;

2.list容器构造函数

list容器构造函数:
	list< T > p;//默认构造
	list(begin,end);//区间赋值
	list(int num,elem);//num个elem值
	list(const list &p);//拷贝构造
	取头数据:front()
	取尾数据:back();
	互换成员swap();
  •  使用示例:

#include <iostream>
using namespace std;
#include <list>
/*遍历*/
void PrintList(const list<int>& p, int flag)
{
	if (flag == 1)//正向遍历
	{
		cout << "正向遍历:" << endl;
		for (list<int>::const_iterator ptr = p.begin(); ptr != p.end(); ptr++)
		{
			cout << *ptr << " ";
		}
	}
	else //逆向遍历
	{
		cout << "逆向遍历:" << endl;
		for (list<int>::const_reverse_iterator ptr = p.rbegin(); ptr != p.rend(); ptr++)
		{
			cout << *ptr << " ";
		}
	}
	cout << endl;
}
void test()
{
	list<int> lst;//默认构造
	//尾插法
	lst.push_back(100);
	lst.push_back(200);
	//头插法
	lst.push_front(300);
	lst.push_front(400);
	PrintList(lst, 1);
	PrintList(lst, 0);
	list<int> lst2(lst.begin(), lst.end());//区间赋值
	cout << "lst2第一个成员:" << lst2.front() << endl;
	cout << "lst2最后一个成员:" << lst2.back() << endl;
	cout << "\tlst3" << endl;
	list<int> lst3(3, 666);//3个666
	PrintList(lst3, 1);
	list<int> lst4(lst2);//拷贝构造
}
int main()
{
	test();
	system("pause");
}

3.list容器赋值与互换成员

list容器赋值:
	重载运算符=: list& operator=(const list &p);
	siggn(int num,elem);//num个elem
	siggn(begin,end);//区间赋值
互换:
	swap(list &p);
  •  使用示例:

#include <iostream>
using namespace std;
#include <list>
void PrintList(const list<int>& p)
{
	for (list<int>::const_iterator ptr = p.begin(); ptr != p.end(); ptr++)
	{
		cout << *ptr << " ";
	}
	cout << endl;
}
void test()
{
	list<int> lst;
	for (int i = 10; i <= 30; i += 10)
	{
		lst.push_back(i);
	}
	list<int> lst2 = lst;//直接赋值
	cout << "lst2:" << endl;
	PrintList(lst2);
	list<int> lst3;
	lst3.assign(5, 666);
	cout << "lst3:" << endl;
	PrintList(lst3);
	list<int> lst4;
	lst4.assign(lst3.begin(), lst3.end());//区间赋值
	cout << "lst4:" << endl;
	PrintList(lst4);
	
	//互换元素
	lst4.swap(lst);
	cout << "lst4:" << endl;
	PrintList(lst4);
	cout << "lst:" << endl;
	PrintList(lst);
}
int main()
{
	test();
	system("pause");
}

4.list容器设置和获取大小

   list容器也有获取元素个数函数size()和设置元素个数函数resize(),但list容器不存在获取容量capacity()。
   检查容器是否为空可以使用empty()函数。

list容器元素个数:size()
指定元素个数:resize(int num);
			 resize(int num,elem); 指定大小,超出用elem补齐
判断容器是否为空:empty()
  •  使用示例:

#include <iostream>
using namespace std;
#include <list>
void PrintList(const list<string>& p)
{
	for (list<string>::const_iterator ptr = p.begin(); ptr != p.end(); ptr++)
	{
		cout << *ptr << " ";
	}
	cout << endl;
}
void test()
{
	list<string> lst;
	//插入数据
	lst.push_back("C++");
	lst.push_back("list容器");
	lst.push_back("学习");
	lst.push_back("示例");
	PrintList(lst);
	cout << "list成员个数:" << lst.size() << endl;
	lst.resize(10, "c++");//指定大小
	PrintList(lst);
	cout << "list成员个数:" << lst.size() << endl;
	lst.resize(2, "c++");//指定大小
	PrintList(lst);
	cout << "list成员个数:" << lst.size() << endl;

	list<string> lst2;
	if (lst2.empty())
	{
		cout << "lst2容器为空" << endl;
	}

}
int main()
{
	test();
	system("pause");
}

5.list容器插入与删除

   list容器中插入与删除相关函数如下所示:

list插入:
	push_back();尾插
	push_front();//头插入
	insert(iterator pos,elem);//在指定位置插入elem
	insert(iterator pos,n,elem);//在指定位置插入n个elem
	insert(iterator pos,begin,endl);在指定位置插入一个区间
list删除:
	pop_back();//尾删
	pop_front();//头删除
	erase(iterator pos);//删除指定位置的内容
	erase(begin,end);//删除区间内容
	clear();//删除所有内容
	remov(elem);删除容器中所有的elem

  •  使用示例:

#include <iostream>
using namespace std;
#include <list>
class Person
{
public:
	Person(string name, int age) :name(name), age(age) {

	}
	bool operator==(const Person &p);
	string name;
	int age;
};
ostream& operator<<(ostream& cout, Person p)
{
	cout << "姓名:" << p.name << "\t年龄:" << p.age ;
	return cout;
}
bool Person::operator==(const Person &p)
{
	if (this->age == p.age && this->name == p.name)return true;
	return false;
}
void PrintList(list<Person>& p)
{
	for (list<Person>::iterator ptr = p.begin(); ptr != p.end(); ptr++)
	{
		cout << *ptr << endl;
	}
}
void test()
{
	Person p1("小王",18);
	Person p2("小李", 18);
	Person p3("小刘", 18);
	Person p4("小林", 18);
	Person p5("小郭", 18);
	list<Person> lst;
	lst.push_back(p1);
	lst.push_back(p2);
	lst.push_back(p3);
	lst.push_back(p4);
	lst.push_back(p5);
	if (p1 == p1)
	{
		cout << "相等" << endl;
	}
	cout << "lst成员信息:" << endl;
	PrintList(lst);
	list<Person>::iterator ptr = lst.begin();
	ptr++;
	lst.insert(ptr, Person("it_阿水", 18));//从第一个位置插入数据
	cout << "insert插入成员信息:" << endl;
	PrintList(lst);

	list<Person> lst2;
	lst2.insert(lst2.begin(),lst.begin(), lst.end());//从头插入区间数据
	cout << "insert插入区间信息:" << endl;
	PrintList(lst2);
	ptr = lst2.begin();
	for (int i = 0; i < 3; i++)ptr++;
	lst2.insert(ptr, 3, p1);//指定位置插入3个成员
	cout << "insert插入多个成员信息:" << endl;
	PrintList(lst2);
	cout << "list2元素个数:" << lst2.size() << endl;
	lst2.erase(lst2.begin());//删除第一个位置的成员
	lst2.pop_back();//删除最后一个成员
	cout << "list2元素个数:" << lst2.size() << endl;
	PrintList(lst2);
	//lst2.remove(p1); 


	list<int>lst3;
	lst3.push_back(10);
	lst3.push_back(10);
	lst3.push_back(3);
	lst3.push_back(10);
	lst3.push_back(3);
	lst3.remove(10);//删除所有的10
	for (list<int>::iterator ptr = lst3.begin(); ptr != lst3.end(); ptr++)
	{
		cout << *ptr << " ";
	}
	cout << endl;
}
int main()
{
	test();
	system("pause");
}

6.list容器数据存取

由于list容器底层是通过双向循环链表来实现的,成员空间都是通过指针域保存的,所以不支持[]和at()访问成员。
 list容器的迭代器不支持随机访问。

list容器数据存取:
	back();//获取最后一个元素
	push_back();//从末尾插入
	front();//获取第一个元素
	push_front();从头插入
注意:由于list容器并不是一段连续的空间,所以不支持[]和at()访问成员
	  list容器的迭代器不支持随机访问,但是双向的
  •  使用示例:

#include <iostream>
using namespace std;
#include <list>
void test()
{ 
	list<int> lst;
	//插入数据
	lst.push_back(10);
	lst.push_front(20);
	lst.push_back(30);
	cout << "第一个元素:" << lst.front() << endl;
	cout << "最后一个元素:" << lst.back() << endl;
	list<int>::iterator ptr = lst.begin();
	ptr++;//支持往后
	ptr--;//支持往前
	//ptr += 3;错误,不支持随机访问

}
int main()
{
	test();
	system("pause");
}

7.list容器数据反转与排序

   list容器自带排序函数sort(),默认是升序排序。

list容器反转:
	reverse();//反转(逆序)
list容器排序
	sort();//成员函数
注意:所有不支持迭代器随机访问的容器都不能使用全局函数sort进行排序,一般该容器会自带排序的成员函数

  •  使用示例:
#include <iostream>
using namespace std;
#include <list>
void PrintList(list<int>& p)
{
	for (list<int>::iterator ptr = p.begin(); ptr != p.end(); ptr++)
	{
		cout << *ptr << " ";
	}
	cout << endl;
}
bool mycompare(int v1, int v2)
{
	return v1 > v2;
}
void test()
{
	list<int> lst;
	lst.push_back(10);
	lst.push_back(30);
	lst.push_back(20);
	lst.push_front(40);
	lst.push_front(60);
	lst.push_front(50);
	PrintList(lst);
	//反转
	lst.reverse();
	cout << "lst反转后" << endl;
	PrintList(lst);
	//排序
	lst.sort();//默认是升序
	cout << "从小到大排序:" << endl;
	PrintList(lst);
	//降序排序
	lst.sort(mycompare);
	cout << "从大到小排序:" << endl;
	PrintList(lst);
}
int main()
{
	test();
	system("pause");
}

8.list容器自定义数据类型排序案例

   Person数据保存每个用户的姓名、年龄、身高,现在需要对年龄按升序排序,若年龄相同,则对按身高进行降序排序。

#include <iostream>
using namespace std;
#include <list>
class Person
{
public:
	Person(string name, int age, int height) :name(name), age(age), height(height) {
	}
	string name;//姓名
	int  age;//年龄
	int height;//身高
};
ostream& operator<<(ostream& cout, Person p)
{
	cout << "姓名:" << p.name << "\t年龄:" << p.age << "\t身高:" << p.height;
	return cout;
}
void PrintList(list<Person>& p)
{
	for (list<Person>::iterator ptr = p.begin(); ptr != p.end(); ptr++)
	{
		cout << *ptr << endl;
	}
}
/*
按照年龄升序排序,年龄相同时按升高降序排序
*/
bool PersonCompare(Person& p1, Person& p2)
{
	if (p1.age == p2.age)
	{
		return p1.height > p2.height;
	}
	return p1.age < p2.age;
}
void test()
{
	list<Person> lst;
	lst.push_back(Person("小王", 18, 170));
	lst.push_back(Person("小刘", 18, 175));
	lst.push_back(Person("小李", 23, 168));
	lst.push_back(Person("小林", 20, 171));
	lst.push_back(Person("小蒋", 18, 172));
	lst.push_back(Person("小姜", 17, 176));
	PrintList(lst);
	cout << "排序后:" << endl;
	lst.sort(PersonCompare);
	PrintList(lst);

}
int main()
{
	test();
	system("pause");
}