【C++标准模版库】list的介绍及使用

list

一.list的介绍

  C++中的list标准模板库（STL）是C++标准库中的一个重要组成部分，它提供了一种双向链表的数据结构实现。list是C++ STL中的一个序列容器，它允许在常数时间内进行任意位置的插入和删除操作。与vector不同，list是一个双向链表，其元素不是连续存储的，而是存储在互不相关的独立节点中，每个节点都包含数据部分和两个指针（分别指向前一个节点和后一个节点）。

list关键特性：

1. 双向链表：list的底层实现是双向链表，支持高效的插入和删除操作，尤其是在链表的头部和尾部。
2. 不支持随机访问：与vector和deque（双向队列）等容器不同，list不支持通过索引直接访问元素，访问特定位置的元素需要从已知位置（如头部或尾部）开始迭代。
3. 迭代器：list提供了双向迭代器，允许从前往后或从后往前遍历链表。
4. 内存分配：由于list的元素不是连续存储的，因此它不需要在插入或删除元素时重新分配大块内存，这减少了内存碎片和重新分配的开销。

二.list的使用

  学习list时查看文档是非常重要的（list的文档介绍），list在实际中非常的重要，在实际中我们熟悉常见的接口就可以，下面列出了哪些接口是要重点掌握的。

1.list 构造函数

(construct)构造函数声明接口说明list()（重点）无参构造list（size_type n, const value_type& val =value_type()）构造并初始化n个val，无val默认为T()，例如整形为0list (const list& x)（重点）拷贝构造list (InputIterator first, InputIterator last)使用迭代器区间进行初始化构造
注意：list使用模板，template < class T > ，其中将T重定义为value_type。

intmain(){
    list<int> l1;//无参构造
    list<int>l2(10,1);//10个1有参构造
    list<int>l3(l2.begin(), l2.end());//迭代器区间构造
    list<int>l4(l2);//拷贝构造//list<int> l3(l2.begin() + 3, l2.end() - 2); error
    list<int>l5(++l2.begin(),--l2.end());//注意：list迭代器区间构造不支持+，-操作，但是支持++，--//1.迭代器循环遍历
    list<int>::iterator it = l4.begin();while(it != l4.end()){
        cout <<*it <<" ";++it;}
    cout << endl;//2.auto+范围for变量for(auto e : l4){
        cout << e <<" ";}
    cout << endl;return0;}

2.list 空间大小

函数声明接口说明size返回list中有效节点的个数empty检测list是否为空，是返回true，否则返回false

