(C++ STL)list类的简单模拟实现与源码展示

以下代码环境为 VS2022 C++。

一、前言

list类 本质上是数据结构中的双向带头链表。（可参考：双向链表的讲解与实现）

不过要注意的是，list类 的本身并不支持随机访问，迭代器要求的前后 ++、-- 也不支持，导致这个重担交给了 list 的迭代器，使得它迭代器的设计要比 vector、string 的复杂不少。

接下来我们来简单实现 list类 和 部分对应函数。

参考：legacy.cplusplus.com中的 std::list

二、ListNode 单个节点的成员变量

在 list.hpp 中：

namespace my
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPrev(nullptr),_pNext(nullptr){;}ListNode<T>* _pPrev;	// 前一个节点地址ListNode<T>* _pNext;	// 后一个节点地址T _val;};
}

将 list 的节点单独封装为一个类，便于后续组合操作。

三、ListIterator 迭代器

在 namespace my 中：

    //List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;typedef Ref reference;typedef Ptr pointer;ListIterator(Node* pNode = nullptr):_pNode(pNode){;}ListIterator(const Self& listIter):_pNode(listIter._pNode){;}reference operator*(){return _pNode->_val;}reference operator*() const{return _pNode->_val;}pointer operator->(){return &_pNode->_val;}pointer operator->() const{return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp = _pNode;_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPrev;return *this;}Self operator--(int){Self temp = _pNode;_pNode = _pNode->_pPrev;return temp;}bool operator!=(const Self& listIter) const{return _pNode->_val != listIter._pNode->_val;}bool operator==(const Self& listIter) const{return _pNode->_val == listIter._pNode->_val;}Node* _pNode;};

ListIterator 设计了三个模版关键字，class T, class Ref, class Ptr，这是考虑到 const_iterator 的返回类型。

例如：当返回 operator*() 的返回值时，使用 iterator 返回的是 T 的 引用，也就是 T&，
但使用 const_iterator 返回的是 const T&，两者只差一个 const 权限。pointer、Self 同理。

当然，也可以选择重新设计一个 const_iterator类，这里只是用模版减少了工作量。

四、ReverseListIterator 迭代器

在 namespace my 中：

    // 反向迭代器template<class Iter>struct ReverseListIterator{typedef ReverseListIterator<Iter> Self;typedef typename Iter::reference reference;typedef typename Iter::pointer pointer;ReverseListIterator(const Iter& it = Iter()):_it(it){;}ReverseListIterator(const Self& listIter):_it(listIter._it){;}reference operator*(){return *_it;}reference operator*() const{return *_it;}pointer operator->(){return _it->_val;}pointer operator->() const{return _it->_val;}Self& operator++(){--_it;return *this;}Self operator++(int){Self temp = *this;--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp = *this;++_it;return temp;}bool operator!=(const Self& listIter) const{return (*_it) != (*listIter._it);}bool operator==(const Self& listIter) const{return (*_it) == (*listIter._it);}Iter _it;};

反向迭代器组合了 ListIterator类，毕竟 iterator 的 + + 等价 reverse_iterator 的 - -，而它的 - - 等价 reverse_iterator 的 + +。

五、list 的成员变量与初始化

