C++_list简单源码剖析：list模拟实现

文章目录

- 🚀1. ListNode模板
- 🚀2. List_iterator模板(重要)
- - 🌱2.1 List_iterator的构造函数
  - 🌱2.2 List_iterator的关于ListNode的行为
- 🚀3. Reverse_list_iterator模板(拓展)
- 🚀4. List模板(核心)
- - 🌱4.1 List构造函数
  - 🌱4.2 List迭代器
  - 🌱4.3 List内容相关函数
  - 🌱4.4 List获取头尾元素
  - 🌱4.5 List内存修改

大家好！本文会用C++模拟一个基本的list类，帮助我们更好的理解list的内置函数的实现与规则。在这里插入图片描述

list是带头双向循环链表，在C语言实现一个链表时，我们通常会实现两个结构体，List 与 ListNode,也就是封装了List的本体与List的节点，在C++模拟实现list也是如此，我们需要实现List与ListNode两个模板。

🚀1. ListNode模板

回忆C语言的链表节点封装，大致其实现为：

struct listnode
{listnode* next;listnode* prev;int val;
};

由此，ListNode的内容是比较简单，我们先行封装ListNode，以模板的形式实现，其成员变量只有一个val与两个指针：指针一个指向前节点，一个指向后节点，val就是存储的数据：

template<class T>
struct ListNode
{ListNode<T>* _prev;ListNode<T>* _next;T _val;//构造函数ListNode(const T& val = T()) :_prev(nullptr),_next(nullptr),_val(val){};
};

备注：

关于使用struct的原因：在C++中，如果一个类的成员变量全都是需要公开被访问的，我们通常使用struct不用class。我们封装ListNode，实际上是在List类中进行操作的，为了List能更方便的实现ListNode访问上下节点的操作，ListNode的成员必须的public的。
注: struct默认的所有成员是public，class默认的所有成员是private。
关于 const T& val = T()在 C++_vector简单源码剖析：vector模拟实现中⚡️内置类型也有构造函数 这里有说明，其实就是为了当T是内置类型(int , double)的时候，能顺利初始化val。

🚀2. List_iterator模板(重要)

Listiterator就是list的迭代器，提问🎤：在list类的封装中，能不能直接这么定义迭代器？->

template<class T>
class List
{
public:typedef ListNode<T> Node;typedef Node* iterator;
}

📜答案：不能，为什么🤔？在 C++_vector简单源码剖析：vector模拟实现中，实现vector的迭代器似乎就是这样实现的，为什么到了list就不行了？
💡解释：在这里插入图片描述
那要如何实现？既然默认的++或者–并不是我们所需要的，那么我们就要自己定义这些行为，这里就需要封装一个Listiterator模板，用一个类来封装ListNode与它的一些行为：

//List的迭代器模板
template<class T, class str, class ptr>
struct Listiterator
{typedef ListNode<T> Node;typedef Listiterator<T, str, ptr> Self;Node* _node;//迭代器的构造函数Listiterator(Node* pNode = nullptr);Listiterator(const Self& l);// ListNode的一些行为//前置++重载，当前节点到下一个节点Self operator++();//后置++重载，当前节点到下一个节点Self operator++(int);//前置--重载，当前节点到上一个节点Self operator--();//后置--重载，当前节点到上一个节点Self& operator--(int);//解引用重载str operator*();//->重载ptr operator->();//!=重载bool operator!=(const Self& l);//==重载bool operator==(const Self& l);
};

📈备注：

在List模板中会实例化两个版本的迭代器，一个iterator，一个const_iterator, str会传入 T& 与 const T&，ptr会传入T与const T * 。
Listiterator的内容只有一个成员变量ListNode和它的一些行为，这样的过程叫做封装

🌱2.1 List_iterator的构造函数

typedef ListNode<T> Node;
typedef Listiterator<T, str, ptr> Self;Node* _node;
//迭代器的构造函数
Listiterator(Node* pNode = nullptr){_node = pNode;
}
Listiterator(const Self& l) {_node = l._node;
}

📈备注：构造一个迭代器，让其成员ListNode = 传入的ListNode 。

🌱2.2 List_iterator的关于ListNode的行为

	typedef ListNode<T> Node;typedef Listiterator<T, str, ptr> Self;Node* _node;
