C++学习指南(六)----list
欢迎来到繁星的CSDN。本期内容主要包括，list的介绍、使用以及与vector的优缺点。 
一、什么是list
在先前的C语言学习中，我们接触到了顺序表和链表，而在C++中，这正好对应了vector（动态增长顺序表）和list（链表）。所以本期的内容实质上仍然是与链表相关的封装、重载函数等。
list和之前说的string、vector一样，属于container（容器），作为STL库里的常客，list的出场为我们的链表提供的简易的使用方法。但是很可惜的是，我们的二叉树等链表的变形却不能直接使用。原因是list实质上是带头双向链表。（HEAD节点和其余节点结构一致，但是在list内为空时，该节点不销毁，只是为空）
二、list的接口
list的接口比之list而言更有序，但数量仍然十分众多。
具体查看网址如下：
cplusplus.com/reference/list/list/
构造constructor
explicit list ();//默认构造
explicit list (size_type n);//传值构造
list (size_type n, const value_type& val);//传值构造
template <class InputIterator> list (InputIterator first, InputIterator last);//区间构造
list (const list& x);//拷贝构造
文档中还有其他重载函数，以及以上展示的构造函数中，我已将有关空间配置器的内容省去（因为大部分情况下我们只需要使用STL原生的配置器就可以了）。
实际上我们可以发现，list的构造函数和vector的构造函数差别不大。
销毁destructor
~list();和我们熟悉的销毁方式没有什么区别。实际上就是将链表中的动态申请部分释放，并将相关成员变量置空。而且由于这是STL库内的部分而非自定义类型需要我们自己实现，当程序结束的时候，将会自动调用销毁函数，所以无需担心。
赋值重载operator=
list& operator= (const list& x); 
经过实践检验得知，当我们使用=赋值另一个list的时候，两者的地址不同，所以这是深拷贝，无需担心先前的list销毁导致复制出来的list同时销毁。
迭代器iterator
list的迭代器我们可以暂时理解为指针。
#include<iostream>
#include<list>
using namespace std;
int main() {
int array[] = { 1,2,3,4,0,5,6,7,8,9 };
int n = sizeof(array) / sizeof(int);
list<int> mylist(array, array + n);
auto it = mylist.begin();
*it = 0;
for (int a : mylist) {
cout << a << endl;
}
return 0;
}（这里偷偷使用了auto来偷懒，实际写可以写为list::iterator)
之前提过，迭代器的出现就是为了封装，减少记忆成本。
所以这里的it仍然可以实现，++，--，*这几个方式。
++就是到下一个节点，--就是返回上一个节点，*就是解引用。
与迭代器相关的接口如下：
begin()，end() //正向迭代器
rbegin()，rend() //反向迭代器
cbegin()，cend() //const正向迭代器
crbegin()，crend() //const反向迭代器
但是有一点比较麻烦，list不再支持[ ]，也就是随机访问。
原因在于，底层的链表实现随机访问的代价太大，即使list的底层是带头双向链表，由于物理储存空间的不连续性，最坏情况也可以达到O(n/2)。
容器大小capacity
empty();
size();
max_size();
相比vector，list的capacity变成了max_size，这是因为链表某一结点的空间都是单独申请，所以不存在可容纳空间这一概念，取代capacity的是max_size，代表可供使用的空间大小，这取决于系统，而非自己申请。
访问方式access
front();
back();
front与back分别是整个list的头与尾，可以通过这两个直接得到。
成员函数member function
void push_front (const value_type& val);
void push_back (const value_type& val);
void pop_front();
void pop_back();
//对单个元素进行操作
iterator erase (const_iterator position);//删除单个元素
iterator erase (const_iterator first, const_iterator last);//删除区间内的元素
iterator insert (const_iterator position, const value_type& val);
iterator insert (const_iterator position, size_type n, const value_type& val);
//在某一位置插入一个或多个同一元素
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);
//在某一位置插入另一容器的部分元素对list的相关函数操作，实际上和vector差别不大，当然C++11还支持了emplace_back，emplace_front，emplace，这分别对应push_back,push_front,insert。不过对于左值引用而言，效率一样，对于右值引用（这里未书写，仅仅是将参数类型变成右值），emplace的效率更高。
当然list的相关函数还有很多，感兴趣的可以看：
cplusplus.com/reference/list/list/
三、list和vector的优劣与不可替代性
说起list，就不能不提到与vector的优劣势，以及是否可以被替代。
list和vector的优劣取决于他们的储存方式。vector是由一段连续的物理空间储存，而list是不必使用连续空间储存，却不支持随机访问。
| vector | list | |
| 底层结构 | 动态顺序表、连续物理空间 | 带头双向链表 |
| 随机访问 | 支持 | 不支持 |
| 插入与删除 | 尾端效率高，其余位置需要挪动元素，效率不高 | 任意位置效率均高，O(1) |
| 空间利用率 | 空间利用率高、缓存利用率高 | 空间利用率低、缓存利用率低 |
| 迭代器 | 原生指针 | 对原生指针进行封装 |
| 迭代器失效 | 插入时如发生扩容，迭代器失效，删除时当前迭代器失效 | 插入不会导致失效，删除时仅当前迭代器失效 |
| 使用场景 | 需要高效储存、需要随机访问，不需要大量插入删除操作 | 大量插入删除操作 |
四、list的模拟实现
namespace show
{
// List的节点类
template<class T>
struct ListNode
{
T _val;
ListNode<T>* _pPre;
ListNode<T>* _pNext;
ListNode(const T& val = T())
:_val(val)
,_pNext(nullptr)
,_pNext(nullptr)
{}
;
};
//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)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self& operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
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;
iterator begin()
{
return _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();
}
list(initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
return newnode;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
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;
--_size;
return next;
}
size_t size() const
{
return _size;
}
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
};
本篇内容到此结束，谢谢大家的观看！
觉得写的还不错的可以点点关注，收藏和赞，一键三连。
我们下期再见~
往期栏目：
C++学习指南（一）——C++入门基础_c++ 学习指南-CSDN博客
C++学习指南（二）——类和对象-CSDN博客
C++学习指南（三）——模板_模板类-CSDN博客
C++学习指南(四)------string-CSDN博客
C++学习指南（五）——vector_erwei vector bianliangchushihua-CSDN博客