本篇将对 list 类的常用函数进行模拟。其中主要要点为函数的模拟，另外还会对函数的功能和返回值进行讲解。但 list 可以说是 string vector stack queue …… STL 库中最难实现一个类，因为 list 的迭代器不是很好实现，所以本篇一个很重要的一个点便是 list 的迭代器。不仅仅实现了 list 的迭代器，还实现了 list 中常用的函数。
list 类的底层为双向循环链表，实现的时候对于双向循环链表介绍的也不是很详细，若想详细的了解双向循环链表，可阅读这篇文章：链表/双向循环链表（C/C++）-CSDN博客
目录如下：
目录
1. list 的架构
list 类中主要结构为循环双向链表，所以结点为指针包括 next 和 prev。
list 类主要实现的为一个链表类，所以 list 中的元素即为结点，所以另外我们还需要一个结构体用来充当 list 中的结点，然后 list 中的元素就是维护结点的指针。不仅仅需要一个结构体充当结点，倘若我们只使用指针来表征迭代器，那么想要通过迭代器来访问结点中存储的内容的时候，并不能像使用 *iterator 来访问结点内容，所以我们也还需要一个类来表征迭代器，然后对于迭代器的实现，主要还是使用一个结点指针来实现，但是不同的是，我们会在迭代器类中实现运算符重载，以达到像使用 *iterator 来访问结点内容。
主要的框架如下：
namespace MyList { template <class T> struct ListNode { ListNode* _next; ListNode* _prev; T _data; // 结点的构造函数 ListNode(const T& data) :_next(nullptr) , _prev(nullptr) , _data(data) {} }; // 迭代器类 template <class T> struct ListIterator { public: typedef ListNode<T> node; typedef ListIterator<T> iterator; //...迭代器运算符重载内容 node* _node; }; template <class T> class list { public: typedef ListNode<T> node; typedef ListIterator<T> iterator; // ...内容 private: node* _head; size_t _size; }; }我们将根据以上框架实现 list 类。
2. list 的实现
2.1 pop and push
本篇中首先实现的为 list 中的 pop_back pop_front push_back push_front 这4个函数，对于这四个函数的作用分别为删除最后一个元素，删除第一个元素，尾插一个元素，头插一个元素。我们先实现 pop 函数，如下：
void pop_back() { node* tail = _head->_prev; node* tail_prev = tail->_prev; _head->_prev = tail_prev; tail_prev->_next = _head; delete tail; tail = nullptr; _size--; /*erase(--end());*/ } void pop_front() { node* cur = _head->_next; node* next = cur->_next; _head->_next = next; next->_prev = _head; delete cur; _size--; /*erase(begin());*/ }以上删除的操作，其中的重点为熟悉双向循环链表的指向，删除一个元素，需要将前一个元素的指针的 next 指向下一个元素，将下一个元素的 prev 指向指向前一个，然后将当前指针删除。
接下来实现 push 函数，对于 push 函数的实现，其中主要的要点还是需要熟悉一个新节点的插入，将最后一个结点的 next 指针指向新节点，将新节点的 next 指针指向头结点，将头结点的 prev 指针指向新节点，然后将新节点的 prev 指针指向最后一个结点，这样新结点就成了最后一个结点，对于头插也是一样的道理，只是实现的时候，我们需要注意其中的细节。具体的实现如下：
void push_back(const T& data) { 先new出一个结点 node* newnode = new node(data); // 找到尾结点，新结点的prev指向尾结点，新结点的next指向头结点 node* tail = _head->_prev; newnode->_prev = tail; tail->_next = newnode; newnode->_next = _head; _head->_prev = newnode; _size++; /*insert(end(), data);*/ } void push_front(const T& data) { node* newnode = new node(data); node* cur = _head->_next; _head->_next = newnode; newnode->_prev = _head; newnode->_next = cur; cur->_prev = newnode; _size++; /*insert(begin(), data);*/ }
2.2 swap、empty、and size
接下来我们将实现 swap empty size 函数，对于这几个函数来说，实现的逻辑也相对简单，实现的逻辑如下：
void swap(list& ls) { std::swap(_head, ls._head); std::swap(_size, ls._size); // 换一种写法 } size_t size() const { return _size; } bool empty() { return _head == _head->_next; }对于以上的代码，swap 的实现，只需要调用 std 中的 swap 函数即可，因为本身对于 list 的维护就是使用一个指针和一个 size，所以只需要交换即可。对于 empty 的实现，只需要判断哨兵位是否指向自己。
2.3 iterator、insert、erase
从这段开始，我们将开始实现我们的迭代器，为什么要等到这段才实现 insert 和 erase 函数呢？因为这两个函数的参数都包括迭代器，所以我们需要先实现迭代器。对于迭代器的实现，其主要还是实现我们常使用的迭代器操作，比如对迭代器 ++ 指向下一个元素、对迭代器 -- 、指向前一个元素，迭代之间的比较 == != 判断是否要继续迭代下去，这些都需要使用运算符重载来实现，具体的实现方式如下：
// 迭代器类 template <class T> struct ListIterator { public: typedef ListNode<T> node; typedef ListIterator<T> iterator; //...迭代器运算符重载内容 ListIterator(node* n) :_node(n) {} ~ListIterator() { _node = nullptr; } // 无内置参数，表示前置++ iterator& operator++() { _node = _node->_next; return *this; } // 有内置参数，后置++,返回拷贝的值，不能返回引用，tmp只是一个临时变量，会被析构 iterator operator++(int) { iterator tmp(_node); _node = _node->_next; return tmp; } iterator& operator--() { _node = _node->_prev; return *this; } iterator operator--(int) { iterator tmp(_node); _node = _node->_prev; return tmp; } bool operator!=(const iterator& it) { return _node != it._node; } bool operator==(const iterator& it) { return _node == it._node; } T& operator*() { return _node->_data; } // it->->data T* operator->() { return &_node->_data; } node* _node; };如上，当我们实现 -- 的时候，就是返回当前位置的前一个指针，不过需要注意是前置 -- 还是后置 --，返回的值不一样，对于前置 ++ 和后置 ++ 也一样。然后是 == 与 != 我们同样也只需要返回结点指针的 == 和 != 的 bool 值，对于以上的解引用，我们只需要返回当前指针指向元素的引用即可。除了这些，我们还发现存在一个特殊的运算符重载：T* operator->() ，这个我们返回的为指针指向结点内容的地址，对于这个的使用如下：
struct A { int _a1; int _a2; A(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} }; void Test02() { MyList::list<A> ls; ls.push_back({ 1,2 }); ls.push_back({ 3,4 }); ls.push_back({ 5,6 }); ls.push_back({ 7,8 }); ls.push_back({ 9,10 }); auto it = ls.begin(); while (it != ls.end()) { cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl; cout << it->_a1 << " " << it->_a2 << endl; ++it; } }当我们在 list 中插入的元素中是一个包含多个元素的结构体的时候，这时候使用 *iterator 就不管用了，所以我们需要返回这个结构体的地址，然后在分别遍历，如上，但是按道理来说我们应该在运算符重载那里写两个 -> 但编译器为了加强可读性，将两个箭头优化为了一个。
有了以上的迭代器，我们就可以开始实现我们的 insert 函数和 erase 函数了，对于 insert 函数来说，函数的功能为在指定位置前插入元素，返回值为新插入元素的位置，实现如下：
iterator insert(iterator pos, const T& data) { // 在pos位置之前插入元素 node* cur = pos._node; node* prev = cur->_prev; node* newnode = new node(data); cur->_prev = newnode; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; _size++; return newnode; }对于 erase 函数来说，其主要功能为删除指定位置的元素，然后返回刚删除位置的下一个元素，实现原理如下：
iterator erase(iterator pos) { node* cur = pos._node; node* next = cur->_next; node* prev = cur->_prev; prev->_next = next; next->_prev = prev; delete cur; _size--; return next; }实现以上后，我们还需要在 list 类中实现 begin 和 end 函数，实现如下：
iterator end() { iterator tmp(_head); return tmp; } iterator begin() { iterator tmp(_head->_next); return tmp; }
2.4 const_iterator
对于迭代器而言，以上我们只实现了普通的迭代器，但是当我们遇见被 const 修饰的 list 类的时候，我们还是需要使用 const_iterator，而对于 const_iterator 而言，我们希望的为不希望被 const 修饰的 list 类中的内容不被修改，所以我们可以在实现的时候，相对于普通迭代器只需要将 T& operator*() 和 T* operator->() 用 const 修饰即可，所以得出的 const 迭代器，如下：
template <class T> struct ListConstIterator { public: typedef ListNode<T> node; typedef ListConstIterator<T> const_iterator; // 实现iterator的各种操作 前置++、--，后置++、--，==、!= // 对迭代器进行构造、构造函数 ListConstIterator(node* n) :_node(n) {} ~ListConstIterator() { _node = nullptr; } // 无内置参数，表示前置++ const_iterator& operator++() { _node = _node->_next; return *this; } // 有内置参数，后置++,返回拷贝的值，不能返回引用，tmp只是一个临时变量，会被析构 const_iterator operator++(int) { const_iterator tmp(_node); _node = _node->_next; return tmp; } const_iterator& operator--() { _node = _node->_prev; return *this; } const_iterator operator--(int) { const_iterator tmp(_node); _node = _node->_prev; return tmp; } bool operator!=(const const_iterator& it) { return _node != it._node; } bool operator==(const const_iterator& it) { return _node == it._node; } const T& operator*() const{ return _node->_data; } // it->->data const T* operator->() const{ return &_node->_data; } node* _node; };
2.5 模板 iterator
对于以上两个迭代器而言，我们发现这两个迭代器存在很大的冗余，其中只有两个函数不一样，那么我们是否可以将其封装为一个模板呢？答案是可以的，我们可以将传引用和传地址的部分封装为一个模板参数，然后在 list 类中，将 T T& T* 和 T const T& const T* 分别传进去，实现如下：
template <class T, class Ref, class Ptr> struct ListIterator { public: typedef ListNode<T> node; typedef ListIterator<T, Ref, Ptr> iterator; // 实现iterator的各种操作 前置++、--，后置++、--，==、!= // 对迭代器进行构造、构造函数 ListIterator(node* n) :_node(n) {} // 未开空间的类，有无析构都无所谓 ~ListIterator() { _node = nullptr; } // 无内置参数，表示前置++ iterator& operator++() { _node = _node->_next; return *this; } // 有内置参数，后置++,返回拷贝的值，不能返回引用，tmp只是一个临时变量，会被析构 iterator operator++(int) { iterator tmp(_node); _node = _node->_next; return tmp; } iterator& operator--() { _node = _node->_prev; return *this; } iterator operator--(int) { iterator tmp(_node); _node = _node->_prev; return tmp; } bool operator!=(const iterator& it) { return _node != it._node; } bool operator==(const iterator& it) { return _node == it._node; } Ref operator*() { return _node->_data; } // it->->data Ptr operator->() { return &_node->_data; } node* _node; };我们在 list 类中使用该模板迭代器的形式如下：
2.6 默认成员函数
最后我们在来实现我们的默认成员函数：构造、拷贝构造、赋值运算符重载、析构函数。首先我们先实现我们的构造和拷贝构造函数，使用构造只需要将我们的哨兵位的结点初始化即可，因为是双向循环链表，两个指针都指向指向自己。对于拷贝构造函数而言，我们实现的时候，同样也需要提前将哨兵位的结点空间开辟出来，然后使用范围 for 将每个元素尾插进入新的链表，实现如下：
// 构造和拷贝构造功能相重叠的部分 void empty_init() { _head = new node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } list() { empty_init(); } // 拷贝构造函数 list(const list& ls) { empty_init(); for (auto e : ls) { push_back(e); } }接着实现赋值运算符重载，对于赋值运算符重载函数而言，和拷贝构造类似，我们只需要在参数位置将传入的 list 拷贝构造，然后调用 swap 函数，交换参数的值即可，实现如下：
list& operator=(list ls) { swap(ls); return *this; }最后则是我们的析构函数，对于析构函数而言，就是需要将所有的结点都释放掉，包括哨兵位，其实这个和 clear 函数的功能相重叠，只不过 clear 函数不需要将哨兵位给释放掉，所以我们只需要先实现 clear 函数，然后调用 clear 函数，在使用哨兵位，就可以实现析构函数，实现如下：
void clear() { auto it = begin(); while (it != end()) { it = erase(it); } } ~list() { clear(); delete _head; _head = nullptr; }至此，本篇实现的函数便完结了。
3. all code
namespace MyList {
template <class T>
struct ListNode {
ListNode* _next;
ListNode* _prev;
T _data;
// 结点的构造函数
ListNode(const T& data)
:_next(nullptr)
, _prev(nullptr)
, _data(data)
{}
};
template <class T, class Ref, class Ptr>
struct ListIterator {
public:
typedef ListNode<T> node;
typedef ListIterator<T, Ref, Ptr> iterator;
// 实现iterator的各种操作 前置++、--，后置++、--，==、!=
// 对迭代器进行构造、构造函数
ListIterator(node* n)
:_node(n)
{}
// 未开空间的类，有无析构都无所谓
~ListIterator() {
_node = nullptr;
}
// 无内置参数，表示前置++
iterator& operator++() {
_node = _node->_next;
return *this;
}
// 有内置参数，后置++,返回拷贝的值，不能返回引用，tmp只是一个临时变量，会被析构
iterator operator++(int) {
iterator tmp(_node);
_node = _node->_next;
return tmp;
}
iterator& operator--() {
_node = _node->_prev;
return *this;
}
iterator operator--(int) {
iterator tmp(_node);
_node = _node->_prev;
return tmp;
}
bool operator!=(const iterator& it) {
return _node != it._node;
}
bool operator==(const iterator& it) {
return _node == it._node;
}
Ref operator*() {
return _node->_data;
}
// it->->data
Ptr operator->() {
return &_node->_data;
}
node* _node;
};
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;
// ...内容
// 构造和拷贝构造功能相重叠的部分
void empty_init() {
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list() {
empty_init();
}
// 拷贝构造函数
list(const list& ls) {
empty_init();
for (auto e : ls) {
push_back(e);
}
}
~list() {
clear();
delete _head;
_head = nullptr;
}
void pop_back() {
node* tail = _head->_prev;
node* tail_prev = tail->_prev;
_head->_prev = tail_prev;
tail_prev->_next = _head;
delete tail;
tail = nullptr;
_size--;
/*erase(--end());*/
}
void clear() {
auto it = begin();
while (it != end()) {
it = erase(it);
}
}
void pop_front() {
node* cur = _head->_next;
node* next = cur->_next;
_head->_next = next;
next->_prev = _head;
delete cur;
_size--;
/*erase(begin());*/
}
void push_back(const T& data) {
先new出一个结点
node* newnode = new node(data);
// 找到尾结点，新结点的prev指向尾结点，新结点的next指向头结点
node* tail = _head->_prev;
newnode->_prev = tail;
tail->_next = newnode;
newnode->_next = _head;
_head->_prev = newnode;
_size++;
/*insert(end(), data);*/
}
void push_front(const T& data) {
node* newnode = new node(data);
node* cur = _head->_next;
_head->_next = newnode;
newnode->_prev = _head;
newnode->_next = cur;
cur->_prev = newnode;
_size++;
/*insert(begin(), data);*/
}
void swap(list& ls) {
std::swap(_head, ls._head);
std::swap(_size, ls._size);
// 换一种写法
}
size_t size() const {
return _size;
}
bool empty() {
return _head == _head->_next;
}
iterator insert(iterator pos, const T& data) {
// 在pos位置之前插入元素
node* cur = pos._node;
node* prev = cur->_prev;
node* newnode = new node(data);
cur->_prev = newnode;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
_size++;
return newnode;
}
iterator erase(iterator pos) {
node* cur = pos._node;
node* next = cur->_next;
node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return next;
}
iterator end() {
iterator tmp(_head);
return tmp;
}
iterator begin() {
iterator tmp(_head->_next);
return tmp;
}
private:
node* _head;
size_t _size;
};
}