//前置++重载，当前节点到下一个节点
Self operator++()
{_node = _node->_next;return *this;
};
//后置++重载，当前节点到下一个节点
Self operator++(int) {Node* tmp = _node;_node = _node->_next;return tmp;
};
//前置--重载，当前节点到上一个节点
Self operator--()
{_node = _node->_prev;return *this;
};
//后置--重载，当前节点到上一个节点
Self& operator--(int) {Node* tmp = _node;_node = _node->_prev;return tmp;
};
//解引用重载
str operator*()
{return _node->_val;
};
//->重载
ptr operator->()
{return &*this;
};
//!=重载
bool operator!=(const Self& l) {return l._node !=_node;
};
//==重载
bool operator==(const Self& l) {return l._node == _node;
};

📈备注：++让封装的ListNode指向下一个节点，–指向上一个节点， * 解引用得到当前节点的值，->通过this指针使用成员，比较相不相等就是比较是不是同个节点。

🚀3. Reverse_list_iterator模板(拓展)

Reverse_list_iterator就是反向迭代器。

//反向迭代器
template<class T, class str, class ptr>
struct Reverse_list_iterator
{typedef ListNode<T> Node;typedef Reverse_list_iterator<T, str, ptr> Self;Node* _node;//构造函数Reverse_list_iterator(Node* tmp):_node(tmp) {};//前置++重载Self operator++(){_node = _node->_prev;return *this;};//后置++重载Self operator++(int) {Node* tmp = _node;_node = _node->_prev;return tmp;};//前置--重载，Self operator--(){_node = _node->_next;return *this;};//后置--重载Self& operator--(int) {Node* tmp = _node;_node = _node->_next;return tmp;};//解引用重载str operator*(){return (_node->_prev)->_val;};//->重载shptr operator->(){return &*this;};//!=重载bool operator!=(const Self& l) {return l._node != _node;};//==重载bool operator==(const Self& l) {return l._node == _node;};};

📉省流：与正常迭代器不同的地方就是 ++ ， – ，和解引用 * ， * 解引用获得的是上一个节点的值。

🚀4. List模板(核心)

List模板有很多的成员函数，我们先大致浏览一下它的成员：

