list容器基本概念

功能：将数据进行链式储存
链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
链表的组成：

• 链表由一系列结点组成

结点的组成：

• 储存数据元素的数据域
• 储存下一个节点地址的指针域

STL中链表是一个双向循环列表

list的优点：

• 采用动态存储分配，不会造成内存浪费或溢出
• 可以对任意位置进行快速插入或删除元素

缺点：

• 遍历速度较数组慢
• 占用空间比数组大

list的重要性质：

• 插入和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的

STL中list和vector是最常被使用的容器，各有优缺点

list构造函数

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

#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
    for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
int main()
{
    list<int>L1;//默认构造
    for (int i = 0; i < 10; i++)
    {
        L1.push_back(i);
    }
    PrintList(L1);
    list<int>L2(L1.begin(), L1.end());//区间方式构造
    PrintList(L2);
    list<int>L3(L2);//拷贝构造
    PrintList(L3);
    list<int>L4(10, 2);//n个elem
    PrintList(L4);
    return 0;
}

list赋值和交换

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

#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
    for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
int main()
{
    list<int>L1;//默认构造
    for (int i = 0; i < 10; i++)
    {
        L1.push_back(i);
    }
    list<int>L2;
    L2.assign(L1.begin(), L1.end());//区间赋值
    PrintList(L2);
    L2.assign(10, 1);//n个elem赋值
    PrintList(L2);
    L2 = L1;//等号赋值
    PrintList(L2);
    return 0;
}

list容器大小操作

• .empty();//判断容器是否为空
• .size();//返回容器中元素的个数
• .resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值0填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
• .resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置；如果容器变短，则末尾超出容器长度的元素被删除
  

list插入和删除

两端插入操作：

• .push_back(elem);//尾插
• .push_front(elem);//头插
• .pop_back();//尾删
• .pop_front();//头删

指定位置操作：

• .insert(pos, elem);//在pos位置插入elem元素的拷贝，返回新数据的位置
• .insert(pos, n, elem);//在pos位置插入n个elem元素数据，无返回值
• .insert(pos, beg, end);//在pos位置插入[beg,end)区间的数据，无返回值
• .clear();//清空容器内所有数据
• .eraser(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置
• .erase(pos);//删除pos位置的数据，返回下一个数据的位置

以上操作与deque容器相同，不同的是，list支持remove操作：

• .remove(elem);//删除容器中所有与elem值匹配的元素

#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
    for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
int main()
{
    list<int>L1(10, 1);
    PrintList(L1);
    L1.remove(1);
    PrintList(L1);
    return 0;
}

list数据存取

只支持存取首位：

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

list本质是链表，不是用连续性空间存储数据

• 不能直接利用中括号和at的方式进行访问，而且它的迭代器不支持随机访问，只能前移和后移

//验证迭代器是不支持随机访问的
list<int>L1(10, 1);
list<int>::iterator it = L1.begin();
it++;//可以运行
//it += 1;//会报错

如何验证容器支持的迭代器：

• it++;//支持向前
• it--;//双向迭代器
• it += 1;//支持随机访问
  

list反转和排序

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

不能使用sort(L1.begin(), L1.end());

• 所有不支持随机访问迭代器的容器，不可以用标准算法
• 不支持随机访问迭代器的容器，内部会提供一些对应的算法

sort默认升序排列，如果要降序，要写仿函数，sort参数为函数名

#include <iostream>
#include<list>
using namespace std;
void PrintList(const list<int>& lst)
{
    for (list<int>::const_iterator it = lst.begin(); it != lst.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
bool myCompare(int v1,int v2)
{
    //降序，就让第一个数大于第二个数
    return v1 > v2;
}
int main()
{
    //验证迭代器是不支持随机访问的
    list<int>L1;
    for (int i = 0; i < 10; i++)
    {
        L1.push_back(i);
    }
    PrintList(L1);
    L1.reverse();
    PrintList(L1);
    L1.sort();//默认从小到大
    PrintList(L1);
    L1.sort(myCompare);
    PrintList(L1);
    return 0;
}

自定义数据类型排序

以Person为例，有姓名、年龄、身高等属性
排序规则：按照年龄进行升序，如果年龄相同，按照身高进行降序
高级排序方法：

• 制定排序规则，年龄相同和不同时分别如何排序
• 注意返回值表达式中的>和<，分别为降序和升序

#include <iostream>
#include<list>
#include<string>
using namespace std;
class Person
{
public:
    Person(string name, int age, int height)
    {
        this->m_name = name;
        this->m_age = age;
        this->m_height = height;
    }
    string m_name;
    int m_age;
    int m_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;
}
int main()
{
    list<Person>l;
    //准备数据
    Person p1("A", 10, 100);
    Person p2("B", 17, 90);
    Person p3("C", 15, 190);
    Person p4("D", 15, 150);
    Person p5("E", 15, 90);
    //插入数据
    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;
    }
    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;
    }
    return 0;
}