如何将模拟实现的简单list改写为长尾词？

本文共计3685个文字，预计阅读时间需要15分钟。

这篇博客主要介绍如何使用模板实现list的模拟。什么是list：list是一种有序容器，可以在任意位置插入和删除元素，并支持前后双向遍历。list的底层是双向链表结构。

这篇博客主要是关于使用模板实现list的模拟。

什么是list：

1. list是一种序列式容器，可以在常数时间内在任意位置进行插入和删除操作，并且支持前后双向迭代。

list的底层是双向链表结构，每个元素存储在独立的节点中，节点通过指针指向前一个元素和后一个元素。 list与forward_list非常相似，最主要的区别在于forward_list是单链表，只能进行向前迭代，因此更简单高效。 与其他序列式容器（如array、vector、deque）相比，list通常在任意位置插入和删除元素的效率更高。 然而，与其他序列式容器相比，list和forward_list的最大缺点是不支持任意位置的随机访问。要访问list的第六个元素，必须从已知位置（如头部或尾部）迭代到该位置，这需要线性的时间开销。此外，list还需要额外的空间来保存每个节点的相关信息，对于存储较小元素的大list来说，这可能是一个重要的因素。

list实际上就是链表，只不过list底层实现的是一个双向带头循环链表。

下面开始模拟实现：

模拟实现list：

首先，我们需要定义链表节点的类。

链表节点类：