在 namespace my 中：

    template<class T>class list{public:typedef ListNode<T>* PNode;typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;typedef ReverseListIterator<iterator> reverse_iterator;typedef ReverseListIterator<const_iterator> const_reverse_iterator;private:PNode CreateNode(const T& value = T()){return new Node(value);}PNode CreateHead(){PNode temp = CreateNode();temp->_pNext = temp;temp->_pPrev = temp;return temp;}PNode _pHead = CreateHead();	// 走初始化列表时会执行size_t _size;};        

考虑到 list类 必须要带头，这里直接声明在初始化时候带头，方便后续操作。

六、list 部分函数实现

insert

这里只实现一个。

参考：std::list::insert

在 list.hpp 中：

template<typename T>
typename my::list<T>::iterator my::list<T>::insert(my::list<T>::iterator pos, const T& val)
{PNode cur = pos._pNode;PNode prev = pos._pNode->_pPrev;PNode newNode = CreateNode(val);newNode->_pPrev = prev;newNode->_pNext = cur;prev->_pNext = newNode;cur->_pPrev = newNode;++_size;return newNode;
}

erase

参考：std::list::erase

这里只实现一个。

在 list.hpp 中：

template<typename T>
typename my::list<T>::iterator my::list<T>::erase(my::list<T>::iterator pos)
{PNode cur = pos._pNode;PNode prev = cur->_pPrev;PNode next = cur->_pNext;prev->_pNext = next;next->_pPrev = prev;--_size;delete cur;pos = nullptr;return next;
}

其他实现了的函数不是复用就是代码量小，就不单独拎出来介绍了。

七、list 源代码

#pragma once#include<iostream>namespace my
{// List的节点类template<class T>struct ListNode{ListNode(const T& val = T()):_val(val),_pPrev(nullptr),_pNext(nullptr){;}ListNode<T>* _pPrev;	// 前一个节点地址ListNode<T>* _pNext;	// 后一个节点地址T _val;};//List的迭代器类template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;typedef Ref reference;typedef Ptr pointer;ListIterator(Node* pNode = nullptr):_pNode(pNode){;}ListIterator(const Self& listIter):_pNode(listIter._pNode){;}reference operator*(){return _pNode->_val;}reference operator*() const{return _pNode->_val;}pointer operator->(){return &_pNode->_val;}pointer operator->() const{return &_pNode->_val;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp = _pNode;_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPrev;return *this;}Self operator--(int){Self temp = _pNode;_pNode = _pNode->_pPrev;return temp;}bool operator!=(const Self& listIter) const{return _pNode->_val != listIter._pNode->_val;}bool operator==(const Self& listIter) const{return _pNode->_val == listIter._pNode->_val;}Node* _pNode;};// 反向迭代器template<class Iter>struct ReverseListIterator{typedef ReverseListIterator<Iter> Self;typedef typename Iter::reference reference;typedef typename Iter::pointer pointer;ReverseListIterator(const Iter& it = Iter()):_it(it){;}ReverseListIterator(const Self& listIter):_it(listIter._it){;}reference operator*(){return *_it;}reference operator*() const{return *_it;}pointer operator->(){return _it->_val;}pointer operator->() const{return _it->_val;}Self& operator++(){--_it;return *this;}Self operator++(int){Self temp = *this;--_it;return temp;}Self& operator--(){++_it;return *this;}Self operator--(int){Self temp = *this;++_it;return temp;}bool operator!=(const Self& listIter) const{return (*_it) != (*listIter._it);}bool operator==(const Self& listIter) const{return (*_it) == (*listIter._it);}Iter _it;};//list类template<class T>class list{public:typedef ListNode<T>* PNode;typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T&> const_iterator;typedef ReverseListIterator<iterator> reverse_iterator;typedef ReverseListIterator<const_iterator> const_reverse_iterator;public://-----------------------------------------------list(){;}list(int n, const T& value = T()){for (int i = 0; i < n; ++i){push_back(value);}}list(std::initializer_list<T> il){for (const auto& e : il){push_back(e);}}template <class Iterator>list(Iterator first, Iterator last){while (first != last){push_back(*first);++first;}}list(const list<T>& list1){for (auto& e : list1){push_back(e);}}static void swap(list<T> list1, list<T> list2){std::swap(list1._pHead, list2._pHead);std::swap(list1._size, list2._size);}list<T>& operator=(list<T> list1){swap(*this, list1);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}//-----------------------------------------------iterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead->_pNext;}const_iterator end() const{return _pHead;}reverse_iterator rbegin(){return iterator(_pHead->_pPrev);}reverse_iterator rend(){return iterator(_pHead);}const_reverse_iterator rbegin() const{return const_iterator(_pHead->_pPrev);}const_reverse_iterator rend() const{return const_iterator(_pHead);}//-----------------------------------------------size_t size() const{return _size;}bool empty() const{return _size == 0;}//-----------------------------------------------T& front(){return _pHead->_pNext;}const T& front()const{return _pHead->_pNext;}T& back(){return _pHead->_pPrve;}const T& back() const{return _pHead->_pPrve;}//-----------------------------------------------void push_back(const T& val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T& val){insert(begin(), val);}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& val);iterator erase(iterator pos);void clear(){iterator it = begin();while (it != end()){it = erase(it);}}private:PNode CreateNode(const T& value = T()){return new Node(value);}PNode CreateHead(){PNode temp = CreateNode();temp->_pNext = temp;temp->_pPrev = temp;return temp;}PNode _pHead = CreateHead();size_t _size;};
};template<typename T>
typename my::list<T>::iterator my::list<T>::insert(my::list<T>::iterator pos, const T& val)
{PNode cur = pos._pNode;PNode prev = pos._pNode->_pPrev;PNode newNode = CreateNode(val);newNode->_pPrev = prev;newNode->_pNext = cur;prev->_pNext = newNode;cur->_pPrev = newNode;++_size;return newNode;
}template<typename T>
typename my::list<T>::iterator my::list<T>::erase(my::list<T>::iterator pos)
{PNode cur = pos._pNode;PNode prev = cur->_pPrev;PNode next = cur->_pNext;prev->_pNext = next;next->_pPrev = prev;--_size;delete cur;pos = nullptr;return next;
}