#挑战30天在头条写日记#

1.list容器 链表 基本概念

功能：将数据进行链式存储

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

链表的组成：链表是由一系列节点组成

节点的组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域

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

由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于 双向迭代器

list的优点：

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

list的缺点：

• list链表遍历速度不快，同时占用空间大

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

2.list构造函数

/*
    函数原型
        list<t>   list采用模板实现默认构造
        list(beg,end)  构造函数将[beg,end]区间的元素拷贝给本身
        list(n,elem)   构造函数将n个elem拷贝给本身
        list(const list &lst) 拷贝构造函数
*/
void printList(const list<int>& L) {
    for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) {
        cout << *it << endl;
    }
}
void test01() {
    //创建list容器
    list<int> L1;//默认构造

    //添加数据
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    //遍历list
    printList(L1);

    //区间方式构造
    list<int>L2(L1.begin(), L1.end());
    printList(L2);

    //拷贝构造
    list<int> L3(L2);
    printList(L2);
}
int main() {
    test01();
    system("pause");
    return 0;
}

3.list赋值和交换

功能描述：给list容器进行赋值以及交换list容器

/*
    函数原型
        assign(beg,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容器
    list<int> L1;

    //添加数据
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    //遍历list
    //printList(L1);

    //赋值操作
    list<int>L2;
    L2 = L1;//以等号的方式赋值
    //printList(L2);

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

    list<int> L4;
    L4.assign(2, 5);//assign(n,elem)
    printList(L4);

    //交换
    L4.swap(L3);
    printList(L4);
    printList(L3);
}
int main() {
    test01();
    system("pause");
    return 0;
}

4.list容器大小操作和元素数判断

功能描述：

对list容器的大小进行操作

/*
    函数原型
        size();  返回容器中元素的个数
        empty(); 判断容器是否为空
        resize(num) 重新指定容器的长度为num 若容器变长，则以默认值（一般为0）填充新位置
                    如果容器变短，则末尾超出容器长度的元素被删除
        resize(num，elem) 重新指定容器的长度为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容器
    list<int> L1;

    //添加数据
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    //遍历list
    printList(L1);

    //判断容器是否为空
    if (L1.empty()) {
        cout <<" L1为空 " << endl;
    }else {
        cout <<" L1不为空 " << endl;
        cout <<" L1的元素个数为： "<<L1.size() << endl;
    }

    //重新指定大小
    L1.resize(10);
    printList(L1);//输出：10 20 30 40 0 0 0 0 0 0

    L1.resize(2);
    printList(L1);//输出：10 20
}
int main() {
    test01();
    system("pause");
    return 0;
}

5.list插入和删除

功能描述：对list容器进行数据的插入和删除

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

*/
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容器
    list<int> L1;

    //尾插
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    //头插
    L1.push_front(100);
    L1.push_front(200);
    L1.push_front(300);
    L1.push_front(400);
    //遍历list
    printList(L1);//输出；400 300 200 100 10 20 30 40

    //尾删
    L1.pop_back();
    printList(L1);//输出；400 300 200 100 10 20 30
        

    //头删
    L1.pop_front();
    printList(L1);//输出；300 200 100 10 20 30

    //insert插入
    L1.insert(L1.begin(), 1000);
    printList(L1);//输出；1000 300 200 100 10 20 30

    //可以使用迭代器偏移
    list<int>::iterator it = L1.begin();
    L1.insert(++it, 5000);
    printList(L1);//输出；1000 5000 300 200 100 10 20 30

    //删除
    L1.erase(L1.end());
    printList(L1);//输出；5000 300 200 100 10 20 30

    L1.remove(10);
    printList(L1);//输出；5000 300 200 100 20 30

}
int main() {
    test01();
    system("pause");
    return 0;
}

6.list数据存取

功能描述：

对list容器中数据进行存取

/*
    函数原型
    front()  返回第一个元素
    back()  返回最后一个元素
*/

