大家好啊，今天给大家带来的是我们C++编程中，stl库里的重要角色--list的简单的模拟实现，希望通过这篇小博客，对大家更加深入理解list容器有所帮助。
前言：
在C++标准库中，list是一种双向链表容器。
这里简单提一下双向链表——什么是双向链表呢？
双向链表是一种链式数据结构，其中每个节点包含三个部分：
- 一个存储数据的字段。（我们通常用_data表示）
- 一个指向前驱节点的指针。（我们通常用_prev表示）
- 一个指向后继节点的指针。（我们通常用_next表示）
这样，每个节点都知道它的前一个节点和后一个节点，从而支持在常数时间内进行插入和删除操作。
一：节点结构的定义
在实现list之前，我们要先定义一下这个链表的节点结构。一个链表是有多个节点链接组成，所以节点自然是重中之重。
我们在头文件定义一下节点结构，上文讲到，一个节点包括_data、_prev、_next三个部分：
template <class T>
struct ListNode
{
ListNode(const T& data = T())//给的缺省值是我们想要存储的数据类型的一个匿名对象（自定义类型需要构造函数）
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{
}
T _data;
ListNode<T>* _next;//指向下一个节点
ListNode<T>* _prev;//指向上一个节点
};当然，也要记得写这个模板类的默认构造，我们用想存储的数据的一个匿名对象来完成对_data的初始化。
二、list类的默认构造，成员变量
我们用_count来记录链表的节点数目，_head记录双向带头链表的头节点。
为了简写代码，方便我们操作，我们顺便把ListNode<T>重命名为Node。
随后书写list的默认构造函数，就是赋予头节点空间，将头节点的_prev与_next指向自己，还有把_count初始化为0。
template<class T>
class list
{
typedef ListNode<T> Node;
public:
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_count = 0;
}
private:
Node* _head;
size_t _count;
};三、list：用类实现迭代器的思想
在实现我们list的各种接口之前，我们首先要来实现一下list容器的迭代器。
这属于是list内容的重中之重，不同于vector，我们返回一个指针作为迭代器，指针的++就可以让迭代器向后移动到另一个元素。我们的list是由许多个节点链接而成，又怎么可以使用各种++操作符呢？
在这个基础上，我们想到了，可以是先用一个类，在这个类中重载各种++，--运算符，手动实现迭代器的向后移动（向前移动）。
那我们又如何实现const的迭代器呢？难不成学vector在前面加个const就可以了吗？
显而易见，由于底层结构的不同，const迭代器的实现原理也有所不同。
其实很简单，要想实现const迭代器的作用，我们只需要在迭代器类的各种内置函数的返回参数的类型做手脚就行。函数返回类型变成了const，自然就是const迭代器的作用。这样的代价就是我们要写两个迭代器模板。
但为了减少我们的麻烦，我们可以在写迭代器的时候在tmplete后面多加几个类型参数就行，这样就把我们的麻烦当做礼物送给了编译器（编译器：听我说，谢谢你）。
template<class T,class Ref,class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;//节点类型
typedef ListIterator<T, Ref, Ptr> Self;//代表自己这个类型
Node _node;
ListIterator(Node node = nullptr)//缺省为nullptr的默认构造函数
:_node(node)
{
}
ListIterator(const Self& l)//传一个迭代器类型（在实现后置++，后置--可以用得到)
:_node(l._node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;//Ptr是指针类型，模拟实现->时应该返回的是地址，即返回一个指向当前值的指针
}
Self& operator++()//前置++
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _node != l._node;
}
bool operator==(const Self& l)
{
return _node == l._node;
}
};四、反向迭代器的实现
与我们刚刚实现正向迭代器一样的思想，反向迭代器也需要用模板类的思想来解决。
在实现反向迭代器的时候，我们核心仍然通过正向迭代器去运转，只不过在反向迭代器类中再次重载了各种操作符。例如，反向迭代器的前置++，我们只需要在实现的时候，在函数内调用正向迭代器的前置--就行。
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef typedef Reverse_iterator Self;
Iterator _it;
Reverse_iterator(Iterator it)
:_it(it)
{
}
Ref operator*()//因为反向迭代器的首位置是由正向迭代器的end（）初始化的，在最后一个元素的下一个位置，
// 解引用时要先创建一个临时变量，使其向前移动一步，才是正确的返回位置（避免改变反向迭代器位置）
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
Iterator tmp = _it;
--tmp;
return &(*tmp);
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& l)
{
return _it != l._it;
}
bool operator==(const Self& l)
{
return _it == l._it;
}
};五、list迭代接口的实现
终于把list的迭代器给实现了，紧接着，我们就应该在list类里实现迭代器的各种接口。
先来重命名迭代器：
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator,const T&,const T*> const_reverse_iterator;大家请看上面四行代码，我们通过传递的不同类型的参数类型，实例化出四种不同的迭代器，我们想使用const迭代器时就在重命名const_iterator时传递const T&，const T*就行。
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
iterator end()
{
return iterator(_head);
}
const_iterator end()const
{
return const_iterator(_head);
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}六、list插入函数以及删除函数的实现
list的插入主要是push_back,insert，push_front三个函数，删除操作主要是pop_back(),erase，pop_front三个函数。
//不涉及释放空间，不存在迭代器失效
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
_count++;
return iterator(newnode);//返回由Node类型的newnode初始化完成的匿名对象
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)//存在迭代器失效
{
assert(pos != end());//防止把头节点给删了
Node* node = pos._node;
Node* pnext = node->_next;
Node* prev = node->_prev;
prev->_next = pnext;
pnext->_prev = prev;
delete node;
_count--;
return iterator(pnext);
}
随后，我们就可以让push_back()和push_front调用insert函数实现复用，让pop_back()和pop_front调用erase实现复用，减少我们所需要写的代码：
void push_back(const T& data))
{
insert(end(), data);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& data))
{
insert(begin(), data);
}
void pop_front()
{
erase(begin());
}七、list各种默认函数的实现
我们需要实现各种其他构造函数，方便list类的各种构造，例如(int n, const T& value = T())//传n个元素，每个元素默认为T()，又或者是根据迭代器区间默认构造。
我们不难想到，由于要实现这么多的构造函数，这么多的构造函数，如果在构造前都要现在函数里初始化一遍，破坏了封装性，所以我们可以把初始化这个功能写成一个新的函数，随后，在各种构造函数里调用就行：
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_count = 0;
}
list()//更改默认构造函数
{
empty_init();
}各种构造函数实现：
list(int n, const T& value = T())
{
empty_init();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
template <class Iterator>//适应各个迭代器的构造
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)//拷贝构造
{
empty_init();
for (const auto& it : l)
{
push_back(it);
}
}
list<T>& operator=(const list<T> l)//赋值重载
{
swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
当然，在赋值重载中，我们仍然选择了现代写法，于是我们就要实现一个swap接口，在析构函数中，我们也选择用一个clear来删除除了头结点之外的所有节点，所以我们也需要实现一个clear：
void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_count, l._count);
}
void clear(list<T>& l)
{
auto it = begin();
while (it != end())
{
it = erase(it);//小心迭代器失效
}
}
八、其他接口的实现：
我们想要看这个链表多长，就需要调用我们的size接口，想知道最后或者第一个元素的值，也需要调用back()，front()等接口。
以下是该接口的实现：
T& front()
{
assert(_count > 0);
return _head->_next->_data;
}
const T& front()const
{
assert(_count > 0);
return _head->_next->_data;
}
T& back()
{
assert(_count > 0);
return _head->_prev->_data;
}
const T& back()const
{
assert(_count > 0);
return _head->_prev->_data;
}
void push_back(const T& data)
{
insert(end(), data);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& data)
{
insert(begin(), data);
}
void pop_front()
{
erase(begin());
}九、总代码
#pragma once
#include<assert.h>
namespace bit
{
template <class T>
struct ListNode
{
ListNode(const T& data = T())//给的缺省值是我们想要存储的数据类型的一个匿名对象（自定义类型需要构造函数）
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{
}
T _data;
ListNode<T>* _next;//指向下一个节点
ListNode<T>* _prev;//指向上一个节点
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T>* Node;//节点类型
typedef ListIterator<T, Ref, Ptr> Self;//代表自己这个类型
Node _node;
ListIterator(Node node = nullptr)//缺省为nullptr的默认构造函数
:_node(node)
{
}
ListIterator(const Self& l)//传一个迭代器类型（在实现后置++，后置--可以用得到)
:_node(l._node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;//Ptr是指针类型，模拟实现->时应该返回的是地址，即返回一个指向当前值的指针
}
Self& operator++()//前置++
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _node != l._node;
}
bool operator==(const Self& l)
{
return _node == l._node;
}
};
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator Self;
Iterator _it;
Reverse_iterator(Iterator it)
:_it(it)
{
}
Ref operator*()//因为反向迭代器的首位置是由正向迭代器的end（）初始化的，在最后一个元素的下一个位置，
// 解引用时要先创建一个临时变量，使其向前移动一步，才是正确的返回位置（避免改变反向迭代器位置）
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
Iterator tmp = _it;
--tmp;
return &(*tmp);
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& l)
{
return _it != l._it;
}
bool operator==(const Self& l)
{
return _it == l._it;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_count = 0;
}
list()
{
empty_init();
}
list(int n, const T& value = T())
{
empty_init();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
template <class Iterator>//适应各个迭代器的构造
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)//拷贝构造
{
empty_init();
for (const auto& it : l)
{
push_back(it);
}
}
list<T>& operator=(const list<T> l)//赋值重载
{
swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
iterator end()
{
return iterator(_head);
}
const_iterator end()const
{
return const_iterator(_head);
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}
size_t size()const
{
return _count;
}
bool empty()const
{
return _count == 0;
}
T& front()
{
assert(_count > 0);
return _head->_next->_data;
}
const T& front()const
{
assert(_count > 0);
return _head->_next->_data;
}
T& back()
{
assert(_count > 0);
return _head->_prev->_data;
}
const T& back()const
{
assert(_count > 0);
return _head->_prev->_data;
}
void push_back(const T& data)
{
insert(end(), data);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& data)
{
insert(begin(), data);
}
void pop_front()
{
erase(begin());
}
//不涉及释放空间，不存在迭代器失效
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
_count++;
return iterator(newnode);//返回由Node类型的newnode初始化完成的匿名对象
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)//存在迭代器失效
{
assert(pos != end());//防止把头节点给删了
Node* node = pos._node;
Node* pnext = node->_next;
Node* prev = node->_prev;
prev->_next = pnext;
pnext->_prev = prev;
delete node;
_count--;
return iterator(pnext);
}
void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_count, l._count);
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
private:
Node* _head;
size_t _count;
};
}#pragma once
#include<assert.h>
namespace bit
{
template <class T>
struct ListNode
{
ListNode(const T& data = T())//给的缺省值是我们想要存储的数据类型的一个匿名对象（自定义类型需要构造函数）
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{
}
T _data;
ListNode<T>* _next;//指向下一个节点
ListNode<T>* _prev;//指向上一个节点
};
template<class T, class Ref, class Ptr>
struct ListIterator
{
typedef ListNode<T>* Node;//节点类型
typedef ListIterator<T, Ref, Ptr> Self;//代表自己这个类型
Node _node;
ListIterator(Node node = nullptr)//缺省为nullptr的默认构造函数
:_node(node)
{
}
ListIterator(const Self& l)//传一个迭代器类型（在实现后置++，后置--可以用得到)
:_node(l._node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;//Ptr是指针类型，模拟实现->时应该返回的是地址，即返回一个指向当前值的指针
}
Self& operator++()//前置++
{
_node = _node->_next;
return *this;
}
Self operator++(int)//后置++
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& l)
{
return _node != l._node;
}
bool operator==(const Self& l)
{
return _node == l._node;
}
};
template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
typedef Reverse_iterator Self;
Iterator _it;
Reverse_iterator(Iterator it)
:_it(it)
{
}
Ref operator*()//因为反向迭代器的首位置是由正向迭代器的end（）初始化的，在最后一个元素的下一个位置，
// 解引用时要先创建一个临时变量，使其向前移动一步，才是正确的返回位置（避免改变反向迭代器位置）
{
Iterator tmp = _it;
return *(--tmp);
}
Ptr operator->()
{
Iterator tmp = _it;
--tmp;
return &(*tmp);
}
Self& operator++()
{
--_it;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}
Self& operator--()
{
++_it;
return *this;
}
Self operator--(int)
{
Self tmp(*this);
++_it;
return tmp;
}
bool operator!=(const Self& l)
{
return _it != l._it;
}
bool operator==(const Self& l)
{
return _it == l._it;
}
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
_count = 0;
}
list()
{
empty_init();
}
list(int n, const T& value = T())
{
empty_init();
for (int i = 0; i < n; ++i)
{
push_back(value);
}
}
template <class Iterator>//适应各个迭代器的构造
list(Iterator first, Iterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& l)//拷贝构造
{
empty_init();
for (const auto& it : l)
{
push_back(it);
}
}
list<T>& operator=(const list<T> l)//赋值重载
{
swap(l);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin()const
{
return const_iterator(_head->_next);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin()const
{
return const_reverse_iterator(end());
}
iterator end()
{
return iterator(_head);
}
const_iterator end()const
{
return const_iterator(_head);
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rend()const
{
return const_reverse_iterator(begin());
}
size_t size()const
{
return _count;
}
bool empty()const
{
return _count == 0;
}
T& front()
{
assert(_count > 0);
return _head->_next->_data;
}
const T& front()const
{
assert(_count > 0);
return _head->_next->_data;
}
T& back()
{
assert(_count > 0);
return _head->_prev->_data;
}
const T& back()const
{
assert(_count > 0);
return _head->_prev->_data;
}
void push_back(const T& data)
{
insert(end(), data);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& data)
{
insert(begin(), data);
}
void pop_front()
{
erase(begin());
}
//不涉及释放空间，不存在迭代器失效
// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
prev->_next = newnode;
_count++;
return iterator(newnode);//返回由Node类型的newnode初始化完成的匿名对象
}
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)//存在迭代器失效
{
assert(pos != end());//防止把头节点给删了
Node* node = pos._node;
Node* pnext = node->_next;
Node* prev = node->_prev;
prev->_next = pnext;
pnext->_prev = prev;
delete node;
_count--;
return iterator(pnext);
}
void swap(list<T>& l)
{
std::swap(_head, l._head);
std::swap(_count, l._count);
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
private:
Node* _head;
size_t _count;
};
}
十、总结：
本文实现了一个简化版的双向链表模板类 list，主要包括以下内容：
-
ListNode 结构体：
- 表示链表的节点，包含数据
_data和指向前一个节点_prev、后一个节点_next的指针。
- 表示链表的节点，包含数据
-
ListIterator 结构体：
- 实现了链表的迭代器，支持前向和后向遍历，以及解引用操作符
*和箭头操作符->。
- 实现了链表的迭代器，支持前向和后向遍历，以及解引用操作符
-
list 类：
- 使用
ListNode实现了双向链表的基本操作，包括插入、删除、遍历等功能。 - 提供了正向迭代器
iterator和反向迭代器reverse_iterator。
- 使用
-
功能实现：
- 支持构造函数、拷贝构造函数和赋值运算符重载。
- 实现了
begin()、end()、rbegin()、rend()等方法，用于迭代器的初始化和操作。 - 提供了
push_back()、pop_back()、push_front()、pop_front()等方法，支持双向链表的节点插入和删除。 - 包含
size()、empty()、front()和back()等方法，用于获取链表大小和访问首尾元素。
通过这些实现，希望大家可以更加深入理解了双向链表的底层实现原理，并且掌握如何使用迭代器来操作链表元素等方法。
![[oeasy]python021_赛博宝剑铭文大赏_宝剑上的铭文_特殊符号和宝物](https://img-blog.csdnimg.cn/img_convert/dabde68b1f0ee4c4cff6a0a199be53d8.png)
