文章目录
大家好！本文会用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;
};
//->重载sh
ptr 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;
}
};
}
本文就到这里，感谢你看到这里❤️❤️！
我知道一些人看文章喜欢静静看，不评论🤔，但是他会点赞😍，这样的人，帅气低调有内涵😎，美丽大方很优雅😊，明人不说暗话，要你手上的一个点赞😘！
