C++ 106 之 list容器

#include <iostream>
#include <string>
using namespace std;
// #include <vector>   // 容器头文件
#include <algorithm> // 标准算法头文件
#include <list>

void printList(const list<int> & list1){
    for(list<int>::const_iterator it = list1.begin(); it != list1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}

class Student04{
public:
    string m_name;
    int m_age;
    int m_height;
    Student04(string name, int age, int height){
        this->m_name = name;
        this->m_age = age;
        this->m_height = height;
    }
    // const 不想让它被修改
    bool operator==(const Student04& stu) const{ // const修饰的函数，叫常函数


        // return this->m_age == stu.m_age && this->m_name == stu.m_name && this->m_height == stu.m_height; 
        return this->m_age == stu.m_age && this->m_name == stu.m_name && this->m_height == stu.m_height;


    }
};

bool com_age(Student04 &stu1, Student04 &stu2){
    // return stu1.m_age > stu2.m_age; // 降序排列
    // return stu1.m_age < stu2.m_age; // 升序排列

    // 若果年龄形同，按照身高升序排列
    if(stu1.m_age == stu2.m_age)
    {
        return stu1.m_height < stu2.m_height;
    }
    else{
        return stu1.m_age < stu2.m_age;
    }
}

int main()
{
    // 双向循环连表list

    list<int> list1;
    list1.push_back(1);
    list1.push_back(2);
    list1.push_back(3);

    list1.push_front(10);
    list1.push_front(20);
    list1.push_front(30);
    // 正序遍历
    // for(list<int>::iterator it = list1.begin(); it != list1.end(); it++)
    // {
    //     cout << *it << endl;
    // }

    // 倒序遍历
    // reverse_iterator 倒序迭代器
    // rbegin()   read()  右侧的开始和结束位置
    // for(list<int>::reverse_iterator it = list1.rbegin(); it != list1.rend(); it++)
    // {
    //     cout << *it << endl;
    // }

    // list迭代器  
    // list<int>::iterator it_begin = list1.begin();
    //it_begin++;
    // it_begin--;

    // list迭代器不支持随即访问的,下面语法报错，不允许
    // it_begin = it_begin + 3;

    // cout << *it_begin << endl;

    // printList(list1);
    // list1.pop_back();   // 尾删
    // list1.pop_front();  // 头删
    // printList(list1);

    // list1.insert(list1.begin(), 777);

    // list<int>::iterator it_begin = list1.begin();
    // advance(it_begin, 2);    // 向后移动2个位置
    // advance(it_begin, -1);      // 向前移动1个位置
    // list1.insert(it_begin, 777);
    // printList(list1);


    // // erase 根据迭代器位置进行删除
    // printList(list1);
    // // list1.erase(list1.begin());
    // list<int>::iterator it_begin = list1.begin();
    // advance(it_begin, 2);
    // advance(it_begin, -1);
    // list1.erase(it_begin);
    // printList(list1);

    // remove 删除容器中所有匹配的元素
    // list1.push_back(1);
    // list1.push_back(1);
    // list1.push_back(1);
    // printList(list1);
    // list1.remove(1);
    // printList(list1);

    // 交换
    // list<int> list2;
    // list2.assign(10, 666);
    // list1.swap(list2);
    // printList(list1);

    //反转
    // printList(list1);
    // list1.reverse();
    // printList(list1);

    // // 排序
    // printList(list1);
    // // list1.sort(); // 升序排列
    // // 想实现降序，需要先升序、再反转
    // list1.sort();
    // list1.reverse();
    // printList(list1);

    // 案例：
    Student04 stu1("赵云",62, 190);
    Student04 stu2("关羽",62, 210);
    Student04 stu3("张飞",62, 205);
    Student04 stu4("曹操",9, 179);

    list<Student04> list_stu;

    list_stu.push_back(stu1);
    list_stu.push_back(stu2);
    list_stu.push_back(stu3);
    list_stu.push_back(stu4);

    for(list<Student04>::iterator it = list_stu.begin(); it != list_stu.end(); it++){
        cout << "姓名: " << (*it).m_name << "  年龄：" << it->m_age << " 身高："<< it->m_height <<endl; 
    }

    cout << "-----------------------------" << endl;

    list_stu.sort(com_age); // 自定义类型在list中想要升序或降序排列，学要传回调函数



    for(list<Student04>::iterator it = list_stu.begin(); it != list_stu.end(); it++){
        cout << "姓名: " << (*it).m_name << "  年龄：" << it->m_age << " 身高："<< it->m_height <<endl; 
    }

    cout << "-----------------------------" << endl;

    list_stu.remove(stu3);
    for(list<Student04>::iterator it = list_stu.begin(); it != list_stu.end(); it++){
        cout << "姓名: " << (*it).m_name << "  年龄：" << it->m_age << " 身高："<< it->m_height <<endl; 
    }

    return 0;
}

list容器

3.6.1 list容器基本概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。

List和vector是两个最常被使用的容器。

List容器是一个双向循环链表。

采用动态存储分配，不会造成内存浪费和溢出

链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
链表灵活，但是空间和时间额外耗费较大

3.6.2 list容器的迭代器

List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。

由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators.

List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。