list
面试题：为什么会有list？
vector缺点:
- vector头部和中部插入删除数据效率低，需要挪动数据O(N)
- vector插入数据空间不够需要增容，会付出很大代价（开新空间，拷贝数据，释放就空间）
优点：支持下标随机访问，间接支持排序，二分查找，堆算法等
list优点：
- list头部和中部插入删除数据不需要挪动，效率高O(1)
- list插入数据是新增结点，不需要增容
缺点：不支持随机访问
vector和list两个容器是相辅相成的
支持操作接口的角度分迭代器类型：单向(forwoard_list) 双向(list) 随机(vector可以直接加 it+3)
使用场景分迭代器：正向迭代 反向迭代
iteator
iterator ++it 向右走 –it向左走
reverse_iterator ++rit 向左走 –rit向右走
//[begin,end) 找不到3返回最后一个结点下一位
list<int> :: iterator pos = find(it.begin(),it.end(),3);
insert()和 erase()
list和vector底层物理结构不一样，导致插入后，迭代器位置发生变化
对于list erase()后会导致迭代器失效，位置变了导致失效
对于vector insert()和erase()后都会导致迭代器位置不对，所以失效
解决办法
it = list.erase(it);
list实现
// List的节点类
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:
_pPre(nullptr)
,
,
{}
_pNext(nullptr)
_val(val)
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
};
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;
}
