CPP学习之list使用及模拟实现

一、list简介及用法

1. list简介
list是可以在常数范围内任意位置进行插入、删除、修改操作的有顺序性的容器，而且支持双向迭代，其底层是双链表结构，逻辑上连续但物理空间上不连续，只能通过指针来进行元素访问，无法使用下标随机访问。在任意位置的增删查改的实现上，list效率比vector高；在快排中，因为要取中的原因，vector支持下标随机访问，而list只能从开头或者尾部逐步迭代到对应位置，而且还需要额外的空间开销来存储节点的信息，这使得list的排序效率比vector要低。

2. 重要接口及使用
构造函数：

迭代器iterator

capacity

元素访问

增删查改

注意：在vector中进行增删操作会面临迭代器失效的风险，而在list中增加元素操作不会造成迭代器失效问题，只有删除操作会影响指向被删除元素的迭代器，并且其它的迭代器不会被影响。我们可以通过接收erase函数返回值的办法使迭代器仍然有效。

二、模拟实现

list的模拟实现有几个要点：

1. 需要模拟出双链表的节点，所以我们需要构建节点结构体，这个结构体要包含节点的元素，指向前一个和后一个节点的该结构体的指针；
2. 我们需要构建list的迭代器模板，这个迭代器要有非const及const类型，所以我们要用到模板，模板要有元素类型自定义，元素的const和非const的引用和指针，下面的代码中可以看到T代表元素类型，Ref代表元素引用，Ptr代表指向元素的指针；
3. 开始构建list类，其成员变量要包含哨兵位节点和代表链表内元素个数的size，成员函数则是实现list功能的重要接口。

list的模拟实现如下：

#pragma once
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<assert.h>
#include"my_reverse_iterator.h"using namespace std;// 注意：因为物理上结构的差异，list的迭代器与vector的不一样，需要封装成一个结构体并且重载引用等运算符
// 通过迭代器封装来改变迭代器的行为
// 单参数类型构造函数支持隐式类型转换
// 迭代器结构体内部不能处理节点的创建和释放template<class T>
struct _list_node
{typedef struct _list_node<T> list_node;list_node* _prev;list_node* _next;T _val;_list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_val(val){}};template<class T, class Ref, class Ptr > //T代表数据类型，Ref用于区分const与非const迭代器，Ptr用于箭头运算符重载返回_val
struct _list_iterator
{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self; //self代表iterator自身node* _node;_list_iterator(node* new_node):_node(new_node){}Ref operator*(){return _node->_val;}bool operator==(const self& it){return (_node == it._node);}bool operator!=(const self& it) const{return (_node != it._node);}self operator++(int) //这里不能加引用，因为返回的是temp，{self temp(*this); //采用了拷贝构造函数_node = _node->_next;return temp;}self& operator++(){_node = _node->_next;return *this;}self operator--(int) //这里不能加引用，因为返回的是temp，{self temp(*this); //采用了拷贝构造函数_node = _node->_prev;return temp;}self& operator--(){_node = _node->_prev;return *this;}Ptr operator->() //注意：这里经过特殊处理（C++标准）it->_val即可获得值，不用it->->_val//(正常情况下返回指针得再经过解引用才能得到值){return &_node->_val; //返回地址}};template<class T>
class my_list
{
public:typedef _list_node<T> node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, T*> const_iterator;typedef my_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef my_reverse_iterator<const_iterator, T&, T*> const_reverse_iterator;private:node* _head;size_t _size;public:void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;_size = 0;}my_list(){empty_init();}void clear() //删除链表除哨兵位外所有元素{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~my_list(){clear();delete _head;_head = nullptr;}my_list(const my_list<T>& list) //形参必须是引用才是拷贝构造函数{empty_init();for (auto& e : list) //节省栈帧空间{push_back(e);}}void swap(my_list<T>& list){std::swap(_head, list._head);std::swap(_size, list._size);}my_list<T>& operator=(my_list<T> list){swap(list);return *this;}iterator insert(iterator pos, const T& val) //默认在pos位置前插入数据{node* new_node = new node(val);node* prev = (pos._node)->_prev;new_node->_next = pos._node;new_node->_prev = prev;(pos._node)->_prev = new_node;prev->_next = new_node;_size++;return --pos; //这里return new_node; 也可以}void push_back(const T& val){//node* new_node = new node(val); //使用了默认构造函数(系统生成，无参，全缺省)//new_node->_next = _head; //使用了赋值运算符重载//new_node->_prev = _head->_prev;//_head->_prev->_next = new_node;//_head->_prev = new_node;insert(end(), val);}void push_front(const T& val){insert(begin(), val);}iterator erase(iterator pos) //返回删除元素的后一个元素的位置{assert(pos != end()); //注意：这里要检查链表内是否只有哨兵位，不然会出问题！！！node* next = (pos._node)->_next;node* prev = (pos._node)->_prev;next->_prev = prev;prev->_next = next;//iterator temp = ++pos; //注意：pos也改变了！！！delete pos._node;pos = nullptr;_size--;return next; //函数返回值是iterator类型，为什么这里可以返回node*类型？//因为这里隐式调用了iterator的构造函数，即iterator(next)！！！//如果不希望被隐式类型转换，那么就在构造函数前用explicit修饰//return temp;}void pop_back(){iterator temp = --end();erase(temp);}void pop_front(){erase(begin());}size_t size(){return _size;}iterator begin(){//return _head->_next; //注意，返回值的类型是iterator，用node*返回是错误的！return iterator(_head->_next); //采用迭代器的构造函数来返回}iterator end(){return iterator(_head);}const_iterator begin() const{//return _head->_next; //注意，返回值的类型是iterator，用node*返回是错误的！return const_iterator(_head->_next); //采用迭代器的构造函数来返回}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin(){return end();}const_reverse_iterator rbegin() const{return end();}reverse_iterator rend(){return begin();}const_reverse_iterator rend() const{return begin();}void print(){for (auto e : *this){cout << e << " ";}cout << endl;}
};