	template<class T>class List{public:typedef ListNode<T> Node;//迭代器命名typedef Listiterator<T, T&, T*> iterator;typedef Listiterator<T, const T&, const T*> const_iterator;typedef Reverse_list_iterator<T, T&, T*> reverse_list_iterator;typedef Reverse_list_iterator<T, const  T&, const  T*> const_reverse_list_iterator;//1.  List的构造//默认构造List();//传值构造List(int n, const T& value = T());//迭代器构造template <class Iterator>List(Iterator first, Iterator last);//拷贝构造List(const List<T>& l);//赋值重载List<T>& operator=(List<T> l);//析构函数~List();//2. 迭代器iterator begin() ;iterator end();const_iterator begin() const;const_iterator end() const;reverse_list_iterator rbegin();reverse_list_iterator rend();const_reverse_list_iterator rbegin() const;const_reverse_list_iterator rend() const;//3. 内容相关size_t size()const;bool empty()const;//4. 获取头尾元素T& front();const T& front()const;T& back();const T& back()const;//5. 内存修改void push_back(const T& val);void pop_back();void push_front(const T& val);void pop_front();// 在pos位置前插入值为val的节点//不存在迭代器失效iterator insert(iterator pos, const T& val);// 删除pos位置的节点，返回该节点的下一个位置//存在迭代器失效iterator erase(iterator pos);void clear();void swap(List<T>& l);private: Node* _pHead;void createhead(){_pHead = new Node;_pHead->_prev = _pHead;_pHead->_next = _pHead;}};
}

🌱4.1 List构造函数

//创造head节点
void createhead()
{_pHead = new Node;_pHead->_prev = _pHead;_pHead->_next = _pHead;
}
//默认构造
List()
{createhead();
}
//传值构造
List(int n, const T& value = T())
{createhead();for (int i = 0; i < n; ++i)push_back(value);
}
//迭代器构造
template <class Iterator>
List(Iterator first, Iterator last)
{createhead();auto start = first;while (start != last){push_back(*start);start++;};
};
//拷贝构造
List(const List<T>& l)
{createhead();for (auto e : l){push_back(e);}
};//赋值重载
List<T>& operator=(List<T> l)
{swap(_pHead, l._pHead);return *this;
}
//析构函数
~List()
{clear();delete _pHead;
}

📈备注：

默认构造支持创建空List。
传值构造支持创建长度为n，值为value的List。
迭代器构造支持通过传入迭代器进行初始化的List.
拷贝构造和赋值重载支持传入一个List进行初始化。
析构函数要先clear，这个clear就是清除所有节点的函数，后面会实现。

🌱4.2 List迭代器

一般迭代器：

typedef ListNode<T> Node;
typedef Listiterator<T, T&, T*> iterator;
typedef Listiterator<T, const T&, const T*> const_iterator;iterator begin() {return iterator(_pHead->_next);
};
iterator end()
{return iterator(_pHead);
};
const_iterator begin() const
{return const_iterator(_pHead->_next);
};
const_iterator end() const
{return const_iterator(_pHead);
};

📈备注：begin()返回头节点，end()返回尾节点的下一个节点（就是head节点）

反向迭代器：

typedef ListNode<T> Node;
typedef Reverse_list_iterator<T, T&, T*> reverse_list_iterator;
typedef Reverse_list_iterator<T, const  T&, const  T*> const_reverse_list_iterator;reverse_list_iterator rbegin(){return reverse_list_iterator(_pHead);
};
reverse_list_iterator rend()
{return reverse_list_iterator(_pHead->_next);
};
const_reverse_list_iterator rbegin() const
{return const_reverse_list_iterator(_pHead);
};
const_reverse_list_iterator rend() const
{return const_reverse_list_iterator(_pHead->_next);
};

📈备注：begin()返回头节点前一个节点（就是head节点），end()返回尾节点

🌱4.3 List内容相关函数

size_t size()const
{size_t size = 0;auto it = begin();while (it != end()){size++;it++;}return size;
}
bool empty()const
{return size() == 0;
}

📈备注：size与empty函数慎用，时间复杂度为O(n)。

🌱4.4 List获取头尾元素

T& front()
{return (_pHead->_next)->_val;
}
const T& front()const
{return (_pHead->_next)->_val;
}
T& back()
{return (_pHead->_prev)->_val;
}
const T& back()const
{return (_pHead->_prev)->_val;
}

📈备注：注意要多实现一个const版本的。

🌱4.5 List内存修改

//5. 内存修改
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());
};// 在pos位置前插入值为val的节点
//不存在迭代器失效
iterator insert(iterator pos, const T& val) {Node* tmp = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;tmp->_next = cur;tmp->_prev = prev;cur->_prev = tmp;prev->_next = tmp;return  iterator(tmp);
};// 删除pos位置的节点，返回该节点的下一个位置
//存在迭代器失效
iterator erase(iterator pos)
{Node* Prew = pos._node->_prev;Node* Next = pos._node->_next;delete pos._node;Prew->_next = Next;Next->_prev = Prew;return Next;
};void clear() { iterator start = begin();while (start != end()){start = erase(start);}_pHead->_next = _pHead;_pHead->_prev = _pHead;
}
void swap(List<T>& l)
{Node tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;
}

📈备注：insert传入的迭代器不会失效，但是erase传入的迭代器会失效，erase返回删除节点的下一个节点的有效迭代器。其他是内存修改函数都是通过复用insert与erase实现的。

由此全部完成，附上总代码图：

