【STL】list的使用

诺诺的包包

发布于 2023-10-15 13:58:34

1600

发布于 2023-10-15 13:58:34

文章被收录于专栏：个人笔记总结个人笔记总结

放在专栏【C++知识总结】，会持续更新，期待支持🌹

1、list简介

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
list的底层是带头双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好（时间复杂度：O(1)）。
与其他序列式容器相比，list和forward_list（单向链表）最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息。

相对于vector来说，list对于空间的运用有着绝对的精准，不会存在一点的浪费，因为list是每插入或删除一个元素，就配置或释放一个元素空间。而vector则采用1.5或者2倍扩容机制，会存在一定程度上的空间浪费。两者各有优点。

2、list的数据结构

list本身与list节点，这两个是完全不同的结构，是需要分开来设计的，对于一个list节点来说，由于list是双向环状链表（双向带头循环链表），所以需要提供两个指针，一个指向前一个元素，一个指向另一个元素，同时还需要一个val，用来存储数据。如下所示为SGI版本的list底层（稍作修改，便于学习）：

//list节点
template<class T>
struct _list_node
{
	_list_node<T>* _prev;//指向前一个元素
	_list_node<T>* _next;//指向后一个元素
	T _data;             //用来存储数据
};
//list
template<class T>
class list
{
	typedef _list_node<T> node;
public:
	//.....
private:
	node* _head;//只需要一个指针，便可以表示整个双向循环链表
};

需要注意到的是，list由于存储空间并不是连续的，因此这里的迭代器并不像string与vector那样，是一个原生指针，这里list的迭代器是用一个对象，来模拟指针的行为，从而实现对list元素的访问。具体在后面模拟实现时会详细讲解。这里我们先了解其使用即可：

3、list的使用

在使用前，需要包含头文件<list>

3.1、构造相关

3.1.1、构造一个空容器

	list<int> l;//构造一个存储元素为int类型的空list

3.1.2、构造含有n个val的某类型容器

	list<int> l(10, 5);//构造一个含有10个元素，元素类型为int，值为10的list

3.1.3、拷贝构造

	list<int> l1(5, 1);//l1:1 1 1 1 1
	//拷贝构造
	list<int> l2(l1);  //l2:1 1 1 1 1
	//也可以写成list<int> l2=l1;

3.1.4、迭代器区间构造

	//迭代器区间构造(左闭右开)
	string s("hello world!");
	list<char> l(s.begin(), s.begin() + 5);
	//l:h e l l o

可以看到，整体使用实际上与string或vector并无太大区别，用起来很简单。

3.2、容量相关

3.2.1、size与empty

这里list只存在size，表示list中有效节点个数，而empty就不用说了，用来判断容器是否为空。

3.2.2、resize

与vector相同，resize可以实现对有效元素的扩容或“缩容”，当resize(n,val)时，如果n的值>当前size值，则list会进行扩容到size为n，扩容出来的元素值用val来充当，当n的值<size时，list会缩容到n大小。如下：

3.3、元素访问

3.3.1迭代器

迭代器是个很奇妙的设计，所有的容器，通过迭代器都可以进行访问容器中的元素，list也不例外，用起来也很简单，就像vector中一样用即可。

这里，begin与end分别指向list中第一个有效元素，以及最后一个有效元素的下一个位置，而我们的begin与end区间，通常都是左闭右开，对于环状的链表来说，只需要在尾端加入一个空白节点，便符合STL规范之“前闭后开”。（实际就是一个双向带头循环链表）如下所示：

当然，list中也存在const迭代器，以及反向迭代器，分别对应cbegin与cend（const正向迭代器）、rbegin与rend（反向迭代器）、crbegin与crend（const反向迭代器），const类型的迭代器的特点就是不能对指向的元素做修改。不过需要注意的是，rbegin与end对应，rend与begin对应。

这里我们在后续模拟实现时也会讲到。

list有关迭代器的相关接口

3.3.2、迭代器失效问题

我们知道迭代器失效指的就是迭代器指向了一块不属于它的空间，或者指向的空间已经被销毁了。这里list由于不像vector那样，vector的插入操作可能会引起扩容，从而导致迭代器失效，而list则不会，因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

如下所示为迭代器失效场景：