C++容器——list的基础实现

C++容器中的list，本质是C语言基础数据结构中的链表结构。C++各类容器的使用方法差别不大，通过vector这个类模板的应用，其余类模板的使用也几乎是以相同的方法来实现。本篇博客将重点讲述list的基础底层实现。

通过string和vector的底层实现，我们对类模板的使用场景有了进一步的印象；同时，我们对于迭代器有了基础的认知，通过对于迭代器的使用，我们发现迭代器是一个类似于指针一样的东西。由于string和vector本质都是数组，数组指针就可以起到迭代器的作用，所以在对其进行底层结构实现的时候，通过typedef将数组指针变换为迭代器即可。而list本质是由一个一个的节点组成的结构，节点的指针还能否起到数组指针的作用？这也是list数据结构本质不同的地方，同时list的iterator如何实现将成为本篇博客的重点。

一.不同类型的迭代器

上面几个，是算法库中的几个需要传递迭代器进行使用的函数，但通过观察其参数以及函数模板，可以发现，不同函数对于迭代器的明明不相同。不同迭代器的名称有着不同的含义。

大致可以分为四种迭代器：1.InputIterator（只写迭代器)；2.ForwardIterator（前向迭代器）；3.BidirectionalIterator（双向迭代器）；4.RandomAccessIterator（随机迭代器）。

这是这几种迭代器的一个功能表格：单向迭代器（前向迭代器）仅支持向前遍历（++），代表的数据结构有：单链表、哈希表；双向迭代器，表示其可以正反遍历（++/--），代表性的数据结构有：红黑树/双向链表-list；随机迭代器，不仅支持++/--还支持迭代器的+/-，代表性的如string vector，我们在对这两个实现的过程中也能体会到，由于其底层是数组指针，所以支持+/-。

这几种迭代器的功能本质是向下兼容，如果一个函数需要单向迭代器，那么传递双向和随机都可以；如果一个函数需要双向迭代器，那么传递随机迭代器也可以；如果一个函数需要随即迭代器，那么只能传递随即迭代器。

但是可以看出，还有一个InputIterator，只写迭代器，而在我们使用迭代器的过程中，几乎不会看到只能写不能读的迭代器，所以该迭代器的含义是，传递单向、双向、随机迭代器这三者中的任何一个都可以使用该函数。

而本篇博客实现的list，本质为双向带头循环链表，它的迭代器应该为双向迭代器。

二.list的基础使用

2.1构造函数

list类模板，包含基础的默认构造；n个值的构造；initializer_list的构造，以及拷贝构造。

2.2迭代器相关

迭代器相关函数，还是主要的begin、end 、const类型的cbegin和const类型的cend。分别返回普通迭代器iterator和const迭代器const_iterator。

2.3容量大小和数据相关

empty判空函数；size返回当前链表有多少节点；front和back分别返回当前链表的第一个节点的数据和最后一个节点的数据；

2.4 主要的增删查改相关

头插头删

尾插尾删

某一迭代器位置的插入删除

整个链表清空

三.list的基础实现

3.1成员变量

list是一个链表，而链表要由一个一个的节点组成：所以需要一个表示节点的结构体，和一个能将所有节点串连起来的链表：

template <class T> struct list_node { T _data; list_node* _next; list_node* _prev; list_node(T data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) {} };

表示节点的结构体用类模板来实现。节点内部要有三个成员变量才能表示出一个链表的节点：1.当前节点存放的数据_data；2.指向下一个节点的指针_next；3.指向上一个节点的指针_prev。

节点的构造函数，只需要将数据初始化，两个指针分别置为空指针即可。

template<class T> class list { public: typedef list_node<T> node; list() :_head(new node) { _head->_next = _head; _head->_prev = _head; } private: node* _head; };

链表同样用类模板来实现，在链表内部首先将list_node的类模板重命名为node，从而方便内部使用。链表的成员函数，仅需要一个头节点来将所有节点串联起来即可。头节点不存放任何有效数据，且在没有数据时，自己指向自己。所以在构造函数中，首先创建了一个头节点，然后其前后指针分别指向自己。这样就完成了一个链表头节点的初始化。

3.2 push_back

void push_back(const T& val) { node* newnode = new node(val); newnode->_next = _head; newnode->_prev = _head->_prev; _head->_prev->_next = newnode; _head->_prev = newnode; }