void test01() {

    //创建list容器
    list<int> L1;

    //尾插
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);

    //L1[0]  不可以使用[]方式访问list容器中的元素
    //L1.at(0)  不可以使用at方式访问list容器中的元素
    //原因是list本质是链表，不是用连续性空间存储数据，迭代器也是不支持随机访问

    cout << "第一个元素为： " << L1.front() << endl;
    cout << "最后一个元素为： " << L1.back() << endl;

    //验证迭代器是不支持随机访问的
    list<int>::iterator it = L1.begin();
    it++;//支持双向
    it--;
    //it = it + 2;  报错  是不支持随机访问的
}
int main() {
    test01();
    system("pause");
    return 0;
}

7.list反转和排序

功能描述：

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

/*
    函数原型
    reverse()  反转链表
    sort()  链表排序
*/
//打印函数
void printList(list<int>& L) {
    for (list<int>::iterator it = L.begin(); it != L.end(); it++) {
        cout<<*it<<" ";
    }
    cout << endl;
}
//降序排序  所需函数 
bool myCompare(int v1, int v2) {
    return v1 > v2;
}
void test01() {

    //创建list容器
    list<int> L1;

    //尾插
    L1.push_back(30);
    L1.push_back(20);
    L1.push_back(50);
    L1.push_back(40);

    //反转前
    printList(L1);

    //反转后
    L1.reverse();
    printList(L1);

    //排序
    //sort(L1.begin(), L1.end()); 报错
    //原因 所有不支持随机访问迭代器的容器，不可以使用标准算法
    
    //不支持随机访问迭代器的容器，内部会提供对应一些算法,同时排序还可以实现降序
    L1.sort();//此时是增序
    printList(L1);
    L1.sort(myCompare);//此时是实现降序
    printList(L1);
}
int main() {
    test01();
    system("pause");
    return 0;
}

8.list排序案例

案例描述：将Person自定义数据类型进行排序，Person中属性有姓名，年龄，身高

排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序

//list 容器 排列案例  对于自定义数据类型做排序
//规则：按照年龄进行升序，如果年龄相同按照身高进行降序

class Person {
public:
    string m_Name;
    int m_Age;
    int m_Height;
    Person(string name, int age, int height) {
        this->m_Name = name;
        this->m_Age = age;
        this->m_Height = height;
    }
};

//排序规则函数
bool comparePerson(Person& p1, Person& p2) {
    //按照年龄 升序
    if (p1.m_Age == p2.m_Age) {
        //年龄相同 按照身高排序
        return p1.m_Height > p2.m_Height;
    }
    return p1.m_Age < p2.m_Age;
}

void test01() {

    //创建list容器
    list<Person> L1;

    //创建人物
    Person p1("刘备",35,175);
    Person p2("曹操", 45, 180);
    Person p3("孙权", 30, 178);
    Person p4("诸葛亮", 35, 185);
    Person p5("司马懿", 40, 170);
    Person p6("鲁肃", 35, 178);

    //尾插
    L1.push_back(p1);
    L1.push_back(p2);
    L1.push_back(p3);
    L1.push_back(p4);
    L1.push_back(p5);
    L1.push_back(p6);

    //排序前
    for (list<Person>::iterator it = L1.begin(); it != L1.end();it++) {
        cout << " 姓名：" << (*it).m_Name << " 年龄：" << it->m_Age << " 身高 " << (*it).m_Height << endl;
    }
    
    cout<<"-----------------------------" << endl;
    
    //自定义的数据排序，需要指定排序规则
    L1.sort(comparePerson);
    
    //排序后
    for (list<Person>::iterator it = L1.begin(); it != L1.end(); it++) {
        cout << " 姓名：" << (*it).m_Name << " 年龄：" << it->m_Age << " 身高 " << (*it).m_Height << endl;
    }
}

int main() {
    test01();
    system("pause");
    return 0;
}