STL为我们提供的链表是一个双向循环链表(下图中并没有体现出来循环)。由于链表只支持顺序访问，因此list容器的迭代器只支持双向访问，属于双向跌迭代器。
链表
链表采用动态分配空间，不会造成内存的浪费和溢出；同时插入和删除也十分方便，不需要移动大量元素，修改指针即可。 相比vector容器，list容器的插入和删除都不会使得原有的迭代器失效。但在vector容器下，如果数据插满了，需要去开辟新的空间，导致原来迭代器失效。
构造函数
函数原型
list<T> lst; //采用类模板的方式实现默认构造的形式 list<T>(begin,end); //利用构造函数将[begin,end)区间中的元素拷贝给本身 list<T>(n,elem); //构造函数将n个elem拷贝给本身 list<T>(const list &lit) //拷贝构造函数
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(1);
l1.push_back(3);
l1.push_back(2);
l1.push_back(4);
l1.push_back(5);
printList(l1); //1 3 2 4 5
//将[l1.begin(),l1.end())元素拷贝给自己
list<int>l2(l1.begin(), l1.end());
printList(l2); // 1 3 2 4 5
//拷贝构造
list<int> l3(l2);
printList(l3); //1 3 2 4 5
//10个100
list<int> l4(10, 100);
printList(l4); //100 100 100 100 100 100 100 100 100 100
}
list容器迭代器不可以跳跃式访问，但是可以进行“--”和“++”操作 。
赋值和交换
函数原型
assign(begin,end); //将[beg,end)区间上的数据拷贝给自己 assign(n,elem); //将n个elem拷贝给自己 list& operator=(const list &lst) //重载等号运算符 swap(lst) //将lst与本身的元素互换
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(1);
l1.push_back(3);
l1.push_back(2);
l1.push_back(4);
l1.push_back(5);
printList(l1); //1 3 2 4 5
//赋值 =
list<int> l2;
l2 = l1;
printList(l2);// 1 3 2 4 5
//assign,[l2.begin(),l2.end())区间的数据拷贝给自己
list<int> l3;
l3.assign(l2.begin(), l2.end());
printList(l3); // 1 3 2 4 5
//assign 5个100
list<int> l4;
l4.assign(5, 100);
printList(l4); // 100 100 100 100 100
}
//交换
void test02()
{
list<int> l1;
l1.push_back(1);
l1.push_back(3);
l1.push_back(2);
l1.push_back(4);
l1.push_back(5);
list<int> l2(10, 100);
cout << "交换前：" << endl;
printList(l1); //1 3 2 4 5
printList(l2); // 100 100 100 100 100 100 100 100 100 100
l1.swap(l2);
cout << "交换后：" << endl;
printList(l1); // 100 100 100 100 100 100 100 100 100 100
printList(l2); //1 3 2 4 5
}
大小操作
函数院原型
size(); //返回容器中元素的个数 empty(); //判断容器是否为空 resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置，如果容器短，则末尾多出的部分被删除 resize(num,elme); //如果指定容器的长度为num，若容器变长，则以elem填充新的位置。若容器变短，则末尾超出容器长度被删除
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(1);
l1.push_back(3);
l1.push_back(2);
l1.push_back(4);
l1.push_back(5);
if (l1.empty())
{
cout << "l1为空！" << endl;
}
else
{
cout << "l1不为空" << endl;
cout << "l1的大小为" << l1.size() << endl;
printList(l1); //1 3 2 4 5
}
//重新指定大小
l1.resize(10);
cout << "大小设置为10，多出来的位置用0填充" << endl;
printList(l1); // 1 3 2 4 5 0 0 0 0 0
l1.resize(3);
cout << "大小设置为3，多出来的数据删除" << endl;
printList(l1); // 1 3 2
l1.resize(10, 100);
cout << "大小设置为10，多出来的位置用100填充" << endl;
printList(l1); //1 3 2
}
插入和删除
函数原型
push_back(elem) //尾插一个元素 pop_back(); //尾删一个元素 push_front(); //从容器开头插入一个元素 pop_fron(); //从容器开头删除第一个元素 insert(pos.elem); //在pos位置插入elem的拷贝，返回新数据的位置 insert(pos, n,elem);//在pos处插入elem元素的拷贝，无返回值 insert(pos,begin,end);//在pos位置插入[begin,end)区间的数据，无返回值 clear(); //移出容器的所有数据 erase(begin,end); //删除[begin,end)区间的数据，无返回值。 erase(pos); //删除pos位置的数据，返回下一个数据的位置。 remove(elem); //删除容器中所有与elem值匹配的元素
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(1);
l1.push_front(2);
l1.push_front(3);
printList(l1); // 3 2 1 10 20 30
//尾删
l1.pop_back();
printList(l1); //3 2 1 10 20
//头删
l1.pop_front();
printList(l1); // 2 1 10 20
//insert插入
l1.insert(l1.begin(), 1000); //在l1的初始位置上插入1000
printList(l1);//1000 2 1 10 20
//在l1的第二个位置上插入3个10
l1.insert(++l1.begin(), 3, 10);
printList(l1); //1000 10 10 10 2 1 10 20
//删除起始位置的元素
l1.erase(l1.begin());
printList(l1); //10 10 10 2 1 10 20
//删除容器内所有的10
l1.remove(10);
printList(l1); //2 1 20
//清空
l1.clear();
cout << "大小为" << l1.size() << endl; //0
}
list比之前说过的容器多了个remove函数。和其他的成员函数不同，它的参数不是一个迭代器，而是一个元素值，可以把容器内部所有的这个值都删除。
数据存取
函数原型
front(); //返回第一个元素 back(); //返回最后一个元素
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);
printList(l1); // 10 20 30
cout << "第一个元素为：" << l1.front() << endl;
cout << "最后一个元素为：" << l1.back() << endl;
}
这里也和之前说过的容器不同，list容器没有了[]和at()操作，这也很好理解，因为它的内部是一个非连续的链表结构，链表是不支持随机访问的。
反转和排序
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(23);
l1.push_back(30);
l1.push_back(13);
l1.push_back(6);
cout << "反转前：" << endl;
printList(l1); //10 23 30 13 6
l1.reverse();
cout << "反转后：" << endl;
printList(l1);//6 13 30 23 10
}
bool compare(int v1, int v2)
{
return v1 > v2;
}
//排序
void test02()
{
list<int> l1;
l1.push_back(10);
l1.push_back(23);
l1.push_back(30);
l1.push_back(13);
l1.push_back(6);
cout << "排序前：" << endl;
printList(l1); //10 23 30 13 6
l1.sort(); //默认升序排列
cout << "排序后：" << endl;
printList(l1);//6 10 13 23 30
//降序，需要一个函数，改变sort函数的排序策略为降序
l1.sort(compare);
cout << "降序排序后：" << endl;
printList(l1);//30 23 13 10 6
}
这里主要说一下test02排序算法。我们并没有使用<algorithm>下的标准排序算法，因为list容器不支持随机访问迭代器，只有支持随机访问迭代器的容器才可以使用标准排序算法。但是，这些不支持随机访问迭代器的容器内部会为我们提供必要的算法。本例中list容器的排序实使用的sort算法就是一个成员函数。与标准算法一样，它默认也是升序排列，如果想要实现降序排序，就需要一个函数或者仿函数。
排序按例
案例描述:将Person自定义数据类型进行排序，属性有姓名、年龄、身高。按年龄进行升序，如果年龄相同，按身高进行降序。
class Person
{
public:
Person(string name, int age, int height)
{
this->age = age;
this->height = height;
this->name = name;
}
string name; //姓名
int age; //年龄
int height; //身高
};
void printList(const list<Person> &lp)
{
for (list<Person>::const_iterator it = lp.begin(); it != lp.end(); it++)
{
cout << "姓名：" << it->name << " 年龄：" << it->age << " 身高：" << it->height << endl;
}
}
//排序规则
bool compare(Person &p1, Person &p2)
{
if (p1.age == p2.age)
{
//年龄相同，按身高降序
return p1.height > p2.height;
}
else
{
//年龄不相同 按身年龄升序
return p1.age < p2.age;
}
}
void test01()
{
list<Person> l1;
l1.push_back(Person("刘备", 30, 170));
l1.push_back(Person("关羽", 20, 190));
l1.push_back(Person("张飞", 20, 180));
l1.push_back(Person("赵云", 18, 180));
l1.push_back(Person("马超", 18, 160));
l1.push_back(Person("黄忠", 40, 170));
l1.push_back(Person("魏延", 20, 170));
//排序前
cout << "排序前：" << endl;
printList(l1);
l1.sort(compare);
cout << "排序后：" << endl;
printList(l1);
}
本案例的核心在于compare()函数。由于使list容器里面放的是自定义数据类型，所以必须要有一个函数来制定排序规则，否则无法排序。
