C++之list容器如何使用

2023-02-08 22:44:02 8 0
魁首哥

C++之list容器如何使用

今天小编给大家分享一下C++之list容器如何使用的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

    一、list底层结构

    list底层是带头节点的双向循环链表

    • 双向:可以从前往后,也可以从后往前遍历

    • 循环:找尾节点的时间复杂度为O( 1 )

    • 带头节点:代码实现简单,不用考虑链表为空等特殊情况,可令end()迭代器指向头节点的位置

    二、构造方法

    构造函数

    list<int> l1;list<int> l2(5, 3);//迭代器vector<int> v{ 1,2,3,4,5 };list<int> l3(v.begin(), v.end());//C++11list<int> l4{ 1,2,3,4,5 };

    拷贝构造函数

    利用l1拷贝构造l2

    list<int> l1{ 1,2,3,4,5 };list<int> l2(l1);

    三、元素访问和迭代器

    back&front

    list<int> l1{ 1,2,3,4,5 };cout << l1.front() << endl;cout << l1.back() << endl;

    三种遍历方式

    list<int> l1{ 1,2,3,4,5 };

    采用下面三种方式对下面这个list<int>类型的对象进行遍历打印:

    1.迭代器

    list<int>::iterator it = l1.begin();for (it; it != l1.end(); it++){cout << *it << " ";}cout << endl;

    打印结果:

    2.范围for

    注意这里e是int类型,不用再进行解引用

    //范围forfor (auto e : l1){cout << e << " ";}cout << endl;

    打印结果:

    3.反向迭代器

    list<int>::reverse_iterator rit = l1.rbegin();for (rit; rit != l1.rend(); rit++){cout << *rit << " ";}cout << endl;

    打印结果:

    四、元素修改

    尾插、头插、尾删、头删

    insert、erase

    list支持任意位置的插入,注意list对象的迭代器不支持加减数字,因为其底层空间不连续,如图:

    如果要往一个位置进行插入,可以通过find函数返回位置进行,find是一个通用的函数模板,返回值是传入参数的迭代器类型

    list<int> l1{ 1,2,3,4,5 };l1.insert(find(l1.begin(), l1.end(), 3), 10);//任意位置插入l1.erase(find(l1.begin(), l1.end(), 10), l1.end());//任意位置的删除

    swap

    list内置的交换函数

    list<int> l1{ 1,2,3,4,5 };list<int> l2{ 5,6,7,8,9 };l1.swap(l2);

    resize

    resize改变有效元素的个数,多的元素用第resize二个参数填充,如果没有给第二个参数,则默认用T()。

    list<int> l1{ 0,1,2 };l1.resize(5, 3);

    五、特殊操作

    remove

    删除值为value的元素

    list<int> l1{ 3,0,1,3,2,3 };l1.remove(3);

    remove_if

    remove_if的参数是一个判断条件,可以是函数指针或者函数对象

    //判断5的倍数bool MultipleFive(int n){return 0 == n % 5;}void Test10(){//此处传递函数指针list<int> l1{ 10,0,1,3,5,7,20 };l1.remove_if(MultipleFive);}

    unique、sort

    unique,去重,删除所有重复元素,使用unique之前要先调用sort进行排序,这里的sort是list内置的sort,不是标准库中的sort

    void Test(){list<int> l1{ 1,3,3,5,4,0,2,5,4 };l1.sort();//默认升序l1.unique();//删除重复元素}

    结果:

    对于sort的使用,还可以自定义函数,并将函数指针作为参数传递给sort函数进行排序:

    reverse

    对链表进行逆置

    void Test(){ list<int> l1{ 1,3,5,7,9 };l1.reverse();}

    结果:

    六、list迭代器失效问题

    list底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。 

    erase导致的迭代器失效

    如图所示,it迭代器所指向的位置被删除后,迭代器失效:

    改正方法:

    while (it != l1.end()){//it=l1.erase(it);l1.erase(it++);}

    这里 l1.erase(it++)语句也能达到效果,因为后置++会将自增后的结果保存在临时变量中,而前置则不可以。 

    resize导致的迭代器失效

    resize减少有效元素个数也会导致迭代器失效:

    list<int> l1{ 1,3,5,7,9 };auto it = l1.end();l1.resize(3);

    上面这个程序中,reseze减少有效元素个数后,it指向的位置元素已经被删除,迭代器失效,如果再使用该迭代器,则会出错。

    七、vector与list对比

    vector(动态顺序表)

    list(带头结点的双向循环链表)

    对比vectorlist
    底层结构动态顺序表&#xff0c;连续空间带头结点的双向循环链表
    访问支持随机访问&#xff0c;首地址+下标不能随机访问&#xff0c;可通过find查找&#xff0c;访问随即元素时间复杂度O(N)
    插入删除任意位置插入和删除效率低&#xff0c;需要搬移元素&#xff0c;时间复杂度为O(N)&#xff0c;插入时有可能需要增容&#xff0c;增容&#xff1a;开辟新空间&#xff0c;拷贝元素&#xff0c;释放旧空间&#xff0c;导致效率更低任意位置插入和删除效率高&#xff0c;不需要搬移元素&#xff0c;时间复杂度为O(1)
    空间利用率底层为连续空间&#xff0c;不容易造成内存碎片&#xff0c;空间利用率较高&#xff0c;缓存利用率高。可以一次将一个数据附近的空间都加载到缓存&#xff0c;不用频繁地从内存读取数据底层节点动态开辟&#xff0c;容易造成内存碎片&#xff0c;空间利用率低&#xff0c;缓存利用率低
    迭代器原生态指针对指针进行了封装
    迭代器失效容量相关的操作都有可能导致迭代器失效&#xff0c;如插入引起的扩容&#xff0c;删除元素等插入元素不会导致迭代器失效&#xff0c;删除节点会导致&#xff0c;且只影响当前迭代器&#xff0c;其他迭代器不受影响
    使用场景不关心插入和删除效率&#xff0c;支持随机访问大量插入和删除操作&#xff0c;不关心随机访问的场景

    以上就是“C++之list容器如何使用”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注恰卡编程网行业资讯频道。

    收藏
    分享
    海报
    0 条评论
    8
    上一篇:C++内存对齐如何实现 下一篇:vue3之Suspense加载异步数据怎么使用

    本站已关闭游客评论,请登录或者注册后再评论吧~

    忘记密码?

    图形验证码