前言
这里我们学习的是gcc下STL版本的list。STL里的list容器底层是一个双向带头节点的一个链表，不再是单链表，单链表实际运用很少，更多的是双向带头链表。
正文
list使用
默认成员函数
| 构造函数 | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
迭代器
| 函数声明 | 接口说明 |
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
容量
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个 |
增删查改
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
代码演示
这里list使用很简单，我就不一个一个演示了。就用一个测试案例测试下吧
void Print(const li::list<int>& lt)
{
li::list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//(*it)++;
cout << *it << " ";
++it;
}
}
void list_test01()
{
li::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
Print(lt);
cout << endl;
//这里是拷贝构造 内置类型 浅拷贝
li::list<int>::iterator it = lt.begin();
while (it != lt.end())
{
(*it)++;
cout << *it << " ";
++it;
}
}这里我就简单测试下，需要注意的是，erase之后迭代器被释放失效，记得用返回值接受。clear这里底层上就是释放掉了所有的节点，只留下一个头节点。因为链表结构决定了它是可以部分删除容量的，不像连续地址的顺序表。因此，list的clear就直接删除节点了，而不是仅仅清除数据。
list模拟实现
成员变量
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& x = T())
:_next(nullptr),
_prev(nullptr),
_val(x)
{
}
};
template<class T>
class list
{
typedef list_node<T> Node;
//...
//
private:
Node* _head;
size_t _size;
}从链表开始，就有点复杂了，使用很多封装和重命名。这里我们需要先实现一个结构体(结点)，
这里需要重名命下这个类模板，这是为啥呢？这是一个习惯问题。祖师爷在研究STL的时候，他自己也是从c语言过度来的，虽然类模板也是它老人家研究出来的。但是在声明一个变量的时候，加上一个模板，很容易忘记，尤其习惯了c语言的命名变量的语法。所以，这里重命名下是一种习惯问题，并且也可以简化代码。这也是一个好习惯，因为你的模板可不一定只有一个，如果你的leader突然让你改一下这个容器，增加一个模板，你难不成一个一个该吗？这时候重命名就香很多了，只需要改一下。
这里还有一个size,有这个参数我们就可以很直观的观察链表，和判断链表是否为空。有利于我们更直观的使用链表和调试。
默认成员函数
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
//不能用const引用
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
这里构造函数里面套了一个函数初始化，这也是向库里版本靠齐。这里的赋值重载是用的现代写法，直接swap交换，传统的写法是直接手搓一遍(不推荐)。这里的拷贝构造函数里面复用了push_back，析构函数复用了clear()，这也体现list的高度封装性，其实库里的比这里还复杂。动态内存分配也不是new而是封装了一个空间配置器，就是效率高点。我在vector的博客也提及过。我们学习STL的代码，强烈不建议一行一行看，否则你会直接想放弃的。这里我们先知道个大体逻辑。到下文会解释clear和push_back()这两个函数，其实push_back里面也是套用了insert的。就像套娃一样，这里的代码。
迭代器
重点 重点 重点 重要的事说三遍，list的迭代器可谓是学习list的重点也是一个难点，先问一下，如何设计list的迭代器？可以像vector里那样吗？直接指针吗？可是这里是一个自定义类型呀？解引用也不是结点的值呀？因此，这里肯定是要对*赋值重载的。所以，就可以先否定直接指针了，这肯定不行的！既然要赋值重载，那我们就肯定要自定义类型呀？对，这里的迭代器就是一个自定义类型，里面包含着一个结点指针，还有构造函数，完成初始化。这里不介绍反向迭代器，因为反向迭代器的设计和正向有点不一样，这里我们先学习正向迭代器，正向迭代器就够喝一壶了。
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->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
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;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};这里先给大家看一下完整版的迭代器设计，是不是很蒙，发现和我想的有点不一样呀!
struct _list_iterator
{
typedef list_node<T> Node;
Node* _node;
_list_iterator(Node* node)
:_node(node)
{}
};
这里先看我上面这个代码，是不是发现又看懂了。这里我们学习迭代器需要一步一步拆开学，他的设计其实有点难理解。我们上面讲了，迭代器需要设计成一个自定义类型，需要包装一下结点的指针，以便我们访问。这里的代码是一个雏形，有了这个雏形，对于begin(),end()，我们就完成的差不多了。但还需要大大的完善。这里还要对*，++等运算符赋值重载。那为啥有三个模板呢？这里是根据需求来设定的。首先*赋值重载返回的就是数据本身，所以数据的类型模板，我们需要你上传，直接引用，即使结构体的数据还是什么其他自定义类型数据，都可以返回正确的值。最后一个模板为啥要传一个指针呢？迭代器模仿的是指针的行为？既然是指针那么就可以用箭头访问结构体。所以，这里的迭代器也满足了这种要求。使用箭头访问结点的元素。同理，自己上传一个指针，这样后续更改代码，我们只用修改这部分代码。这里是如何设计const修饰的迭代器呢？这时候我们的模板就香很多了，我们这需要在上传模板的时候加上一个 const,这样子你需要什么我就返回什么。这也证明我们为啥要搞三个模板，就是因为，后面的代码设计是需要使用的。其实刚开始学这里的迭代器的时候，我也很蒙蔽，但是学到后面，你才发现祖师爷的这套设计有多厉害！这里的命名也是向库里靠拢的，建议大家以后命名也尽量向库里靠拢。
typedef list_node<T> Node;
public:
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&,const T*> const_iterator;
iterator begin()
{
return _head->_next; //单参数的构造函数支持隐式类型转换
//return iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}虽然这里链表里的迭代器看起来很简单，和vector差不多。但底层是很复杂的，这里也体现了迭代器的重要。为啥我们要用迭代器遍历数据，祖师爷为啥要研究出个迭代器。就是因为，有了迭代器，我们可以统一用法访问任何容器的任何形式数据。不像数组就要用下标，链表就要用指针。不方便程序员的开发。有了迭代器，STL里的任何容器都可以用迭代器访问。从list开始，迭代器才真正开始上难度，而不是简单的复用指针，这里我们学习list的迭代器的时候，不仅仅要懂list迭代器是如何实现，更要体会的是祖师爷设计的理念和思想。更重要的是人家这种思想，极大提高了编程简化。其实学习c++，c++意义不仅仅在利用c++开发软件和编写底层系统上，而且c++的设计的语法和理念为其他语言提供了模板，很多语言都有c++的影子，尤其像java语言，可以说是一个接近满分的抄作业选手。
容量
bool empty()
{
return _size == 0;
}
size_t size()
{
return _size;
}这里就是简单返回，没啥好说的。
增删查改
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
void push_back(const T& x)
{
/*Node* tail = _head->_prev;
Node* newNode = new Node(x);
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _head;
_head->_prev = newNode;*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
Node* newNode = new Node(x);
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
_size++;
return newNode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return next;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}这里要说一下，push_back和pop_back分别内部调用了insert和erase， 这里增删查改不用一个一个写，库里就是把大量重复的代码，封装起来。以后使用到这段代码就调用这个封装的函数，几乎全是封装。实际上，底层还是那几个指针交换位置。
源码
#pragma once
#include <assert.h>
#include <iostream>
namespace li
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& x = T())
:_next(nullptr),
_prev(nullptr),
_val(x)
{
}
};
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->_val;
}
Ptr operator->()
{
return &(_node->_val);
}
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;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&,const T*> const_iterator;
iterator begin()
{
return _head->_next; //单参数的构造函数支持隐式类型转换
//return iterator(_head->_next);
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
//不能用const引用
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
bool empty()
{
return _size == 0;
}
size_t size()
{
return _size;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
void push_back(const T& x)
{
/*Node* tail = _head->_prev;
Node* newNode = new Node(x);
tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _head;
_head->_prev = newNode;*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
Node* newNode = new Node(x);
prev->_next = newNode;
newNode->_prev = prev;
newNode->_next = cur;
cur->_prev = newNode;
_size++;
return newNode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
_size--;
return next;
}
private:
Node* _head;
size_t _size;
};
}
总结
学习list，学会使用是其次，更重要的是理解list底层的编写的理念和设计。这才是最终要的，关于list的学习，其中最重要的就是他的迭代器的设计，这里是最难的。其他部分都是高度的重复，像增删查改就是简单的链表编写。