#pragma once
namespace bit
{//ListNode节点template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _val;ListNode(const T& val = T()) :_prev(nullptr),_next(nullptr),_val(val){};};//List的迭代器模板template<class T, class str, class ptr>struct Listiterator{typedef ListNode<T> Node;typedef Listiterator<T, str, ptr> Self;Node* _node;//迭代器的构造函数Listiterator(Node* pNode = nullptr){_node = pNode;}Listiterator(const Self& l) {_node = l._node;}//前置++重载，当前节点到下一个节点Self operator++(){_node = _node->_next;return *this;};//后置++重载，当前节点到下一个节点Self operator++(int) {Node* tmp = _node;_node = _node->_next;return tmp;};//前置--重载，当前节点到上一个节点Self operator--(){_node = _node->_prev;return *this;};//后置--重载，当前节点到上一个节点Self& operator--(int) {Node* tmp = _node;_node = _node->_prev;return tmp;};//解引用重载str operator*(){return _node->_val;};//->重载ptr operator->(){return &*this;};//!=重载bool operator!=(const Self& l) {return l._node !=_node;};//==重载bool operator==(const Self& l) {return l._node == _node;};};//反向迭代器template<class T, class str, class ptr>struct Reverse_list_iterator{typedef ListNode<T> Node;typedef Reverse_list_iterator<T, str, ptr> Self;Node* _node;//构造函数Reverse_list_iterator(Node* tmp):_node(tmp) {};//前置++重载Self operator++(){_node = _node->_prev;return *this;};//后置++重载Self operator++(int) {Node* tmp = _node;_node = _node->_prev;return tmp;};//前置--重载，Self operator--(){_node = _node->_next;return *this;};//后置--重载Self& operator--(int) {Node* tmp = _node;_node = _node->_next;return tmp;};//解引用重载str operator*(){return (_node->_prev)->_val;};//->重载ptr operator->(){return &*this;};//!=重载bool operator!=(const Self& l) {return l._node != _node;};//==重载bool operator==(const Self& l) {return l._node == _node;};};//list模板template<class T>class List{public:typedef ListNode<T> Node;//迭代器命名typedef Listiterator<T, T&, T*> iterator;typedef Listiterator<T, const T&, const T*> const_iterator;typedef Reverse_list_iterator<T, T&, T*> reverse_list_iterator;typedef Reverse_list_iterator<T, const  T&, const  T*> const_reverse_list_iterator;//1.  List的构造//默认构造List(){createhead();}//传值构造List(int n, const T& value = T()){createhead();for (int i = 0; i < n; ++i)push_back(value);}//迭代器构造template <class Iterator>List(Iterator first, Iterator last){createhead();auto start = first;while (start != last){push_back(*start);start++;};};//拷贝构造List(const List<T>& l){createhead();for (auto e : l){push_back(e);}};//赋值重载List<T>& operator=(List<T> l){swap(_pHead, l._pHead);return *this;}//析构函数~List(){clear();delete _pHead;}//2. 迭代器iterator begin() {return iterator(_pHead->_next);};iterator end(){return iterator(_pHead);};const_iterator begin() const{return const_iterator(_pHead->_next);};const_iterator end() const{return const_iterator(_pHead);};reverse_list_iterator rbegin(){return reverse_list_iterator(_pHead);};reverse_list_iterator rend(){return reverse_list_iterator(_pHead->_next);};const_reverse_list_iterator rbegin() const{return const_reverse_list_iterator(_pHead);};const_reverse_list_iterator rend() const{return const_reverse_list_iterator(_pHead->_next);};//3. 内容相关size_t size()const{size_t size = 0;auto it = begin();while (it != end()){size++;it++;}return size;}bool empty()const{return size() == 0;}//4. 获取头尾元素T& front(){return (_pHead->_next)->_val;}const T& front()const{return (_pHead->_next)->_val;}T& back(){return (_pHead->_prev)->_val;}const T& back()const{return (_pHead->_prev)->_val;}//5. 内存修改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());};// 在pos位置前插入值为val的节点//不存在迭代器失效iterator insert(iterator pos, const T& val) {Node* tmp = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;tmp->_next = cur;tmp->_prev = prev;cur->_prev = tmp;prev->_next = tmp;return  iterator(tmp);};// 删除pos位置的节点，返回该节点的下一个位置//存在迭代器失效iterator erase(iterator pos){Node* Prew = pos._node->_prev;Node* Next = pos._node->_next;delete pos._node;Prew->_next = Next;Next->_prev = Prew;return Next;};void clear() { iterator start = begin();while (start != end()){start = erase(start);}_pHead->_next = _pHead;_pHead->_prev = _pHead;}void swap(List<T>& l){Node tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;}private: Node* _pHead;void createhead(){_pHead = new Node;_pHead->_prev = _pHead;_pHead->_next = _pHead;}};
}

本文就到这里，感谢你看到这里❤️❤️！
我知道一些人看文章喜欢静静看，不评论🤔，但是他会点赞😍，这样的人，帅气低调有内涵😎，美丽大方很优雅😊，明人不说暗话，要你手上的一个点赞😘！