intmain(){
    list<int> l1;
    cout << l1.size()<< endl;//0
    cout << l1.empty()<< endl;//1return0;}

3.list 增删查改

函数声明接口声明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素assign赋值：支持个数赋值、迭代器赋值（不常用）insert在list position 位置中插入值为val的元素（只支持迭代器）erase删除list position位置的元素（只支持迭代器）swap交换两个list中的元素resize改变list的有效元素的个数clear清空list中的有效元素emplace_front在某些情况下比push_front效率高emplace_back在某些情况下比push_back效率高

intmain(){
    list<int>l1(10,1);//初始化为10个1
    l1.front()=100;//返回引用——>修改头为100
    l1.back()=100;//返回引用——>修改尾为100

    l1.push_front(10);//头插
    l1.pop_front();//头删
    l1.push_back(10);//尾插
    l1.pop_back();//尾删

    list<int> l2;
    l2.assign(5,1);//赋值为5个1
    l2.assign(l1.begin(), l1.end());//迭代器赋值

    list<int> l3;
    l3.push_back(1);
    l3.push_back(2);
    l3.push_back(3);
    l3.push_back(4);//要求在第3个位置插入10：实际是第四个位置变成10//错误写法：l3.insert(l3.begin() + 3, 10); //双向迭代器：支持++/--、不支持随机访问+/-//正确写法如下：auto it = l3.begin();int k =3;while(k--){++it;}
    l3.insert(it,10);//插入一个10for(auto e : l3){
        cout << e <<" ";//1 2 3 10 4}
    cout << endl;

    l3.insert(it,5,1);//插入5个1for(auto e : l3){
        cout << e <<" ";//1 2 3 10 4}
    cout << endl;

    l3.insert(it, l1.begin(), l1.end());//插入5个1for(auto e : l3){
        cout << e <<" ";//1 2 3 10 4}
    cout << endl;int x =0;
    cin >> x;
    it =find(l3.begin(), l3.end(), x);//先找x所在的迭代器if(it != l3.end())//找不到x的表面：it == l3.end(){
        l3.erase(it);//按照迭代器删除x}

    l3.swap(l1);//l3与l1交换
    l3.clear();//清空l3中的有效数据
    l3.resize(10,1);//修改有效数据的个数：10个数据全为1
    l3.resize(20);//前10个数据全为1，后10个数据默认为0return0;}

structA{public:A(int a1 =1,int a2 =1):_a1(a1),_a2(a2){
        cout <<"A(int a1 = 1, int a2 = 1)"<< endl;}A(const A& a){
        cout <<"A(const A& a)"<< endl;}int _a1;int _a2;};intmain(){//对于内置类型无区别
    list<int> l1;
    l1.push_back(1);
    l1.emplace_back(2);

    list<A> l2;
    A aa1(1,1);
    l2.push_back(aa1);//尾插有名对象
    l2.push_back(A(2,2));//尾插匿名对象//l2.push_back(3, 3);  //不支持

    A aa2(1,1);//有参构造
    l2.emplace_back(aa2);//拷贝构造
    l2.emplace_back(A(2,2));//有参构造+拷贝构造//emplace_back()支持直接传构造A对象的参数，而push_back()不支持
    l2.emplace_back(3,3);//直接有参构造更高效return0;}

4.list 迭代器的使用

函数声明接口说明begin + end（重点）获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iteratorrbegin + rend获取最后一个数据位置的reverse_iterator/const_reverse_iterator，获取第一个数据前一个位置的reverse_iterator/const_reverse_iterator
迭代器划分为两类：

按照功能：

1. 正向迭代器：iterator
2. 反向迭代器：reverse_iterator
3. const修饰正向迭代器：const_iterator
4. const修饰反向迭代器：const_reverse_iterator

按照性质：

1. 单向：forward_list/unordered_map… 支持：++
2. 双向：list/map/set… 支持：++/–
3. 随机：vector/string/deque… 支持：++/–/+/-

+：正向、支持随机访问（例如：支持begin()++、begin() + 3）
-：反向、支持随机访问（例如：支持begin()- -、begin() - 3）
++：正向、不支持随机访问（例如：支持begin()++、不支持begin() + 3）
–：反向、不支持随机访问（例如：支持begin()- -、不支持begin() - 3）

双向包含单向，同理随机包含双向。

intmain(){
    list<int>l1(10,1);//list不支持算法库中的sort，要求随机迭代器//sort(l1.begin(), l1.end());//vector、string支持sort
    string s1("156874239");sort(s1.begin(), s1.end());
    cout << s1 << endl;//123456789return0;}

1.正向迭代器

intmain(){//普通正向迭代器
    list<int>l1(10,1);
    list<int>::iterator it = l1.begin();while(it != l1.end()){//(*it)++; 可以修改
        cout <<*it <<" ";++it;}
    cout << endl;//const修饰正向迭代器const list<int>l2(10,1);
    list<int>::const_iterator cit = l2.begin();while(cit != l2.end()){//(*cit)++; 不可以修改
        cout <<*cit <<" ";++cit;}
    cout << endl;return0;}

2.反向迭代器

intmain(){//普通反向迭代器
    list<int>l1(10,1);
    list<int>::reverse_iterator rit = l1.rbegin();while(rit != l1.rend()){//(*rit)++; 可以修改
        cout <<*rit <<" ";++rit;}
    cout << endl;//const修饰反向迭代器const list<int>l2(10,1);
    list<int>::const_reverse_iterator crit = l2.rbegin();while(crit != l2.rend()){//(*crit)++; 不可以修改
        cout <<*crit <<" ";++crit;}
    cout << endl;return0;}

5.list 其他成员函数

函数声明接口声明reverse逆置设计的些许冗余，可以使用算法库中的reversesort排序：默认得到升序的list，降序需要使用仿函数merge合并两个有序的list，默认传入升序的list，得到升序的list，降序需要使用仿函数unique将有序的list去除重复的数据remove移除给定值的数据splice剪切+粘贴（具体看如下代码）

intmain(){
    list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);//list的成员函数reverse设计的有些冗余
    l1.reverse();//算法库的reversereverse(l1.begin(), l1.end());

    l1.sort();//排序：默认升序，低层是归并//算法库的函数sort要支持随机访问，无法被list使用，低层是快排//降序——>仿函数
    less<int> ls;//小于号：升序
    greater<int> gt;//大于号：降序

    l1.sort(ls);

    l1.sort(greater<int>());//匿名对象

    list<int> first;
    first.push_back(1);
    first.push_back(3);
    first.push_back(5);

    list<int> second;
    second.push_back(2);
    second.push_back(4);
    second.push_back(6);//合并两个升序list，得到升序的list，此时second为空//也支持合并两个降序list，得到降序的list——>与sort一样使用仿函数
    first.merge(second); 
    cout << first.size()<< endl;//6
    cout << second.size()<< endl;//0

    list<int> l2;
    l2.push_back(1);
    l2.push_back(3);
    l2.push_back(2);
    l2.push_back(2);
    l2.push_back(5);
    l2.push_back(5);
    l2.sort();//先排序再去重
    l2.unique();//有序list去重
    l2.remove(3);//移除3return0;}

intmain(){
    list<int> mylist1, mylist2;for(int i =1; i <=4;++i){ 
        mylist1.push_back(i);//mylist1: 1 2 3 4}for(int i =1; i <=3;++i){
        mylist2.push_back(i *10);//mylist2: 10 20 30}

    list<int>::iterator it;
    it = mylist1.begin();++it;//一个链表的节点转移给另一个链表
    mylist1.splice(it, mylist2);//mylist1：1 10 20 30 2 3 4//mylist2：empty

    list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);
    l1.push_back(5);
    l1.push_back(6);int x;
    cin >> x;
    it =find(l1.begin(), l1.end(), x);if(it != l1.end()){//l1.splice(l1.begin(), l1, it); //将it位置的数据剪切粘贴到l1的头部//将迭代器区间it~l1.end()剪切粘贴到l1的头部
        l1.splice(l1.begin(), l1, it, l1.end());}return0;}

三.vector与list关于sort性能的比较

注意：凡是测试性能Debug下不具有参考价值，要在release下测试性能。

intmain(){srand(time(0));constint N =1000000;

    list<int> l1;
    vector<int> v1;for(int i =0; i < N;++i){auto e =rand()+ i;//减少重复的数值
        l1.push_back(e);
        v1.push_back(e);}int begin1 =clock();sort(v1.begin(), v1.end());//算法库：sort（快排）排序vectorint end1 =clock();int begin2 =clock();
    l1.sort();//无法使用算法库的sort，使用类成员函数sort（归并）排序int end2 =clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);return0;}

思考：可以发现算法库中的sotr性能更高，list中成员函数sort性能不太高，因此如果将list中的数据拷贝到vector中进行sort，再将vector赋值到list时性能还会更高？代码如下：

intmain(){srand(time(0));constint N =1000000;

    list<int> lt1;
    list<int> lt2;for(int i =0; i < N;++i){auto e =rand()+ i;
        lt1.push_back(e);
        lt2.push_back(e);}int begin1 =clock();//拷贝vector
    vector<int>v(lt2.begin(), lt2.end());//排序sort(v.begin(), v.end());//拷贝回lt2
    lt2.assign(v.begin(), v.end());int end1 =clock();int begin2 =clock();
    lt1.sort();int end2 =clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);}

事实证明：拷贝数据不会花太多时间，以及list排序性能不太行，甚至不如拷贝到vector中进行排序。