push_back是尾插函数，表示在当前链表的最后一个节点之后插入一个值。

首先我们利用传递的数据创建一个新的节点。然后分别改变这个新节点和头节点的指向即可。（这里较为省略指向互相改变的过程，该过程在C语言基础数据结构的链表中解释的较为详细）

到这里，可以开始进行基础的测试工作：

void test1() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); }

创建一个空链表，然后尾插1 2 3 4，通过调试面板观察：

可看出实现了基础的链表结构，0表示头节点，但该数据并不是有效数据，仅仅是头节点的数据位。正常尾插了1 2 3 4。

3.3 迭代器的实现

在string和vector中，由于其底层使用数组来实现的这个结构，所以数组的指针就可以当作迭代器来使用。但是这里的原生指针是node*，它的解引用拿到的是整个节点而不是节点的数据，它++之后走到的是间隔node*大小的空间之后的下一块node*大小的位置，但这个位置是否是有效数据的位置就不确定了，因为链表不是连续的空间结构。

指向节点的指针并不能起到迭代器的作用，并且相关的操作符也无法对该节点指针进行符合预期的操作。所以就需要对该指针进行一定的封装，从而让其起到迭代器的效果：

template<class T> struct __list_iterator { typedef list_node<T> Node; Node* _node; __list_iterator(Node* node) :_node(node) {} T& operator*() { return _node->_data; } bool operator!=(const __list_iterator<T>& it) const { return _node != it._node; } bool operator==(const __list_iterator<T>& it) const { return _node == it._node; } };

这里实现了一个叫做__list_iterator的类模板，内部的成员变量为一个指向节点的node*类型的指针。构造函数，用外部传递的结点指针来初始化该成员变量即可。

这样就将外部的一个指向节点的指针构造成了一个__list_iterator的类对象。通过对于解引用运算符的重载，实现了取出该节点内部数据的功能。这样调用该类型对象时，对其解引用就实现了取出节点内部数据的功能。

同时判断节点相等和不等：只需要将两个类对象的_node指针判断是否相同/不同即可。

__list_iterator<T>& operator++() { _node = _node->_next; return *this; } __list_iterator<T> operator++(int) { __list_iterator<T> tmp(*this); _node = _node->_next; return tmp; } __list_iterator<T>& operator--() { _node = _node->_prev; return *this; } __list_iterator<T> operator--(int) { __list_iterator<T> tmp(*this); _node = _node->_prev; return tmp; }

前置++/--，后置++/--，都分别通过运算符重载来实现。++让该节点通过_next指针走到下一个节点的位置；--让该节点通过_prev指针走到上一个节点的位置。

同时在list类内部，通过typedef __list_iterator<T> iterator;将该类型变为iterator

typedef __list_iterator<T> iterator;

同时在list内部要实现begin和end

iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); }

begin和end函数都返回一个iterator对象。begin通过第一个节点指针来构造一个iterator对象并返回，end则通过头节点指针来构造一个iterator对象并返回。

这是第一次通过类模板的方式来实现一个iterator对象，回顾上面的实现过程：首先，节点指针无法达到我们需要的目的，无论是对其解引用还是++、--操作符。所以我们用一个类型将这个结点指针封装起来，在该类型内部重载所需要用到的几个函数；之后在list类内对这个对象重命名为iterator即可。接下来进行一些基础测试：

list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); list<int>::iterator it = lt1.begin(); while (it != lt1.end()) { cout << *it << " "; it++; } cout << endl;

这是常用到的一个迭代器遍历和打印的方法。

程序正常输出了每一个元素。到目前为止，所实现的基础的itetator能正常使用。

我们尝试写一个打印函数，这样就不需要每次输出验证时，都在写一遍迭代器遍历的过程。

template <class T> void print(const list<T>& val) { typename list<T>::const_iterator it = val.begin(); while (it != val.end()) { cout << *it << " "; it++; } cout << endl; }

打印函数写成一个函数模板的形式。注意如果函数模板嵌套类模板，并取内部的一个类型时，要在类模板前面加上typename告诉编译器这是一个类型，而不是一个静态变量。或者直接用auto自动识别类型。

打印函数参数传递一个const list&类型的对象，因为print函数不需要对内部数据进行改变。

