目录
在C++中list实际上是一个双向带头循环链表，所以list是不支持随机访问的。list的迭代器类型是双向迭代器，与string和vector不同的是，list不是简单的指针，list的迭代器是类。此处本文将会详细讲解。
list的成员变量
list的成员变量是指向哨兵位节点的指针，通过定义ListNode类来实现节点的定义及使用。注意：此处使用struct来声明ListNode而不用class的原因是：struct默认权限是public而private的默认权限是private，直接用struct可以让类外直接访问。
template<class T>
struct ListNode
{
//初始化节点
ListNode(const T& val=T())
:_val(val)
,_next(this)
,_prev(this)
{}
T _val;
ListNode<T>* _next;
ListNode<T>* _prev;
};
template<class T>
class list
{
public:
typedef ListNode<T> ListNode;
private:
ListNode* _phead;
};list的迭代器
list底层是节点所以list是不支持随机访问的，因此不能简单的对指针++或--来实现对迭代器的左移和右移。list迭代器底层也是一个类，这个类用来存放当前节点。重载++，--等等迭代器的基本功能。
迭代器的定义
此处的模板并不完善，后面还要添加其他模板。
//创建list迭代器
template<class T>
struct list_iterator
{
typedef ListNode<T> ListNode;
typedef list_iterator<T> list_iterator;
//构造函数
list_iterator(ListNode* node = nullptr)
:_node(node)
{}
ListNode* _node;
};迭代器*和->
//重载解引用*
T& operator*()
{
return _node->_val;
}
//重载->
T* operator->()
{
return &(operator*); //此处直接调用*运算符重载来实现取地址
}注意：此处需要考虑只有读取权限的const_iterator不能对解引用的数据进行修改，所以再使用T&和T*是明显不够的。
因此需要添加模板参数来实现const_iterator。
template<class T,class Ref ,class Ptr>
//用ref来代替T&和const T&，同理用Ptr来代替T*和const T*
typedef list_iterator<T,Ref,Ptr> Self;
//重载解引用*
Ref operator*()
{
return _node->_val;
}
//重载->
Ptr operator->()
{
return &(operator*); //此处直接调用*运算符重载来实现取地址
}在list的类中iterator和const_iterator的声明如下；
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;迭代器的++和--
typedef list_iterator<T,Ref,Ptr> Self;
//重载++,非const类型
Self operator++()
{
_node = _node->_next;
return *this;
}
//重载--，非const类型
Self operator--()
{
_node = _node->_prev;
return *this;
}
//重载++,const类型
Self operator++()const
{
_node = _node->_next;
return *this;
}
//重载--，const类型
Self operator--()const
{
_node = _node->_prev;
return *this;
}此处前置++和--就不展示了。
迭代器的==和!=
//重载==
bool operator==(const Self& it)
{
return _node == it._node;
}
//重载!=
bool operator!=(const Self& it)
{
return !(*this==it); //此处直接调用==
}迭代器代码汇总
//创建list迭代器
template<class T,class Ref ,class Ptr>
//用ref来代替T&和const T&，同理用Ptr来代替T*和const T*
struct list_iterator
{
typedef ListNode<T> ListNode;
typedef list_iterator<T,Ref,Ptr> Self;
//构造函数
list_iterator(ListNode* node = nullptr)
:_node(node)
{}
//重载++,非const类型
Self operator++()
{
_node = _node->_next;
return *this;
}
//重载--，非const类型
Self operator--()
{
_node = _node->_prev;
return *this;
}
//重载++,const类型
Self operator++()const
{
_node = _node->_next;
return *this;
}
//重载--，const类型
Self operator--()const
{
_node = _node->_prev;
return *this;
}
//重载解引用*
Ref operator*()
{
return _node->_val;
}
//重载->
Ptr operator->()
{
return &(operator*); //此处直接调用*运算符重载来实现取地址
}
//重载==
bool operator==(const Self& it)
{
return _node == it._node;
}
//重载!=
bool operator!=(const Self& it)
{
return !(*this==it); //此处直接调用==
}
ListNode* _node;
};list的成员函数
template<class T>
class list
{
public:
typedef ListNode<T> ListNode;
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
private:
ListNode* _phead;
};迭代器的begin和end
//begin函数，非const类型
iterator begin()
{
return _phead->_next; //此处使用了隐式类型转化，将ListNode*转化为了iterator
}
//end函数，非const类型
iterator end()
{
return _phead;
}
//begin函数，const类型
const_iterator begin()const
{
return _phead->_next;
}
//end函数，const类型
const_iterator end()const
{
return _phead;
}构造函数
无参构造
//构造函数，无参初始化
list()
:_phead(new ListNode) //此处需要创建哨兵位，交给ListNode的构造函数
{}迭代器构造
此处偷懒直接调用了push_back尾插函数。
//迭代器构造函数
template<class T>
list(const T* first, const T* last)
: _phead(new ListNode) //还是创建哨兵位
{
while (first != last)
{
push_back(*first);
++first;
}
}n的val构造
//用n个val构造
list(size_t n, const T& val)
:_phead(new ListNode)
{
while (n--)
{
push_back(val);
}
}拷贝构造
//拷贝构造
list(const list& l)
: _phead(new ListNode)
{
for (auto& e : l) //范围for遍历原链表
{
push_back(e);
}
}尾插和头插
尾插即创建新节点，对原有节点的指针进行修改。
//尾插
void push_back(const T& val)
{
ListNode* newnode = new ListNode(val);
newnode->_next = _phead;
newnode->_prev = _phead->_prev;
_phead->_prev->_next = newnode;
_phead->_prev = newnode;
}
//头插
void push_front(const T& val)
{
ListNode* newnode = new ListNode(val);
newnode->_next = _phead->_next;
newnode->_prev = _phead;
_phead->_next->_prev = newnode;
_phead->_next = newnode;
}尾删和头删
删除就是记录需要删除的节点位置将其前后节点指向改变即可。
//尾删
void pop_back()
{
ListNode* del = _phead->_prev;
del->_prev->_next = _phead;
_phead->_prev = del->_prev;
delete[] del;
}
//头删
void pop_front()
{
ListNode* del = _phead->_next;
del->_next->_prev = _phead;
_phead->_next = del->_next;
delete[] del;
}指定位置插入，删除
通过迭代器实现指定位置的插入和删除。指定位置插入会返回插入节点的迭代器；指定位置删除会返回删除位置的下一个迭代器。
//指定位置之前插入
iterator insert(iterator it, const T& val)
{
ListNode* newnode = new ListNode(val);
ListNode* cur = it._node;
newnode->_next = cur;
newnode->_prev = cur->_prev;
cur->_prev->_next = newnode;
cur->_prev = newnode;
return newnode;
}
//指定位置删除
iterator erase(iterator it)
{
ListNode* del = it._node;
ListNode* cur = del->_next;
del->_prev->_next = cur;
cur->_prev = del->_prev;
return cur;
}swap交换
此处为了实现swap(l1,l2)，而不是l1.swap(l2)，需要使用友元函数而不是成员函数。
注意：编译器在解析友元函数的时候无法正确的匹配外部声明的模板函数，此时就需要在声明的时候也加上模板参数。
template<class T>
friend void swap(list<T>& l1, list<T>& l2);
template<class T>
void swap(list<T>& l1, list<T>& l2)
{
std::swap(l1._phead, l2._phead);
}clear
list::clear函数的作用是清空有效节点，只保留哨兵位。注意：清空节点之后还要将哨兵位指向本身。
void clear()
{
ListNode* cur = _phead->_next;
while (cur != _phead)
{
ListNode* del = cur;
cur = cur->_next;
delete[] del;
}
//清空数据之后，将哨兵位指向哨兵位
_phead->_next = _phead;
_phead->_prev = _phead;
}返回首节点和尾节点
返回首尾节点的值。
//非const类型
T& front()
{
return _phead->_next->_val;
}
T& back()
{
return _phead->_prev->_val;
}
//const类型
const T& front()const
{
return _phead->_next->_val;
}
const T& back()const
{
return _phead->_prev->_val;
}返回链表长度
//返回链表长度
size_t size()
{
ListNode* cur = _phead->_next;
size_t sz = 0;
while (cur != _phead)
{
cur = cur->_next;
++sz;
}
return sz;
}判空
//链表是否为空
bool empty()
{
return _phead == _phead->_next;
}赋值运算符重载
进行赋值的是否需要先将原链表的所有数据清空。
//赋值运算符重载
list& operator=(const list& l)
{
clear();
ListNode* cur = l._phead->_next;
while (cur != l._phead)
{
push_back(cur->_val);
cur = cur->_next;
}
return *this;
}