【C++】学习STL中的list

❤️前言

大家好！，今天为大家带来的一篇博客是关于STL中的list，内容主要包括list的介绍使用、list的模拟实现。以及list与vector的对比。

正文

list的介绍和使用

首先，让我们看看list的文档介绍：

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

官方网站list的文档介绍如下：

list - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/list/list/?kw=list list的简单使用在我们学会了vector的使用之后只要多看看list的文档并多加使用就可以很熟悉，因此在这里就不多讲了。

需要提一提的是，由于存储在其中的元素的内存并不是连续的，list并不支持随机访问，也没有提供重载方括号。并且因此它并不适合算法库中的sort()和reverse()，于是在我们想要对list进行排序或者逆置的时候，应该使用list自带的接口，它们的名字与算法库中的一样。

除此之外，使用list时也可能遇到迭代器失效的问题，这时候我们需要重新为迭代器赋值来解决这个问题。

list的模拟实现

list的模拟实现分为三个部分，分别为：list的节点、list的迭代器、list本体。

list_node的模拟实现

首先我们模拟实现list的节点，双向链表需要节点具有前后两个指针：

template<typename T>
struct list_node
{// 我们初学类模板时常常会忘记写<T>// 这里需要注意，模板名带上尖括号之后才会成为类型名list_node<T>* _prev;list_node<T>* _next;T _val;list_node<T>(const T& x = T()):_prev(nullptr),_next(nullptr),_val(x){}
};

list迭代器的模拟实现

然后我们要接着模拟实现list的迭代器，这里我们有一个很重要的设计，就是设置多个模板参数，对应数据类型，数据的引用类型，数据的指针类型。

设计的思路：当我们设计迭代器类的时候，不仅要考虑普通的迭代器，还要考虑const迭代器，它并不是简单的在迭代器类声明对象前加上const关键字就可以。因为我们的const迭代器并不意味着我们不能改动这个迭代器对象本身，而是我们不能改动此迭代器所指向的数据。因此我们需要对迭代器类的一些接口的返回值类型做改动，也就是 * 号和 -> ，原因是这两个重载运算符会提供操作数据的方式。这种设计很好的减少了代码的冗余，使我们不用再另写一份const迭代器。

除此之外，迭代器实现中比较独特的一点就是->运算符的重载，我们可以看到这里的运算符重载返回值为节点值的地址，那么我们获得了节点数据的地址之后继续要访问节点值的成员，应该要再使用一次->运算符，那么在具体应用中我们就需要使用两个箭头，也就是 iterator->->member ，但是这不符合我们使用->运算符的习惯，于是编译器就为我们简化了一下，只要使用一次箭头，编译器自己会正确识别这样的写法。

	template<typename T, typename Ref, typename 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){_node = _node->_next;return _node->_prev;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){_node = _node->_prev;return _node->_next;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};

除了正向迭代器之外，我们还有一个反向迭代器，反向迭代器的使用规则与正向迭代器完全相反，如果我们直接重新定义一个反向迭代器的类模板，那么我们就需要为每一种迭代器都再写一份反向迭代器，这样代码会非常的冗余。于是这里就引出了一个新的概念——适配器模式。

由于反向迭代器的规则与迭代器完全相反，反向迭代器的许多地方其实是可以复用对应正向迭代器本身的接口。那么我们就将迭代器类型作为一个模板参数传入，然后在反向迭代器内部创建一个正向迭代器，之后就可以直接对其进行相反的操作，这样我们就得到了一个可以复用的反向迭代器模板。代码如下：

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{typedef Reverse_iterator<Iterator, Ref, Ptr> self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){return *_it;}Ptr operator->(){return &_it->_node->_val;}self& operator++(){return --_it;}self operator++(int){return _it--;}self& operator--(){return ++_it;}self operator--(int){return _it++;}bool operator!=(const self& rit) const{return _it != rit._it;}bool operator==(const self& rit) const{return _it == rit._it;}private:Iterator _it;
};

list本身的实现

list本身的实现非常简单，我们之前在数据结构时期已经学过了链表的相关知识，写个双向循环链表应该是不在话下。简单代码如下：

template<typename T>
class list
{typedef list_node<T> Node;
public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;reverse_iterator rbegin(){return (iterator)_head->_prev;}reverse_iterator rend(){return (iterator)_head;}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}list<T>(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list<T>(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto& x : lt){push_back(x);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}// 复用insert的代码void push_back(const T& x){//Node* tail = _head->_prev;//Node* newnode = new Node(x);//newnode->_next = tail->_next;//newnode->_prev = tail;//tail->_next = newnode;//_head->_prev = newnode;//_size++;insert(end(), x);}// 复用erase的代码void pop_back(){//Node* tail = _head->_prev;//Node* nexttail = tail->_prev;//_head->_prev = nexttail;//nexttail->_next = _head;//delete tail;//_size--;erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}// pos之前位置插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);newnode->_prev = prev;newnode->_next = cur;prev->_next = newnode;cur->_prev = newnode;_size++;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return next;}size_t size(){return _size;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}~list<T>(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size = 0;
};