当前位置：首页 > ds >正文

C++--List的模拟实现

ds 2025/7/14 16:47:27

一,引言

为了更好的掌握list的接口的熟练掌握，理解list的底层接口的底层逻辑。为此通过list的模拟实现来提高对自身对list的理解。首先list是带头双向循环链表。以及list的底层物理空间并不连续，因此list的迭代器并不能使用原生指针进行封装。最后list的链表是由每一个节点组成。为此list的模拟实现需要准备三个部分1,node节点2,迭代器封装3,list链表。

二,node节点

list的底层是带头双向循环链表，因此node节点由三部分组成1,存储数据变量2,指向前一个位置的指针3,指向后一个位置的指针。并对节点实现初始化。在C++中通过一个类对该节点进行封装。具体用例如下：

template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}};

节点的三个成员变量，并且对该节点进行初始化。

三,迭代器封装

list的底层为链表，物理空间并不连续，因此不能使用原生指针对迭代器进行封装。迭代器指向节点数据，所以将迭代器设置成节点指针的形式。并且对迭代器实现++，--，*，==，!=。等接口进行封装。另外在简单的迭代器分为const和非const两种；在本次模拟实现中使用三个模板参数进行控制。来看如下图：

通过不同的模板变量来具体控制是否是const类型。具体代码如下：

template<class T, class Ref, class 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->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};

四,list链表

做好前两部分准备工作之后就可以着手实现list标准库内部的相关接口。首先在一个size控制list容器的数据个数，_head指向带头节点。并且在初始化阶段建立哨兵位。具体代码如下：

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;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}private:Node* _head;size_t _size;};

将list的基本框架搭建好之后，就可以进行接口的实现，这次仅仅实现最主要的接口。

insert，pop_back,pop_front,push_back,push_front,erase,clear等等，具体实现如下：

list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void push_back(const T& x){/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;++_size;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;++_size;return newnode;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}size_t size() const{return _size;}bool empty() const{return _size == 0;}