【C++】STL之list模拟实现：关于链表容器的双向迭代器你知道多少？

前言：

前面的博客中我已经介绍了STL核心容器之一的list相关接口的使用，今天我们就从底层出发，来模拟实现一下list的那些核心接口函数。同时，也来感受一下list的双向迭代器到底与string和vector的随机迭代器有哪些区别？

list容器功能接口介绍：https://blog.ZEEKLOG.net/Miun123/article/details/151685386?spm=1001.2014.3001.5502

废话不多说，我们直接进入今天的正题👇️👇️👇️

list容器深度剖析及模拟实现

我们想要模拟实现list容器，那就要理解list容器的底层结构。前面的博客已经提到，其本质就是一个双向链表，所以，成员变量就应该包含一个记录头节点的指针，以及记录有效节点个数的变量。同时，为了list容器可以满足不同类型的数据，我们将所有的类实现为类模板。

1、定义节点结构

struct创建的类默认所有的成员但是公开的，而节点结构就需要公开被list访问。

template<class T> struct list_node { // 成员变量 T _data; list_node<T>* _next; list_node<T>* _prev; // 默认构造 list_node(const T& val = T()) :_data(val) , _next(nullptr) , _prev(nullptr) {} };

2、双向迭代器

我们先看一段 slt_list.h头文件 中实现list迭代器的源码：（注释是本人自己加的）

template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; // 普通迭代器 typedef __list_iterator<T, const T&, const T*> const_iterator; // const迭代器 typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; // 数据类型 typedef Ptr pointer; // 指针类型 typedef Ref reference; // 引用类型 typedef __list_node<T>* link_type; // 节点类型 typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; // 成员变量 __list_iterator(link_type x) : node(x) {} // 拷贝构造 __list_iterator() {} // 默认构造 __list_iterator(const iterator& x) : node(x.node) {} // 拷贝构造 bool operator==(const self& x) const { return node == x.node; } // 重载== bool operator!=(const self& x) const { return node != x.node; } // 重载!= reference operator*() const { return (*node).data; } // 重载————解引用* #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } // 重载-> #endif /* __SGI_STL_NO_ARROW_OPERATOR */ self& operator++() { //重载前置++ node = (link_type)((*node).next); return *this; } self operator++(int) { // 重载后置++ self tmp = *this; ++*this; return tmp; } self& operator--() { // 重载前置-- node = (link_type)((*node).prev); return *this; } self operator--(int) { // 重载后置-- self tmp = *this; --*this; return tmp; } };

和前面string和vector的迭代器不同，list的迭代器不仅自己封装成了一个单独的类模板，而且这个类模板的模板参数有三个。这是为什么呢❓️

我们知道，对于const对象和非const对象，如果将模板参数只有一个<class T>，那么我们势必就要实现两个迭代器的类模板。而这两个类模板中，只有解引符号重载函数和箭头 ->重载函数由于返回值与其对应的类型有关（因为对于const对象，我们无法通过解引用和->改变const对象的值）而实现方式稍有不同；对于其他函数，在两个类模板中就重复了。所以，我们为了避免这种情况，就在类模板中引入了另外两个参数：Ref（T& / const T&——解引用操作符函数的返回值类型），     Ptr（T* / const T*—— ->重载函数的返回值类型）。

可以看到，在源码中typedef用得非常多，接下来我们就自己实现一个迭代器的类模板出来：其中++，--，==，!=，*，->这些操作符都是对节点的操作，所以，我们迭代器的类模板中应该有一个记录节点的成员变量_node。

template<class T, class Ref,class Ptr> struct list_iterator { typedef list_node<T> Node; typedef list_iterator<T, Ref, Ptr> Self; // Ref--T& / const T& ; Ptr--T* / const T* Node* _node; // 成员变量 list_iterator(Node* node) // 拷贝构造 :_node(node) {} // ... };

2.1、解引用

Ref& operator*()const { return _node->_data; }

2.2、->

Ptr operator->()const { return &(_node->_data); }

2.3、前置--  后置--

// 前置-- Self& operator--() { _node = _node->_prev; return *this; } // 后置-- Self operator--(int) { list_iterator<T> tmp(*this); _node = _node->_prev; return tmp; }

2.4、后置++  前置++

// 后置++ Self operator++(int) { Self tmp(*this); _node = _node->_next; return tmp; } // 前置++ Self& operator++() { _node = _node->_next; return *this; }

2.5、== 和 !=

bool operator==(const Self& s)const { return _node == s._node; } bool operator!=(const Self& s)const { return _node != s._node; }

3、list容器功能接口

template<class 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;// const迭代器 // ... private: Node* _head; // 头节点 size_t _size;// 有效节点个数 };

3.1、链表初始化

3.1.1、构造空链表

即创建头节点（哨兵位），并初始化

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

3.1.2、默认构造

list(){ empty_init(); }

3.1.3、拷贝构造

list(const list<T>& lt) { // 由于拷贝无法完成头节点初始化，所以先初始化头节点 empty_init(); for (auto e : lt) push_back(e); }

3.1.4、初始化列表

list(initializer_list<int> il) { empty_init(); for (auto& e : il) push_back(e); }

3.1.5、赋值重载

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; }

3.2、析构

~list() { clear(); // 清理所有节点 delete _head; // 释放头节点 _head = nullptr; }

3.3、迭代器

迭代器即可以理解为指针，我们用迭代器记录第一个有效节点和尾节点的位置。

iterator begin() { return _head->_next; } iterator end() { return _head; } const_iterator begin()const { return _head->_next; } const_iterator end()const { return _head; }

3.4、插入

先找到指定位置之后的节点：pos->next；然后。连接pos节点，新节点newnode与指定位置之后的节点pos->next。注意：连接顺序，防止改变pos->next的指向。

3.4.1、指定位置插入

iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); // 构造新节点 Node* pcur = pos._node; Node* prev = pos._node->_prev; // 连接：prev newnode pcur prev->_next = newnode; newnode->_prev = prev; newnode->_next = pcur; pcur->_prev = newnode; ++_size; // 有效节点个数加1 return pos; // 返回pos节点 }

3.4.2、头插

void push_front(const T& x) { insert(begin(), x); }

3.4.3、尾插

void push_back(const T& x) { insert(end(), x); }

3.5、删除节点

现在的指定位置节点之前的节点：pos->prev；指定位置之后的节点：pos->next。然后，连接pos->prev与pos->next。最后，释放指定位置节点。

3.5.1、删除指定位置节点

iterator erase(iterator pos) { assert(pos != end()); Node* prev = pos._node->_prev; Node* next = pos._node->_next; // 连接 prev next prev->_next = next; next->_prev = prev; // 释放 delete pos._node; pos._node = nullptr; --_size; return next; // 返回pos节点的下一个节点 }

3.5.2、头删

void pop_front() { erase(begin()); }

3.5.3、尾删

void pop_back() { erase(--end()); }

3.5.4、链表的清理

void clear() { auto it = begin(); while (it != end()) { it = erase(it); } }

3.6、获取节点个数

size_t size() const { return _size; }

3.8、判空

bool empty() const { return _size == 0; }

4、总结

那么，本期的分享就到此结束，如果大家觉得写的还不错的话，点个小爱心❤️支持一下吧😘😘😘，我们下期再见🤗🤗🤗