我们知道，list支持反向迭代，所以我们也需要模拟实现反向迭代器，以下是实现反向迭代器的一些要点：

1. 构建反向迭代器只需复用正向迭代器即可，正向迭代器自加那么反向迭代器就自减；
2. 在设计中，反向迭代器是正向迭代器的镜像，rbegin指向end，rend指向begin，所以在反向迭代器解引用操作符重载中，需要让指针自减再解引用；
3. 同样地，反向迭代器模拟实现也需要用到模板，模板要实现可以自定义是哪种迭代器(vector or list?)，const还是非const类型。类的成员变量仅有iterator _it。

如下是反向迭代器的模拟实现：

#pragma once
#include"my_list.h"template<class iterator, class ref, class ptr> //用普通迭代器来做反向迭代器，ref为类型引用，ptr是指针
class my_reverse_iterator
{
public:iterator _it;typedef my_reverse_iterator<iterator, ref, ptr> self;my_reverse_iterator(iterator it):_it(it){}ref operator*(){self temp = *this;return *(--temp._it);}self& operator++() //前置++{_it--;return *this;}self operator++(int) //后置++{iterator temp = _it;_it--;return temp;}self& operator--(){_it++;return *this;}self operator--(int){iterator temp = _it;_it++;return temp;}ptr operator->(){return &(operator*()); //直接返回解引用后内容的地址即可}bool operator!=(const self& it) const{return (_it != it._it);}
};

三、与vector对比

四、小结

本文一开始简要介绍了list的定义和重要接口，接着进行list的模拟实现，在模拟实现内容中列出了实现的数个要点，这些要点是关于list和反向迭代器的构建思路的，最后则是总结了list和vector的不同点，使读者可以根据需求来选择容器。
如有错误，请批评指正，谢谢。