但这样iterator内部没有合适的函数重载来调用const类型的对象。

那么能否在__list_iterator对象内部重载一份：

const T& operator*() const { return _node->_data; }

这样能否实现const_iterator的功能呢？返回值的constT& 没有问题，因为const_iterator对象要求返回值不能修改。那么const成员函数这一点存在问题，因为该const成员函数，需要const __list_iterator对象才能调用，而const __list_iterator对象就不能实现++/--等功能了。

这里需要格外注意const_iterator对象是迭代器可以正常遍历，而其指向的内容不能修改。

较为简单的解决方法是，再实现一个对象，让其能达到const_iterator的效果。

template<class T> struct __list_const_iterator { typedef list_node<T> Node; Node* _node; __list_const_iterator(Node* node) :_node(node) {} const T& operator*() { return _node->_data; } __list_const_iterator<T>& operator++() { _node = _node->_next; return *this; } __list_const_iterator<T> operator++(int) { __list_iterator<T> tmp(*this); _node = _node->_next; return tmp; } __list_const_iterator<T>& operator--() { _node = _node->_prev; return *this; } __list_const_iterator<T> operator--(int) { __list_const_iterator<T> tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const __list_const_iterator<T>& it) const { return _node != it._node; } bool operator==(const __list_const_iterator<T>& it) const { return _node == it._node; } };

这里实现了一个__list_const_iterator的类模板，内部解引用操作符的重载返回对象为const T&，之后在list内，将这个类模板typedef成const_iterator即可。这样就能实现普通对象调用普通iterator，const对象调用const_iterator。

typedef __list_const_iterator<T> const_iterator; const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); }

同时要注意实现const_iterator版本的begin 和end。

这是第一种解决方法。通过观察两个iterator类型可以发现：两个类型中，只有operator* 解引用操作符重载的返回值类型不同，那么有什么方法可以用同一个模板表示出不同的返回值类型吗？

再加入一个模板参数，用来表示解引用操作符的返回值类型即可：

template<class T ,class Ref> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref> Self; node* _node; __list_iterator(node* node) :_node(node) {} Ref operator*() { return _node->_data; } Self operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(_node); _node = _node->_next; return tmp; } Self operator--() { _node = _node->_prev; return *this; } Self operator--(int) { Self tmp(_node); _node = _node->_prev; return tmp; } bool operator != (const Self& it) { return (_node != it._node); } bool operator == (const Self& it) { return (_node == it._node); } };

添加了一个新的模板参数Ref用来当作解引用操作符重载函数的返回值。这样只需要在list内部typedef即可：

typedef __list_iterator<T, T& > iterator; typedef __list_iterator<T, const T& > const_iterator;

在list内部，针对__list_iterator的函数模板，第一个参数传递T，第二个参数传递T&，就能表示普通的iterator对象；第二个参数改为const T&，即可表示const_iterator对象。

本质是同一个类模板，通过传递不同的参数，分别实例化了iterator和const_iterator这两个对象。

如果list内部存放的不是内置类型数据，而是自定义类型：

struct A { int _a1; int _a2; A(int a1 = 0,int a2 = 0) :_a1(a1) ,_a2(a2) { } };

这里实现了一个简单的结构体A。

void test2() { list<A> lt1; lt1.push_back({ 1,1 }); lt1.push_back({ 2,2 }); lt1.push_back({ 3,3 }); lt1.push_back({ 4,4 }); lt1.push_back({ 5,5 }); list<A>::iterator it = lt1.begin(); while (it != lt1.end()) { cout << (*it)._a1 << ":" << (*it)._a2 << endl; it++; } }

通过迭代器遍历进行输出的过程中，需要利用 “.”操作符，分别取出节点内部存放数据类型A的两个变量。

正常来说，还有 ->操作符来实现取出数据。但是针对it对象，不能这么写，因为it是一个实例化的对象，还没有实现->操作符的重载。

所以接下来就需要针对->来进行函数重载。可知，普通对象调用普通迭代器iterator，所以普通对象取出元素后可以进行修改；const对象调用const_iterator，取出元素后不能进行修改，所以

->的函数重载也许要有两种返回值类型，T*和const T*。

