一、list简介及用法
1. list简介
list是可以在常数范围内任意位置进行插入、删除、修改操作的有顺序性的容器，而且支持双向迭代，其底层是双链表结构，逻辑上连续但物理空间上不连续，只能通过指针来进行元素访问，无法使用下标随机访问。在任意位置的增删查改的实现上，list效率比vector高；在快排中，因为要取中的原因，vector支持下标随机访问，而list只能从开头或者尾部逐步迭代到对应位置，而且还需要额外的空间开销来存储节点的信息，这使得list的排序效率比vector要低。
2. 重要接口及使用
构造函数：
迭代器iterator
capacity
元素访问
增删查改
注意：在vector中进行增删操作会面临迭代器失效的风险，而在list中增加元素操作不会造成迭代器失效问题，只有删除操作会影响指向被删除元素的迭代器，并且其它的迭代器不会被影响。我们可以通过接收erase函数返回值的办法使迭代器仍然有效。
二、模拟实现
list的模拟实现有几个要点：
- 需要模拟出双链表的节点，所以我们需要构建节点结构体，这个结构体要包含节点的元素，指向前一个和后一个节点的该结构体的指针；
- 我们需要构建list的迭代器模板，这个迭代器要有非const及const类型，所以我们要用到模板，模板要有元素类型自定义，元素的const和非const的引用和指针，下面的代码中可以看到T代表元素类型，Ref代表元素引用，Ptr代表指向元素的指针；
- 开始构建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支持反向迭代，所以我们也需要模拟实现反向迭代器，以下是实现反向迭代器的一些要点：
- 构建反向迭代器只需复用正向迭代器即可，正向迭代器自加那么反向迭代器就自减；
- 在设计中，反向迭代器是正向迭代器的镜像，rbegin指向end，rend指向begin，所以在反向迭代器解引用操作符重载中，需要让指针自减再解引用；
- 同样地，反向迭代器模拟实现也需要用到模板，模板要实现可以自定义是哪种迭代器(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的不同点，使读者可以根据需求来选择容器。
如有错误，请批评指正，谢谢。