【C++】STL---list
STL---list
一、list 的介绍
- list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)。
二、list 的模拟实现
list 学习时也要学会查看文档：list 文档介绍，在实际中我们熟悉常见的接口就可以，下面我们直接开始模拟实现，在模拟实现中我们实现的是常见的接口，并且会在实现中讲解它们的使用以及注意事项。
首先跟以往不一样的是，list 是一个个节点连接起来的，所以它不是连续的物理空间，这也就意味着，它不用扩容，每次插入的时候只需要申请一个节点，然后连接起来即可；
其次，list 底层的迭代器实现也跟 string和 vector 不一样，它们两个的迭代器可以说是原生指针，但是 list 的迭代器是要让节点指向下一个节点，所以底层实现也不一样；例如我们想让迭代器 it，往后迭代，就是 ++it，但是底层的实现却不是真的让节点++，因为它们的空间不是连续的，所以我们要把 list 迭代器封装成一个类。
首先我们先创建一个自己的命名空间，把 list 节点的类，list 迭代器的类，list 类都放进去；
1. list 节点类
list 节点类如下，因为是双向链表，所以应该有一个数据，两个指针；
namespace Young
{
// list 节点类
template <class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;
list_node(const T& x = T())
:_data(x)
,_next(nullptr)
,_prev(nullptr)
{}
};
}2. list 正向迭代器类
首先我们先定义一个类模板，其参数有三个，分别是类型、类型的引用(const 和 非const) 、类型的指针(const 和 非const) ；
为什么要定义三个模板参数呢，因为考虑到 const 迭代器，const 迭代器和普通迭代器不是同一个类，不能直接在 iterator 前直接加 const，如 const iterator ，这不是 const 迭代器，因为这里的 const 修饰的是迭代器本身，就是迭代器本身不能修改，但是我们期望的是迭代器本身可以被修改，如 it++、++it，只是期望迭代器指向的内容不能被修改，如 *it = 10、it->10 ；
这就类比 const T* 和 T* const ， const T* 中 const 是修饰指向的内容不能被修改，而 T* const 中 const 修饰的是指针本身不能被修改；而我们需要实现的 const 迭代器 是要满足第一种的，所以 list 中普通迭代器和 const 迭代器 是两个完全不一样的类，应该写成两个类，但是我们可以通过增加两个模板参数 类型的引用(const 和 非const) 、类型的指针(const 和 非const) 来复用普通迭代器，具体实现如下：
// list 迭代器类
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)
{}
}首先我们先将节点类起别名为 Node，再将自己的类起别名为 self；迭代器本身也是一个指针，只是它内部实现不一样，所以我们需要一个 _node 节点的指针，构造函数实例化一个节点的指针，比如说 list<int>::iterator it = lt.begin();，这里的 it 就会调构造函数，实例化一个 lt.begin() 节点的指针，其实 lt.begin() 就是指向头节点的指针。
接着我们重载一些迭代器常用的运算符：
（1）前置++
就是让迭代器往后迭代，具体的实现就是让节点的指针指向下一个节点：
// 前置 ++
self& operator++()
{
_node = _node->_next;
return *this;
}（2）后置++
跟前置++的区别就是，后置++需要拷贝，返回++以前的迭代器，所以一般都不用后置++；
// 后置 ++
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}（3）前置- -、后置- -
前置- -、后置- - 与 ++ 的区别就是， - -返回上一个节点的迭代器；
// 前置 --
self& operator--()
{
_node = _node->_prev;
return *this;
}
// 后置--
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}（4）!= 和 == 运算符重载
!= 运算符重载就是比较它们的节点是否相等；== 运算符就相反；
// != 运算符重载 iterator it != lt.begin();
bool operator!=(const self& s)
{
return s._node != _node;
}
// == 运算符重载 iterator it == lt.begin();
bool operator==(const self& s)
{
return s._node == _node;
}（5）* 解引用重载 和 -> 重载
解引用重载 和 -> 重载 就是改变迭代器指向内容的两个运算符，所以我们定义的三个模板参数，就在这里起作用了；比如我们实例化的模板参数是 const 迭代器 的 __list_iterator<T, const T&, const T*>，这里的 const T& 就是 Ref，const T* 就是 Ptr，这里就可以直接用 Ref （解引用重载）和 Ptr（箭头重载） 作返回值；
如果是 非const 迭代器的 __list_iterator<T, T&, T*>，T& 就是 Ref，T* 就是 Ptr；所以就可以根据它们的类型返回对应的迭代器类型，就不需要我们自己写两个迭代器的类了。
// * 解引用重载
Ref operator*()
{
return _node->_data;
}
// -> 重载
Ptr operator->()
{
return &_node->_data;
}解引用 和 -> 重载的使用：
假设 list 里面存的类型是一个自定义类型，这个自定义类型中有两个成员变量，那么我们在使用 解引用 和 -> 重载的时候，应该访问哪一个呢？这时候就需要我们指定访问了，如下代码：
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{}
int _a1;
int _a2;
};
void test4()
{
Young::list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
Young::list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
// 使用解引用
//cout << (*it)._a1<<" "<<(*it)._a2 << endl;
//使用 ->
cout << it->_a1 << " " << it->_a2 << endl;
++it;
}
cout << endl;
}上面的 cout << it->_a1 << " " << it->_a2 << endl; 调用了->重载，实际上是 cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;，本来应该是有两个 -> 的，即 it->->_a1 但是这样写可读性不好，所以编译器特殊处理，省略了一个 ->。
3. list 反向迭代器类
list 的反向迭代器可以复用 list 的正向迭代器，就不需要我们重新写一个反向迭代器的类了。我们先简单看一下 list 的反向迭代器的使用：
与正向迭代器相反，反向迭代器的 ++ 是倒着走的，反向迭代器的 rbegin 是正向迭代器 end 位置的前一个位置；rend 的位置就是 begin 的前一个位置。
我们先看一下反向迭代器的类：
// list 反向迭代器类
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
typedef ReverseIterator<Iterator, Ref, Ptr> Self;
// 反向迭代器的构造函数
ReverseIterator(Iterator it)
:_it(it)
{}
private:
Iterator _it; // 定义一个类成员为正向迭代器的对象，复用正向迭代器的类
};（1）前置++
反向迭代器的 ++ 是使迭代器从后往前走，我们底层只需要改成 – 即可：
// 前置++
Self& operator++()
{
--_it;
return *this;
}（2）后置++
// 后置++
Self operator++(int)
{
_it--;
return *this;
}（3）前置- -
// 前置--
Self& operator--()
{
++_it;
return *this;
}（4）后置- -
// 后置--
Self operator--(int)
{
_it++;
return *this;
}（5）解引用重载
直接复用正向迭代器的解引用重载即可：
// 解引用重载
Ref operator*()
{
return *_it;
}（6）-> 重载
复用正向迭代器的 -> 重载：
// 箭头重载
Ptr operator->()
{
return _it.operator->();
}（7）== 和 != 重载
bool operator!=(const Self& s)
{
return _it != s._it;
}
bool operator==(const Self& s)
{
return _it == s._it;
}4. list 类
list 类首先将 const 迭代器和非 const 迭代器类型起别名为 const_iterator 和 iterator ，反向迭代器同上；成员变量有 _head 哨兵位节点和 _size 记录链表的长度，如下：
// list 类
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;
// 反向迭代器
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
private:
Node* _head;
size_t _size;
};（1）迭代器
注意，begin() 是哨兵位的下一个节点，end() 是哨兵位节点。
begin() 和 end() 返回的类型也是一个迭代器，这里 iterator(_head->_next) 是调用迭代器类的构造函数，构造一个节点的指针返回；也可以写成 _head->_next，因为支持隐式类型的转换；
// 非 const 反向迭代器
reverse_iterator rbegin()
{
return reverse_iterator(--end());
}
reverse_iterator rend()
{
return reverse_iterator(end());
}
// const 反向迭代器
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(--end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(end());
}
// 非 const 正向迭代器
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
// const 正向迭代器
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}（2）修改相关的接口
swap()
交换链表数据，需要借助标准库的 swap 函数实现：
// 交换链表数据
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}insert()
在 pos 迭代器插入节点；新开一个节点，然后插入指定迭代器的位置，连接好 prev 和 cur 的位置即可；因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的；
// 插入节点
iterator insert(iterator pos, const T& x)
{
Node* newnode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size;
return newnode;
}erase()
删除 pos 迭代器位置的节点；在删除时迭代器会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响，所以 erase() 函数执行后，it 所指向的节点已被删除，因此 it 无效，在下一次使用 it 时，必须先给其赋值；
// 删除节点
iterator erase(iterator pos)
{
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
pos._node->_next = pos._node->_prev = nullptr;
--_size;
return next;
}push_back、push_front、pop_back、pop_front
只需要复用 insert() 和 erase() 即可，实现如下：
// 尾插
void push_back(const T& x)
{
insert(end(), x);
}
// 头插
void push_front(const T& x)
{
insert(begin(), x);
}
// 尾删
void pop_back()
{
erase(--end());
}
// 头删
void pop_front()
{
erase(begin());
}clear()
清空链表数据，删除除了哨兵位的节点即可；
// 清空链表数据
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
} 以上修改接口配合迭代器的使用如下图：
（3）空链表初始化
// 空链表初始化
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}（4）构造函数
构造函数只需要创建一个哨兵位即可；
// 构造函数
list()
{
empty_init();
}（5）拷贝构造函数
拷贝构造函数直接初始化，然后插入数据即可；
// 拷贝构造函数 -- lt2(lt1)
list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}（6）赋值运算符重载
现代写法，传参的时候调用拷贝构造，然后交换数据即可；
// 赋值运算符重载 -- lt2 = lt1
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}（7）析构函数
清空链表数据之后再释放哨兵位的节点即可；
// 析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}4. 打印容器的接口
（1）打印链表整型的接口
像 vector、list 这些容器都没有重载流插入运算符，所以我们可以自己实现一个打印的接口函数；我们先来实现一下打印链表整型的接口：
// 打印链表 -- 只能针对 int 类型
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//*it = 10; error
cout << *it << " ";
++it;
}
cout << endl;
}此接口可以打印链表的数据，但是只能针对 int 类型，我们可以对它进行改造一下，使用模板。
（2）打印 list 的接口
我们学了模板，就可以利用模板实现泛型编程，将类型改为模板的泛型，即可打印 list 中的不同类型，如下：
// 打印链表 -- 只能打印 list 容器
template<typename T>
void print_list(const list<T>& lt)
{
typename list<T>::const_iterator it = lt.begin();
while (it != lt.end())
{
//*it = 10; error
cout << *it << " ";
++it;
}
cout << endl;
}这里的模板参数使用了 typedef 关键字，这里必须使用 typedef 关键字，而且在指定类域前还要加上 typedef 关键字，如 typename list<T>::const_iterator it = lt.begin();；因为在模板还没有进行实例化的时候， const_iterator 就到 list<T> 的类域中寻找类型，此时类中还没有实例化参数 T，所以编译器分不清它是类型还是静态变量，不能去 list<T> 里面找，所以在前面加 typedef 关键字就说明它是个类型，编译器在等 list<T> 实例化后，再去类里面去取根据类型去取类型。
但是上面的接口还是不够完美，要是我想打印 vector 呢？那还是不能打印出来，所以我们可以实现一个专门打印容器的接口；
（3）打印容器的接口
我们使用模板参数代表容器，让编译器到指定容器去取它的迭代器即可；
// 打印容器 -- 能打印各种容器
template<typename container>
void print_container(const container& con)
{
typename container::const_iterator cit = con.begin();
while (cit != con.end())
{
cout << *cit << " ";
++cit;
}
cout << endl;
}使用如下图：