template<class T ,class Ref,class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref , Ptr> Self; node* _node; __list_iterator(node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &(_node->_data); } Self operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(_node); _node = _node->_next; return tmp; } Self operator--() { _node = _node->_prev; return *this; } Self operator--(int) { Self tmp(_node); _node = _node->_prev; return tmp; } bool operator != (const Self& it) { return (_node != it._node); } bool operator == (const Self& it) { return (_node == it._node); } };

而针对T*和const T*的这个问题，本质又是仅仅只有返回值不同， 所以再次添加一个类模板参数。list函数内部只需要进行typedef即可：

typedef __list_iterator<T, T& , T*> iterator; typedef __list_iterator<T, const T& , const T*> const_iterator;

在list内部，如果是iterator对象，则传递T*的参数类型；如果是const_itertator对象，则传递const T*的参数类型。

list<A> lt1; lt1.push_back({ 1,1 }); lt1.push_back({ 2,2 }); lt1.push_back({ 3,3 }); lt1.push_back({ 4,4 }); lt1.push_back({ 5,5 }); list<A>::iterator it = lt1.begin(); while (it != lt1.end()) { cout << (*it)._a1 << ":" << (*it)._a2 << endl; cout << it->_a1 << ":" << it->_a2 << endl; cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl; it++; }

这样，针对A类型对象的输出就变为上面这种输出格式。

在针对->的函数重载中，返回的是节点指针，按照理论来说，节点指针还需要再利用一次->才可以正常输出。但这里只调用了一次就正常输出了A内部的两个数据。

这是编译器的优化。如果通过operator->（）来调用，就需要再->一次来输出数据。

到这里，针对迭代器类型对象的实现，就大体完成了。这是第一次实现对于迭代器的封装工作，需要细细体会。往后的函数实现就十分简单。

3.4 insert和erase函数

iterator insert(iterator position , const T& val) { node* newnode = new node(val); node* prev = position._node->_prev; newnode->_prev = prev; newnode->_next = position._node; prev->_next = newnode; position._node->_prev = newnode; return iterator(newnode); }

insert函数，再某一迭代器位置插入某个值。与string和vector均不同的是，list中插入数据，只需要改变前后节点的指向即可。

首先创建一个存放有目标数据的新节点，之后，让迭代器节点的上一个节点和该迭代器节点指向newnode，以及让newnode分别指向前后节点即可。最后返回newnode位置的迭代器。

iterator erase(iterator position) { node* prev = position._node->_prev; node* next = position._node->_next; prev->_next = next; next->_prev = prev; delete position._node; return iterator(next); }

erase，删除某个迭代器位置的数据，并返回该迭代器位置的下一个数据。同样的，只需要改变该迭代器位置的上一个节点_prev和下一个节点_next的指向即可。

基础测试：

list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); print(lt1); lt1.insert(lt1.begin(), 0); lt1.insert(lt1.end(), 5); print(lt1); lt1.erase(lt1.begin()); print(lt1); lt1.erase(--lt1.end()); print(lt1); lt1.clear(); print(lt1);

首先创建一个空链表，尾插4个数据。之后分别在begin位置和end位置插入0和5。在分别调用erase删除这两个位置的值。注意insert插入数据，可以在end位置插入，因为表示在end之前插入一个数据。但是删除的时候不能删除end位置，因为end是头节点。

首先尾插的1 2 3 4。之后在第一个位置插入0，最后一个位置插入5。再删除掉这两个值。

而有了insert和erase后，就可以对push_back函数进行改写

void push_back(const T& val) { //node* newnode = new node(val); //newnode->_next = _head; //newnode->_prev = _head->_prev; //_head->_prev->_next = newnode; //_head->_prev = newnode; insert(this->end(), val); }

直接调用insert在end位置插入数据即可。

那么pop_back、push_front、pop_front，都可以通过复用insert和erase来实现

void pop_back() { if (!empty()) { erase(--end()); } } void pop_front() { if (!empty()) { erase(begin()); } } void push_front(const T& val) { insert(begin(), val); }

头插，只需要在begin迭代器的位置插入数据即可。

头删尾删只需要分别删除begin位置和end的前一个位置即可。注意头删尾删的时候要判断是否为空链表，只有当该链表不为空时再进行删除。

3.5 clear函数

void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }

利用迭代器遍历每个节点，依次erase删除该节点即可。

