【c++_containers】10分钟带你学会list

2023-10-06 23:45

本文主要是介绍【c++_containers】10分钟带你学会list,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

        链表作为一个像是用“链子”链接起来的容器,在数据的存储等方面极为便捷。虽然单链表单独在实际的应用中没用什么作用,但是当他可以结合其他结构,比如哈希桶之类的。不过今天学习的list其实是一个带头双向链表。

言归正传,让我们看一下list的特性。

一、list的特性

这里我还是推荐去cplusplus上阅读英文原文档。这里我总结了几条,

1. list 是可以在常数范围内 在任意位置进行插入和删除的序列式容器 ,并且该容器 可以前后双向迭代。
2. list 的底层是 双向链表结构 ,双向链表中每个 元素存储在互不相关的独立节点 中,在节点中通过指针指向其前一个元素和后一个元素。
3. list forward_list 非常相似:最主要的不同在于 forward_list是单链表 ,只能朝前迭代,已让其更简单高效。
4. 与其他的序列式容器相比 (array vector deque) list 通常 在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比, list forward_list 最大的缺陷是 不支持任意位置的随机访问 ,比如:要访问 list的第6 个元素,必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置,在这段位置上迭代需要线性的时间开销;list 还需要一些 额外的空间, 以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素)。

其物理模型简化后如下图:

二、list的基本结构

前面我们提到list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。那么他每个小结点的结构就变得清楚明了了。

    template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _val;list_node(const T& val = T()): _prev(nullptr), _next(nullptr), _val(val){}			};

随后我们就可以写list的本体了

    template<class T>class list{typedef list_node<T> Node;private:Node* _head;//哨兵位size_t _size;};

加一个表示size的数据是因为list的空间是不连续的。

三、list的基础构造

        void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}list(){empty_init();}

将empty经行再封装是因为这样的构造函数设计可以方便地创建空的list对象,并且避免了在创建list对象时必须显式地指定初始大小。同时,通过将初始化代码封装在empty_init()函数中,可以简化list类的实现,提高代码的可读性和可维护性。

四、list的插入与删除

与vector不同的是list的其他几种构造或多或少的依赖插入,而且哨兵位的初始化就可以继续后面的操作。当然插入和删除是list的重要点。

我们先从尾插写起,如图当插入一个节点时我们可以先新建一个新的节点,将值存入其中。然后将末尾(_head->_prev)的_next与newnode链接,然后将new的_prev与末尾链接,最后将头节点的_prev指向newnode,newnode的_next与_head链接。

        void push_back(const T&x){Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;_size++;}

而对于任意位置插入,其实和上面的逻辑相似。

        //在pos之前插入,返回新插入元素位置iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}

与次对立的是list任意位置的删除。逻辑就是他反过来。

        iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;}

但是list的删除面临着迭代器的失效前面说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响

比如下面的案例:

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it); ++it;}// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给
其赋值改正后:
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);}
}

当这两个比较泛型的插入与删除实现后其余代码就变得简单了。

//拷贝构造        list(const list<T>& lt)//list(const list& lt){empty_init();for (auto& e : lt){push_back(e);}}
//析构函数~list(){clear();delete _head;_head = nullptr;}
//头插void push_front(const T& x){insert(begin(), x);}
//尾删void pop_back(){erase(--end());}
//头删void pop_front(){erase(begin());}
//清空void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}

五、list的迭代器

list的迭代器我们要实现的主要就是他的++与--问题,而++就是返回当前位置的_next, --就是返回当前位置的_prev。

template<class T,class Ref,class Ptr>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T, Ref,Ptr> self;Node* _node;_list_iterator(Node* node):_node(node){}Ref& operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}self& operator++() {_node = _node->_next;return *this;}self& operator++(int)//后置{self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self & it)const{return _node != it._node;}bool operator==(const self & it)const{return _node == it._node;}};

_list_iterator类模板的三个类型参数分别为T(元素类型)、Ref(引用类型)和Ptr(指针类型)。这个类包含一个成员变量_node,它是一个指向list_node对象的指针,用于存储当前迭代器所指向的节点。这里的Ref与Ptr主要用于分辨const与非const.

六、list与vector的对比

vector
list
动态顺序表,一段连续空间
带头结点的双向循环链表
访
支持随机访问,访问某个元素效率 O(1)
不支持随机访问,访问某个元素 效率 O(N)
任意位置插入和删除效率低,需要搬移元素,时间复杂 度为 O(N) ,插入时有可能需要增容,增容:开辟新空 间,拷贝元素,释放旧空间,导致效率更低
任意位置插入和删除效率高,不
需要搬移元素,时间复杂度为 O(1)
底层为连续空间,不容易造成内存碎片,空间利用率
高,缓存利用率高
底层节点动态开辟,小节点容易
造成内存碎片,空间利用率低,
缓存利用率低
原生态指针
对原生态指针 ( 节点指针 ) 进行封装
在插入元素时,要给所有的迭代器重新赋值,因为插入
元素有可能会导致重新扩容,致使原来迭代器失效,删
除时,当前迭代器需要重新赋值否则会失效
插入元素不会导致迭代器失效,
删除元素时,只会导致当前迭代
器失效,其他迭代器不受影响
使
需要高效存储,支持随机访问,不关心插入删除效率
大量插入和删除操作,不关心随
机访问

这篇关于【c++_containers】10分钟带你学会list的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/154673

相关文章

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,:本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例:2. strerror()示例:3. perror(