💐专栏导读

🌸作者简介：花想云，在读本科生一枚，致力于 C/C++、Linux 学习。

🌸本文收录于 C++系列，本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等，专为大学生打造全套 C++ 学习教程，持续更新！

🌸相关专栏推荐：C语言初阶系列 、C语言进阶系列 、数据结构与算法

💐文章导读

本章我们将认识与学习list的使用并且参照STL源码来模拟实现list容器，需要读者具有一定的数据结构基础。通过本章的学习，我们将对类和对象、模板的运用更加熟练，同时还会实现list的重要角色——迭代器，让我们对迭代器的了解更上一层楼~

🌷list是什么？

list是C++ STL中的一个容器，是一个双向链表，可以存储任意类型的元素。list中的元素可以通过指针在链表中进行高效的插入和删除操作，因此list通常被用于需要频繁进行插入和删除操作的场合。

🌷list如何使用？

• 使用list前需包含头文件< list >;

#include <list>

• 🍁定义一个list容器；

	list<int> mylist; // 声明一个空的listlist<int> mylist2(10); // 声明一个有10个默认值的listlist<int> mylist3(5, 2); // 声明一个有5个值为2的list

• 🍁向list中添加元素；

mylist.push_back(1); // 在list的末尾添加元素1
mylist.push_front(2); // 在list的开头添加元素2
mylist.insert(mylist.begin(), 3); // 在指定位置插入元素3

• 🍁访问list中的元素；

	cout << mylist.front() << endl; // 访问第一个元素cout << mylist.back() << endl; // 访问最后一个元素

• 🍁遍历list中的元素；

for (auto it = mylist.begin(); it != mylist.end(); ++it) {cout << *it << " ";
}

• 🍁删除list中的元素；

mylist.pop_front(); // 删除第一个元素
mylist.pop_back(); // 删除最后一个元素
mylist.erase(mylist.begin()); // 删除指定位置的元素
mylist.clear(); // 删除所有元素

list的常见使用就是这些了，若想查看更多操作，还需借助STL文档来学习。

🌷list的模拟实现

🌺定义list类

为了区别于库中的list类，我们可以在自己的命名空间中定义list类。list的基本成员变量只有一个——list的头结点（head）并且头节点内不存储有效数据。

• 🍁定义结点结构；

namespace hxy
{//定义结点结构template<class T>struct ListNode{struct ListNode<T>* _next; // 指向下一个结点struct ListNode<T>* _prev; // 指向前一个结点T _data; // 结点存储的数据ListNode(const T& data = T()) // 构造函数 // 申请一个节点 :_next(nullptr),_prev(nullptr),_data(data){}};
}

• 🍁定义list类；

namespace hxy
{//定义结点结构template<class T>struct ListNode{struct ListNode<T>* _next; // 指向下一个结点struct ListNode<T>* _prev; // 指向前一个结点T _data; // 结点存储的数据ListNode(const T& data = T()) // 构造函数 // 申请一个节点 :_next(nullptr),_prev(nullptr),_data(data){}};// list类的定义template<class T>class list{typedef ListNode<T> node; // 简写private:node* _head;}；
}

🌺构造函数

	list(){_head = new node;_head->_next = _head;_head->_prev = _head;}

🌺push_back

• 🍁对list进行尾插元素；

	void push_back(const T& data){node* newNode = new node(data); // 申请一个结点node* tail = _head->_prev; // list的尾结点就是头结点的前一个// 链接结点tail->_next = newNode;newNode->_prev = tail;newNode->_next = _head;_head->_prev = newNode;}

🌺pop_back

• 🍁对list进行尾删；

	void pop_back(){assert(_head->_next != _head);node* tail = _head->_prev;tail->_prev->_next = _head;_head->_prev = tail->_prev;delete tail; //释放尾结点}

🌷list迭代器

迭代器——作为list最精华的部分，有着及其重要的作用，且同样为list模拟实现中最难的一部分。通过本章的内容，我们对于迭代器的理解会更上一层楼!

在string与vector的学习中，我们经常使用下标+[]来访问容器的元素，非常方便。但是到了list以后的内容，[]访问元素的方法将不再适用，我们将使用迭代器。

前面的文章中曾经简单的提到过迭代器，描述它为一种像指针一样却又不单纯是指针的东西（string和vector中的迭代器在一些编译器下确实是原始指针）。接下来我们就模拟实现list的迭代器。

🌺定义list迭代器的类

迭代器本质就是对指针的封装模拟指针的行为，所以我们需要通过运算符重载来模拟实现指针的++、--以及*、->等操作。

	template<class T,class Ref,class Ptr> // 三个参数的含义分别为--数据类型T--T的引用--T的指针struct _list_iterator{typedef ListNode<T> node;typedef _list_iterator<T, Ref, Ptr> self;node* _node; //迭代器的基本成员变量_list_iterator(node* node):_node(node){}self& operator++(){//...}self operator++(int){//...}self& operator--(){//...}self operator--(int){//...}Ref& operator*(){//...}Ptr& operator->(){//...}bool operator==(const self& s){//...}bool operator!=(const self& s){//...}}

🌺迭代器运算符重载的实现

	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;}Ref& operator*(){return _node->_data;}Ptr& operator->(){return &(_node->_data);}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}