3.6 其余的构造函数和析构函数以及赋值运算符重载

list(initializer_list<T> lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } } list(size_t n, const T& val) { _head = new node; _head->_next = _head; _head->_prev = _head; for (size_t i = 0; i < n; i++) { push_back(val); } } list(const list<T>& lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } } list<T>& operator=(const list<T>& lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } return *this; } ~list() { clear(); delete _head; _head = nullptr; }

initializer_list构造、拷贝构造、赋值运算符重载，这三个函数，都只需要创建一个头节点后，遍历每个节点然后依次尾插即可。

n个值的构造。创建一个头节点，循环n次，每次都尾插该值即可。

析构函数，调用clear函数清空整个链表，之后只需要删除头节点即可。

3.7 取头取尾

T& front() { return _head->_next->_data; } const T& front() const { return _head->_next->_data; } T& back() { return _head->_prev->_data; } const T& back() const { return _head->_prev->_data; }

取头取尾，分别都实现两个重载，用来给普通版本和const版本调用。分别返回第一个位置的数据和最后一个位置的数据即可。

至此，实现了list的大部分底层结构，以及常用部分的实现。在函数实现部分其实与vector大差不差，主要内容仍然围绕增删查改来实现。但是，针对迭代器的实现是与之前的有着极大的不同，需要反复思考迭代器的实现方式。

以下是完整版的list.h

#pragma once #include<iostream> #include<list> #include<algorithm> #include<initializer_list> using namespace std; struct A { int _a1; int _a2; A(int a1 = 0,int a2 = 0) :_a1(a1) ,_a2(a2) { } }; namespace Practice { template <class T> struct list_node { T _data; list_node* _next; list_node* _prev; list_node(T data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) {} }; template<class T ,class Ref,class Ptr> struct __list_iterator { typedef list_node<T> node; typedef __list_iterator<T, Ref , Ptr> Self; node* _node; __list_iterator(node* node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &(_node->_data); } Self operator++() { _node = _node->_next; return *this; } Self operator++(int) { Self tmp(_node); _node = _node->_next; return tmp; } Self operator--() { _node = _node->_prev; return *this; } Self operator--(int) { Self tmp(_node); _node = _node->_prev; return tmp; } bool operator != (const Self& it) { return (_node != it._node); } bool operator == (const Self& it) { return (_node == it._node); } }; template<class T> class list { public: typedef list_node<T> node; typedef __list_iterator<T, T& , T*> iterator; typedef __list_iterator<T, const T& , const T*> const_iterator; list() :_head(new node) { _head->_next = _head; _head->_prev = _head; } list(initializer_list<T> lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } } list(size_t n, const T& val) { _head = new node; _head->_next = _head; _head->_prev = _head; for (size_t i = 0; i < n; i++) { push_back(val); } } list(const list<T>& lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } } list<T>& operator=(const list<T>& lt) { _head = new node; _head->_next = _head; _head->_prev = _head; for (const auto& e : lt) { push_back(e); } return *this; } ~list() { clear(); delete _head; _head = nullptr; } iterator begin() { return iterator(_head->_next); } const_iterator begin() const { return const_iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); } void push_back(const T& val) { //node* newnode = new node(val); //newnode->_next = _head; //newnode->_prev = _head->_prev; //_head->_prev->_next = newnode; //_head->_prev = newnode; insert(this->end(), val); } void push_front(const T& val) { insert(begin(), val); } bool empty() { return (_head->_next == _head); } void pop_back() { if (!empty()) { erase(--end()); } } void pop_front() { if (!empty()) { erase(begin()); } } iterator insert(iterator position , const T& val) { node* newnode = new node(val); node* prev = position._node->_prev; newnode->_prev = prev; newnode->_next = position._node; prev->_next = newnode; position._node->_prev = newnode; return iterator(newnode); } iterator erase(iterator position) { node* prev = position._node->_prev; node* next = position._node->_next; prev->_next = next; next->_prev = prev; delete position._node; return iterator(next); } void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } T& front() { return _head->_next->_data; } const T& front() const { return _head->_next->_data; } T& back() { return _head->_prev->_data; } const T& back() const { return _head->_prev->_data; } void remove(const T& val) { iterator target = std::find(begin(), end(),val); if (target != end()) { erase(target); } } private: node* _head; }; }