list类
基础介绍
list类
是STL中封装的链表模板类,并且底层实现是以双向链表作为基础进行封装的。在数据结构中,线性存储结构中主要分为顺序表和链表,前者在物理结构上拥有连续的内存空间和地址,在STL中vector
和string
都是使用了这种结构,其最大的特点就是方便进行随机访问并且尾插和尾删都能达到O1的时间复杂度并且使用方便,而链表作为物理结构上内存空间不连续的数据结构,其最大的特点就是方便在任何位置就行插入删除,list
就是建立在此数据结构上封装出的模板类。
常用接口
构造函数
1 | list(); //构造空的list |
迭代器相关
1 | begin(); //返回第一个元素的迭代器 |
容量相关
1 | bool empty() const; //检测list是否为空,是返回true,否则返回false |
增删查改
1 | reference front(); //返回list的第一个节点中值的引用 |
emplace与insert
在STL很多接口中我们都发现有一个emplace()
的接口也是用来进行插入的,那么它与insert()
和push_back()
有什么区别呢?以下用vector
举个例子,从接口调用上就能看出区别。
1 | #include <iostream> |
在进行内置类型和拥有单参构造函数的类型的插入时我们只传入一个参数往往很难发现区别,但在我们必须传入多个参数才能进行插入时我们就会发现在使用insert()
这些接口时我们必须插入与容器中元素类型相同的元素才能完成接口调用,这让我们不得不构造一个临时匿名对象,而emplace
则不需要,我们只要按照构造一个对象那样给构造元素的参数即可省去了构造匿名对象的过程。而这其中需要用到C++11
中的新标准变参模板和完美转发,因此emplace
使用的时候要求编译器支持C++11
标准。
emplace
不光是调用接口上有所不同,在有的时候也可以提高我们的效率。例如在list
中如果利用insert
传入一个元素的时候我们就需要先调用元素的构造函数构造元素,然后再调用Node
的构造函数以及该元素的拷贝构造函数构造一个拥有该元素值的结点,才能进行插入,而emplace
则可以在创建结点时直接利用原本要构造临时元素对象的参数来直接构造结点,并且直接构造结点中的元素对象,相当于少了一次元素的拷贝构造,并且省去了构造临时对象,效率更高。
list迭代器失效
对于list
这种链式结构,在插入后是不会迭代器失效的,因为原先位置的迭代器依旧指向原来的结点,不会因为添加结点导致指向位置的变动。而在删除后迭代器原本指向的结点内存被释放,因此删除后删除结点的迭代器失效,但是其他结点迭代器指向不变因此不会发生迭代器失效。
总结:list只有在删除节点后才会发生迭代器失效,并且只有删除结点的迭代器失效。
实现
list
采用链式结构存储,因此实现起来要稍微麻烦一些,迭代器也需要额外进行封装。
1 | #include <assert.h> |