template<class T> struct list_node { T _data; // 节点储存的信息 list_node* _next; // 指向下一个节点的指针 list_node* _prev; // 指向上一个节点的指针 };

下面是链表的类：

template<class T> class list { private: list_node<T>* _head; };

默认构造函数（不带参数）

list的官方默认构造函数有四种实现方式，但是由于我还没有学习内存池，所以暂时只能模拟实现其中的两种。首先，当一个链表实例化之后，肯定存在一个节点，即哨兵卫。因此，我们的不带参数的默认构造函数只需要创建一个指向自己的哨兵卫即可。

void empty_head() { _head = new list_node<T>; _head->_data = T(); _head->_next = _head; _head->_prev = _head; } list() { empty_head(); }

至于带参数的默认构造函数，我会在下面实现。这里就先不实现了。

push_back函数

一个很简单的尾插函数，实现逻辑很简单，首先创建一个装有目标值的新节点，然后找到链表的尾（头节点的_prev）将其链表上即可。

Node* buyNode(const T& x) { Node* newnode = new Node; //这里的Node*也即是list_node的指针，只是我将list_node重命名了而已。 newnode->_data = x; newnode->_next = nullptr; newnode->_prev = nullptr; }//创建一个新节点，其中它的next，和prev指向为空

void push_back(const T& x)//将一个x，尾插到链表中去 { //第一步创建一个新节点 Node* tmp = buyNode(x); Node* tail = _head->_prev;//找到原先的尾节点。 tail->_next = tmp; tmp->_prev = tail; tmp->_next = _head;//因为现在的tmp是新的尾节点 _head->_prev = tmp;//理由如上 }

虽然现在实现了这个函数，但是如果不将迭代器完成的话，我们也不知道这个链表是否正确（不使用调式）。所以下面我们就来实现迭代器。

正向迭代器的实现

首先原生指针肯定是无法使用了，如果我们使用原生指针也就是Node*来表示迭代器的话，那么解引用这个Node得到的就是一个整体的节点，但是我们需要的只是节点里面的_data。并且因为链表里面每一个节点都不是连续的，所以如果使用原生指针直接++/--是无法得到下一个/上一个节点的。所以和vector的反向迭代器一样，我们需要写一个类来模拟指针。这个类也就是迭代器。

template<class T, class ptr, class ref>//这里使用三个模板参数也是为了让const和非const迭代器 //能直接使用一个模板就能够实例完成，而不用完成两个模板类 struct __iterator { typedef __iterator<T, ptr, ref> Self; typedef list_node<T> Node;//这两个都是重命名，便于写 Node* _point; __iterator(Node* x) :_point(x) {}//当创建完成之后就使用Node*来初始化_point //下面就是指针的一些引用了 Self operator++()//重载前置++ { _point = _point->_next; return *this; } Self operator--()//重载前置-- { _point = _point->_prev; return *this; } Self operator++(int)//重载后置++ { Self tmp(_point); _point = _point->_next; return tmp; } Self operator--(int)//重载后置-- { Self tmp(_point); _point = _point->_prev; return tmp; } //下面就是*和->也是const迭代器和非const迭代器唯一的区别 ref operator*()//非const迭代器返回的是&所以可以通过迭代器改变指针指向的值 //而const迭代器为const T&不能通过指针改变指针指向的值 { return _point->_data; } ptr operator->() //这里也是一样的 { return &(_point->_data); } Self operator+(size_t n)//不改变自身 { Node* tmp = _point; for (int i = 0; i < n; i++) { tmp = tmp->_next; } return tmp; } Self operator-(size_t n)//不改变自身 { Node* tmp = _point; for (int i = 0; i < n; i++) { tmp = tmp->_prev; } return tmp; } Self operator-=(size_t n)//要改变自身 { for (int i = 0; i < n; i++) { _point = _point->_prev; } return _point; } Self operator+=(size_t n)//要改变自身 { for (int i = 0; i < n; i++) { _point = _point->_next; } return *this; } bool operator==(const Self& b) { return _point == b._point; }//判断两个迭代器是否相等判断的也就是节点的指针是否相等 bool operator!=(const Self& b) { return _point != b._point; } };//由此就完成了正向迭代器

当然在lsit的类中我们也要增加一些函数

typedef __iterator<T, T*, T&> iterator;//将上面的类实例化的非const迭代器重命名为iterator typedef __iterator<T, const T*, const T&> const_iterator;//将const迭代器重命名为const_iterator iterator begin()//返回的是开始的节点 { return _head->_next;//_head为哨兵卫 } iterator end() { return _head;//哨兵卫自然是链表结束的节点，因为list是循环链表 } const_iterator begin() const//这里的iterator和const_iterator我都是重命名过的 { return _head->_next; } const_iterator end() const { return _head; }

可以看到我们实现的const和非const版本的迭代器都没有问题。

既然都已经完成正向迭代器了，下面直接来完成反向迭代器。

反向迭代器的实现

依旧是要完成一个类

template<class T, class ptr, class ref>//依旧使用三个模板参数 struct Reserve__iterator { typedef list_node<T> Node; typedef Reserve__iterator<T, ptr, ref> Self;//和正向迭代器一样 Node* _point; Reserve__iterator(Node* x = nullptr) :_point(x) {}//构建一个构造函数 Self operator++() { _point = _point->_prev; return *this; }//对于反向迭代器而言，++就是正向迭代器的-- Self operator--() { _point = _point->_next; return *this; }//这些都是前置++/-- Self operator++(int) { Self tmp(_point->_prev); _point = _point->_prev; return tmp; } Self operator--(int) { Self tmp(_point->_next); _point = _point->_next; return tmp; } Self operator+(size_t n) { Node* tmp = _point; for (int i = 0; i < n; i++) { tmp = tmp->_prev; } return tmp; } Self operator-(size_t n) { Node* tmp = _point; for (int i = 0; i < n; i++) { tmp = tmp->_next; } return tmp; } Self operator-=(size_t n) { for (int i = 0; i < n; i++) { _point = _point->_next; } return _point; } Self operator+=(size_t n) { for (int i = 0; i < n; i++) { _point = _point->_prev; } return *this; } //依旧是*和-> ref operator*() { return _point->_data; } ptr operator->() { return &(_point->_data); } bool operator!=(const Self& b) { return _point != b._point; } bool operator==(const Self& b) { return _point == b._point; } };

然后依旧要在list类中增加反向迭代器需要的函数：

reserve_iterator rbegin()//开始即为结束 { return _head->_prev;//反向迭代器的开始应该为尾节点，所以 //这里返回_head->_prev } reserve_iterator rend()//结束即为开始 { return _head;//为什么这里反向迭代器返回的是_head而不是_head->_next呢？ //因为所有的迭代器（限定本博客）的打印区间都是左闭右开，为了打印第一个数据不能 //让第一个数据当作结束否则就不会打印最后一个数据 //正向迭代器也是同理 } const_reserve_iterator rbegin() const { return _head->_prev; } const_reserve_iterator rend() const { return _head; }

下面是我测试这些功能的代码：

void print(const list<int>& s1)//测试正向const迭代器 { list<int>::const_iterator t1 = s1.begin(); while (t1 != s1.end()) { cout << *t1 << " "; t1++; } cout << endl; } void print2(const list<int>& s1)//测试反向const迭代器 { list<int>::const_reserve_iterator t1 = s1.rbegin(); while (t1 != s1.rend()) { cout << *t1 << " "; t1++; } cout << endl; } void testlist1() { list<int> s1; s1.push_back(1); s1.push_back(2); s1.push_back(3); s1.push_back(4); s1.push_back(5); s1.push_back(6); list<int>::iterator t1 = s1.begin(); while (t1 != s1.end())//非const正向迭代器 { cout << *t1 << " "; t1++; } cout << endl; print(s1); cout << endl; list<int>::reserve_iterator t2 = s1.rbegin(); while (t2 != s1.rend())//非const反向迭代器 { cout << *t2 << " "; t2++; } cout << endl; print2(s1); }

运行截图：

构造函数二（带参数）

我知道的list还有两种初始化方式，

方式一：在创建的时候就放入值

list(size_t n, const T& x = T()) //这个初始化的方式也就是在创建的时候就将n个x放到链表中去 { empty_head();//创建一个头节点 while (n--) { push_back(x); }//这样就完成了，通过复用push_back完成。 }

下面是测试即运行截图。

方式二：使用迭代器区间初始化

拷贝构造函数以及=函数

下面我们来完成拷贝构造函数。

很简单的思路使用迭代器将b中的值取出来在尾插到*this中

list(const list<T>& b) { empty_head(); list<T>::const_iterator e1 = b.begin(); while (e1 != b.end()) { push_back(*e1); e1++; }//复用push_back将b中的值复制到*this中 }

下面来重载=符号

void swap(list<T>& a, list<T>& b) { std::swap(a._head, b._head);//只需要交换两个头节点的_head,自然就完成交换了 } void operator=(const list<T> b) { //这里的赋值操作符有两种写法，一种和拷贝函数一样，我就不写了，这里我使用的是交换的方法 swap(b);//直接将b和*this交换，不用担心这种写法会对传过来的参数有影响， //因为这里的b是原参的拷贝。 }

这里使用的方法就是复用了拷贝构造将this需要的值拷贝到了b中，再让b和this交换，这样就能完成赋值，并且b的销毁也会在=结束的时候，自动销毁。当然我现在还没有写析构函数，所以这个思路暂时还是存在问题的。析构函数的完成如果不复用函数的话，很难实现。

erase函数

erase函数也有两种实现的方式，一种是删除当前迭代器指向的值，另外一种是删除一段迭代器区间。

删除当前迭代器（单一删除）

iterator erase(iterator pos)//删除当前迭代器的值，为了防止出现迭代器失效的问题， //会将删除迭代器的下一个 //迭代器返回 { Node* prev = pos._point->_prev;//记住待删除节点的上一个节点 Node* next = pos._point->_next;//记住待删除节点的下一个节点 next->_prev = prev; prev->_next = next; delete pos._point; return next; }

思路很简单：改变待删除节点前面节点的next和后面节点的prev，最后删除掉当前节点即可

删除一段迭代器区间的值

//删除一段迭代器区间的值 iterator erase(iterator first, iterator last)//为了防止 //迭代器失效所以需要返回删除得这一段区间得下一个节点 { Node* prev = first._point->_prev; Node* next = last._point->_next; prev->_next = next; next->_prev = prev; while (first != last) { first = erase(first); }//这里复用了erase的函数重载 //因为上面得循环在first==last的时候就不会在进入了，如果 //不处理last，那么last就会删除失败 erase(last);//手动删除last return next;//单参数的构造函数支持隐式类型转换 }

思路基本和上面的是一样的，不过最后我们要复用一下删除单个节点值得erase用于释放空间。

测试代码：

void testlist4() { list<int> s1; s1.push_back(1); s1.push_back(2); s1.push_back(3); s1.push_back(4); s1.push_back(5); s1.push_back(6); for (auto e : s1) { cout << e << " "; } cout << endl; list<int>::iterator e1 = s1.begin(); while (e1 != s1.end()) { e1 = s1.erase(e1);//这里我们测试返回的是否是删除节点的下一个节点。 } for (auto e : s1) { cout << e << " "; } list<int> s2; s2.push_back(1); s2.push_back(2); s2.push_back(3); s2.push_back(4); s2.push_back(5); s2.push_back(6); list<int>::iterator e3 = s2.erase(s2.begin(), s2.begin()+2); cout << *e3 << endl; for (auto e : s2) { cout << e << " "; } cout << endl; }

下面是测试的运行截图：

clear函数

首先clear函数的目的是释放一个链表中除了哨兵卫以外的所有节点的值。在我们完成了erase函数的删除一段迭代器区间之后，这道题目就会非常的简单。直接复用即可，当然使用单个删除的erase函数也是可以的.

void clear() { //这里需要注意因为我的end函数返回的是哨兵卫，而clear函数是不清除哨兵卫的，所以方法一需要前置--end //方法一： erase(begin(), --end()); //方法二： /*iterator e1 = begin(); while (e1!=end()) { e1 = erase(e1); }*/ }

运行测试和运行截图：

析构函数

在完成了clear函数之后，析构函数就非常的好写了。

~list() { if(_head->_next !=_head) clear();//调用clear删除所有的非哨兵卫节点,只有存在有存值的节点的时候， //才取调用clear delete _head;//删除哨兵卫节点 _head = nullptr; }

insert函数

insert函数依旧有两种形式，一种是在pos位置的前面插入一个值，一种是在pos位置前面插入n个值

插入一个值：

iterator insert(iterator pos, const T& x = T())//在pos位置的前面插入一个x,并且返回插入那个值的迭代器 { Node* prev = pos._point->_prev; Node* tmp = buyNode(x);//创建一个新节点 tmp->_prev = prev; prev->_next = tmp; tmp->_next = pos._point; pos._point->_prev = tmp; return tmp; }

插入n个值：

iterator insert(iterator pos, size_t n, const T& x = T())//在pos的前面n个x { for (int i = 0; i < n; i++) { pos = insert(pos, x); }//复用单个的插入以完成多个的插入 return pos; }//返回的是插入完最后一个x后那个x所在的迭代器 void clear()

两个代码的思路很简单都是记录pos位置前面节点的迭代器（prev），然后创建一个新节点，让新节点的_prev指向prev，让新节点的_next指向pos然后返回这个新节点的迭代器。插入多个值也就是要循环多编并且考虑迭代器失效而已。

测试和运行截图：

pop_back，pop_front，push_front函数

头删和尾删函数就非常的好实现了。直接复用erase即可

void pop_back()//尾删 { erase(--end()); } void pop_front()//头删 { erase(begin()); }

至于头插复用insert函数即可

void push_front(const T& x = T()) { insert(begin(), x); }

当然push_back函数也可以复用insert函数完成。

测试和运行截图：

希望这篇博客能对你有所帮助，如果发现了任何错误，欢迎指出。