【C++入门到精通】C++入门 —— list (STL)

阅读导航

前言

文章绑定了VS平台下std::list的源码，大家可以下载了解一下😍

前面我们讲了C语言的基础知识，也了解了一些数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点—— list（STL）。下面话不多说坐稳扶好咱们要开车了😍

一、list简介

1.概念

std::list是C++标准库中的双向链表容器。(这里有官方介绍链接) 它支持在任意位置进行快速插入和删除操作，并且在需要对元素进行频繁的插入和删除操作时，通常比std::vector更高效。std::list的元素不是在连续内存中存储，而是通过指针相互连接在一起。

2.特点

1. 双向访问：std::list的元素可以通过双向迭代器从前向后或者从后向前进行访问。
2. 插入和删除操作高效：由于std::list的元素是通过指针连接在一起的，插入和删除操作只需要修改相邻元素的指针，因此在任意位置进行插入和删除操作的时间复杂度是O(1)。
3. 不支持随机访问：由于std::list的元素不是在连续内存中存储的，因此不能通过下标来随机访问元素。如果需要随机访问元素，可以考虑使用std::vector或者std::array。
4. 内存占用相对较大：由于每个元素都需要额外的指针来连接其他元素，std::list的内存占用相对较大。

二、list的使用

list 中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

1.list的构造

std::list类提供了多个构造函数，用于创建和初始化std::list对象。官方链接点这里跳转 下面是常用的构造函数列表：

1. 默认构造函数：std::list<T> myList;创建一个空的std::list对象，其中T是元素的类型。
2. 带有容量参数的构造函数：std::list<T>myList(size, value);创建一个包含size个元素的std::list对象，每个元素的值都是value。
3. 区间构造函数：std::list<T>myList(first, last);创建一个std::list对象，其中包含[first, last)区间的元素。first和last是输入迭代器，用于指定要拷贝到新std::list中的元素范围。
4. 拷贝构造函数：std::list<T>myList(otherList);创建一个std::list对象，其中包含与otherList相同的元素。这将执行深拷贝，即将otherList中的元素复制到新的std::list对象中。
5. 移动构造函数：std::list<T>myList(std::move(otherList));创建一个std::list对象，并从其他std::list对象otherList中移动元素到新的std::list对象中。在移动构造函数后，otherList将为空。

注意：上述构造函数中的T表示元素的类型，可以是任何有效的C++类型。

#include<list>intmain(){// 默认构造函数
    std::list<int> myList;// 带有容量参数的构造函数
    std::list<int>myList2(5,10);// 包含5个值为10的元素// 区间构造函数int arr[]={1,2,3,4,5};
    std::list<int>myList3(std::begin(arr), std::end(arr));// 包含数组arr的元素// 拷贝构造函数
    std::list<int>myList4(myList2);// 移动构造函数
    std::list<int>myList5(std::move(myList4));// myList4将为空return0;}

这些是std::list常用的构造函数示例。你可以根据自己的需求选择适当的构造函数来创建std::list对象。

2.常见的操作

⭕std::list类型的增、删、查、改

1. 插入元素：- push_back(value)：在列表的末尾插入一个元素。- push_front(value)：在列表的开头插入一个元素。- insert(pos, value)：在指定位置pos之前插入一个元素。
2. 删除元素：- pop_back()：删除列表末尾的元素。- pop_front()：删除列表开头的元素。- erase(pos)：删除指定位置pos处的元素。- erase(first, last)：删除从[first, last)范围内的所有元素。
3. 访问元素：- front()：返回列表的第一个元素的引用。- back()：返回列表的最后一个元素的引用。
4. 迭代器操作：- begin()：返回指向列表第一个元素的迭代器。- end()：返回指向最后一个元素之后位置的迭代器。- rbegin()：返回指向列表最后一个元素的逆向迭代器。- rend()：返回指向第一个元素之前位置的逆向迭代器。
5. 大小和清空操作：- size()：返回列表中元素的数量。- empty()：检查列表是否为空。- clear()：清除列表中的所有元素。
6. 修改元素：- assign(first, last)：用[first, last)范围内的元素替换列表的内容。- assign(n, value)：用n个值为value的元素替换列表的内容。- resize(count)：改变列表的大小，使其包含count个元素，并根据需要插入或删除元素。- swap(otherList)：交换当前列表与otherList之间的内容。
7. 查找和排序：- find(value)：返回指向第一个值为value的元素的迭代器；如果找不到，则返回end()。- sort()：按升序对列表中的元素进行排序。- reverse()：反转列表中的元素的顺序。

