一、标准库中的list类
1.1 list类介绍
- list的底层是一个带哨兵位的双向循环链表结构
- 对比forward_list的单链表结构，list的迭代器是一个双向迭代器
- 与vector等顺序结构的容器相比，list在任意位置进行插入删除的效率更好，但是不支持任意位置的随机访问
list是一个模板类，在使用的时候我们需要给出元素的类型
使用list类时，需要包含头文件<list>
1.2 list的常用接口
1.2.1 常用的构造函数
list();
list类的默认构造函数，构造一个空链表
例如：
list(size_type n, const value_type& val = value_type());
构造一个list对象并用n个val初始化
例如：
list(const list& x);
list类的拷贝构造函数
例如：
Template<class InputIterator>
list(InputIterator first, InputIterator last);
使用迭代器进行初始化构造
例如：
1.2.2 容量操作接口
（1）size
size_type size() const;
获取链表节点个数
例如：
（2）empty
bool empty() const;
判断链表是否为空
例如：
（3）resize
void resize(size_type n, value_type val = value_type());
缩减或增加节点个数为n
如果没有给出val，就用0作为元素
例如：
1.2.3 访问和遍历
（1）迭代器
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
迭代器，用于获取链表中第一个节点的位置和最后一个节点的下一个位置（即哨兵位）
例如：
（2）反向迭代器
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
反向迭代器，rbegin获取容器中最后一个节点的位置，rend获取容器中哨兵位的位置
例如：
需要注意，反向迭代器rit也要用++而不是--
（3）back
reference back();
const_reference back() const;
返回链表中最后一个节点存储的数据的引用
例如：
（4）front
reference front();
const_reference front() const;
返回链表中第一个节点存储的数据的引用
例如：
1.2.4 list的增删查改
（1）push_front
void push_front(const value_type& val);
从链表头部插入一个元素
例如：
（2）pop_front
void pop_front();
从链表头部删除一个元素
例如：
（3）push_back
void push_back(const value_type& val);
从链表尾部插入一个元素
例如：
（4）pop_back
void pop_back();
从链表尾部删除一个元素
例如：
（5）find
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);
在两个迭代器区间寻找val并返回其所在处的迭代器
例如：
需要注意的是，该函数并非list的成员函数，是标准库中的函数，多个容器共用该find函数
可以看到，我们可以直接对list的迭代器进行解引用并修改其内容，但是迭代器不应该指向节点吗？为什么对其解引用能修改数据呢？
实际上list的迭代器并不是用原生态指针进行模拟实现的，需要进行底层的封装，这里会在list的模拟实现的源代码中体现。
（6）insert
iterator insert(iterator position, const value_type& val);
void insert(iterator position, size_type n, const value_type& val);
————————————————————————————————————————
template<class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
在position位置的前面插入一个或多个元素
例如：
细心的读者可能已经发现了，list的insert操作是不会导致迭代器失效的，因为pos指向的节点不变，相对位置也不变。
但是list的删除操作一定会导致迭代器失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
（7）erase
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
删除position位置的元素或者 [first，last) 区间的所有元素
例如：
（8）swap
void swap(vector& x);
交换两个list对象
例如：
（9）assign
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const value_type& val);
为list指定新内容，替换其当前内容并修改节点个数
例如：
（10）clear
void clear();
删除链表所有节点
例如：
1.2.5 list的顺序修改接口
（1）sort
void sort();
template<class Compare>
void sort(Compare comp);
list由于结构的特殊性，是无法使用标准库中的sort函数的，因为迭代器无法进行相减的操作
并且在C++文档中，我们可以看到标准库中的sort也限定了迭代器的类型必须是可以进行随机访问（RandomAccess）的
迭代器有几个功能分类：
- 单向迭代器，只能进行++
- 双向迭代器，可以++和--
- 随机迭代器，可以++，--，+和-
但是list的sort函数也是没什么必要的，因为直接对链表排序的效率比拷贝到vector进行排序再拷贝回链表要慢的多
（2）reverse
void reverse();
对链表进行逆置
例如：
二、模拟实现list类
学习了list类中各种常用接口的用法后，我们就可以开始自己手撕一个自己的list类了
为了不和标准库中的list类冲突，我们可以开一个自己的命名空间
#include <iostream>
#include <assert.h>
using namespace std;
namespace Eristic
{
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x = T()) //匿名对象作为缺省值，变为默认构造函数
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
template<class T, class Ref, class Ptr>
//通过模板参数实现const迭代器和普通迭代器版本的复用
//和list类中迭代器的typedef配合阅读会较好理解
struct __list_iterator //重点：迭代器的底层封装
{
typedef list_node<T> node;
typedef __list_iterator<T, Ref, Ptr> self;
node* _node;
//node*本身不支持解引用等操作，对其进行封装就可以模仿原生态指针的行为
__list_iterator(node* n)
:_node(n)
{}
Ref& operator*()
{
return _node->_data;
}
Ptr operator->() //误区：在使用箭头运算符的时候，为什么只需要一个箭头而不是两个？
//答：为了可读性，编译器会帮助我们省略一个箭头
{
return &_node->_data;
}
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& s)
{
return _node != s._node;
}
bool operator==(const self& s)
{
return _node == s._node;
}
//不需要写拷贝构造，因为我们用默认生成的进行浅拷贝就能完成需求
//析构函数也不需要写，释放节点是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;
//对应上面的多个模板参数
void list_init()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
list_init();
}
list(int n, const T& x = T())
{
list_init();
for (int i = 0; i < n; i++)
push_back(x);
}
template<class iterator>
list(iterator first, iterator last)
{
list_init();
while (first != last)
{
push_back(*first);
++first;
}
}
list(const list<T>& lt)
{
list_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
list<T>& operator=(const list<T> lt)
{
swap(lt);
return *this;
}
int size()
{
iterator it = begin();
int count = 0;
while (it != end())
{
++it;
++count;
}
return count;
}
void resize(size_t n, const T& x = T())
{
if (n < size())
while (n < size())
pop_back();
else if (n > size())
while (n > size())
push_back(x);
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
T& front()
{
return _head->_next->_data;
}
const T& front() const
{
return _head->_next->_data;
}
T& back()
{
return _head->_prev->_data;
}
const T& back() const
{
return _head->_prev->_data;
}
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());
}
void insert(iterator pos, const T& x)
{
node* cur = pos._node;
node* prev = cur->_prev;
node* newnode = new node(x);
cur->_prev = newnode;
newnode->_next = cur;
prev->_next = newnode;
newnode->_prev = prev;
}
iterator erase(iterator pos)
{
assert(pos != end()); //哨兵位不能删
node* prev = pos._node->_prev;
node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
return iterator(next);
}
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}
void clear()
{
iterator it = begin();
while (it != end())
{
erase(it++);
}
}
private:
node* _head;
};
}如有错误，欢迎在评论区指出
完.