🌷list其它接口的实现

有了迭代器，我们才能更好的实现多种接口。

🌺迭代器相关函数

	template<class T>class list{typedef ListNode<T> node;public:typedef _list_iterator<T,T&,T*> iterator; // 类型重命名——普通迭代器typedef _list_iterator<T, const T&,const T*> const_iterator; // 类型重命名——const迭代器iterator begin() {return iterator(_head->_next);}iterator end() {return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}//...}

🌺insert——插入

list模拟实现时，主要完成insert与erase（删除）函数实现即可，其它的头插、尾删等函数可以复用这两个函数。

	void insert(iterator pos,const T& data){node* newNode = new node(data);node* cur = pos._node;node* prev = cur->_prev;newNode->_prev = prev;prev->_next = newNode;newNode->_next = cur;cur->_prev=newNode;}

🌺erase——删除

	iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node * next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next); // 返回删除位置的下一个迭代器位置}

🌺其它删除及插入操作

	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());}void clean() // 清空list{iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}

🌺迭代器区间构造

	// 迭代器区间构造template<class Iterator>list(Iterator begin, Iterator end){//初始化_head = new node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}

🌺拷贝构造

	//拷贝构造list(const list<T>& lt){//初始化_head = new node;_head->_next = _head;_head->_prev = _head;//复用区间构造list<T> tmp(lt.begin(), lt.end());swap(tmp);}

🌺赋值重载

	//赋值重载list<T>& operator=(list<T> lt){swap(lt);return *this;}

🌺析构函数

	~list(){clean();delete _head;_head = nullptr;}

🌷完整源码

#include<iostream>
#include<assert.h>
using namespace std;
namespace hxy
{//定义结点结构template<class T>struct ListNode{struct ListNode<T>* _next; // 指向下一个结点struct ListNode<T>* _prev; // 指向前一个结点T _data; // 结点存储的数据ListNode(const T& data = T()) // 构造函数 // 申请一个节点 :_next(nullptr),_prev(nullptr),_data(data){}};//迭代器的定义template<class T, class Ref, class Ptr> // 三个参数的含义分别为--数据类型T--T的引用--T的指针struct _list_iterator{typedef ListNode<T> node;typedef _list_iterator<T, Ref, Ptr> self;node* _node;_list_iterator(node* node):_node(node){}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;}Ref& operator*(){return _node->_data;}Ptr& operator->(){return &(_node->_data);}bool operator==(const self& s){return _node == s._node;}bool operator!=(const self& s){return _node != s._node;}};// list类的定义template<class T>class list{typedef ListNode<T> node;public: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;}// 迭代器区间构造template<class Iterator>list(Iterator begin, Iterator end){//初始化_head = new node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}void swap(list<T>& tmp){std::swap(_head, tmp._head);}//拷贝构造list(const list<T>& lt){//初始化_head = new node;_head->_next = _head;_head->_prev = _head;//复用区间构造list<T> tmp(lt.begin(), lt.end());swap(tmp);}//赋值重载list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clean();delete _head;_head = nullptr;}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}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());}void insert(iterator pos, const T& data){node* newNode = new node(data);node* cur = pos._node;node* prev = cur->_prev;newNode->_prev = prev;prev->_next = newNode;newNode->_next = cur;cur->_prev = newNode;}iterator erase(iterator pos){assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next); // 返回删除位置的下一个迭代器位置}void clean(){iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}}private:node* _head;};
}