以上只是std::list的一些常见操作，还有很多其他的成员函数可用于更复杂的操作。这里有官方的链接你可以根据具体的需求选择适当的操作。

以下是一些示例，展示了std::list的常见操作：

#include<list>#include<iostream>intmain(){
    std::list<int> myList;// 插入元素
    myList.push_back(1);
    myList.push_front(2);
    myList.insert(std::next(myList.begin()),3);// 删除元素
    myList.pop_back();
    myList.pop_front();
    myList.erase(std::next(myList.begin()));// 访问元素
    std::cout <<"Front element: "<< myList.front()<< std::endl;
    std::cout <<"Back element: "<< myList.back()<< std::endl;// 迭代器操作for(auto it = myList.begin(); it != myList.end();++it){
        std::cout <<*it <<" ";}
    std::cout << std::endl;// 大小和清空操作
    std::cout <<"Size: "<< myList.size()<< std::endl;
    std::cout <<"Empty: "<<(myList.empty()?"Yes":"No")<< std::endl;
    myList.clear();// 查找和排序
    myList.push_back(5);
    myList.push_back(2);
    myList.push_back(4);
    myList.push_back(1);auto it = myList.find(4);
    ifit != myList.end()){
        std::cout <<"Found value 4"<< std::endl;}

    myList.sort();
    std::cout <<"Sorted list: ";for(constauto& element : myList){
        std::cout << element <<" ";}
    std::cout << std::endl;return0;}

三、list与vector的对比

1. 数据存储方式：- vector：使用连续的内存块存储，可以在O(1)时间内访问任意位置的元素。- list：使用双向链表存储，每个节点存储一个元素，在O(n)时间内访问任意位置的元素。
2. 动态性：- vector：动态数组，长度可变。能够动态增长和收缩，但在插入和删除操作时可能需要重新分配内存，导致数据的搬移。- list：由于使用链表存储，插入和删除操作相对快速，不会涉及内存的重新分配和数据的搬移。
3. 访问效率：- vector：由于数据存储在连续的内存块中，可以通过下标访问元素，提供了O(1)的随机访问效率。- list：需要遍历链表才能访问到指定位置的元素，访问效率为O(n)。
4. 插入和删除操作：- vector：在尾部进行插入和删除操作效率高，复杂度为O(1)；在中间或头部进行插入和删除操作会导致后续元素的移动，复杂度为O(n)。- list：在插入和删除操作时，只需修改相邻节点的指针，复杂度为O(1)，对于任意位置的插入和删除都具有较高效率。
5. 内存使用：- vector：由于数据存储在连续的内存块，相对于list可能产生更少的内存开销。- list：由于每个元素需要额外的指针进行连接，相对于vector可能产生更多的内存开销。

综上所述，当需要频繁进行随机访问操作或者需要动态增长和收缩容量时，vector是一个更好的选择。而在需要频繁进行插入和删除操作、对访问效率要求不高或者需要避免数据搬移时，list是一个更合适的选择。

温馨提示

感谢您对博主文章的关注与支持！在阅读本篇文章的同时，我们想提醒您留下您宝贵的意见和反馈。如果您喜欢这篇文章，可以点赞、评论和分享给您的同学，这将对我提供巨大的鼓励和支持。另外，我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！

再次感谢您的支持和关注。我们期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！