深入解析：list的学习

1、list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代

2、list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向前一个或后一个元素

3、list与forward_list非常相似，但forward_list只能朝前面迭代

4、list的缺点就是不能随机访问 ，你只能从已知位置（头节点或尾节点遍历过去去找）

list的接口较多

我们去学常见的重要接口

---

list的构造

构造函数（constructor）

list(size_t n,const value_type &val=value_type())            构造的list中包含n个值为val的元素

list()                                       构造空的list

list(const list& x)                       拷贝构造函数

list(inputiterator first,inputiterator last)                 用（first,last）区间中的元素构造list

list iterator的使用

这地方把迭代器暂时理解成指针，该指针指向list中的一个节点

begin+end                    返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器

rbegin+rend                  颠倒过来

---

list capacity

empty               检测list是否为空 ，是返回true,不是返回false

size                返回list中有效节点个数

list element access

front                     返回list的第一个节点中值的引用

back                        返回list的最后一个节点中值的引用

push_front             在list首元素前插入值为val的元素

pop_front              删除list中的第一个元素

push_back            在list尾部插入值为val的元素

pop_back              删除list中最后一个元素

insert              在指定的这个位置插入值val

erase                  删除指定位置的元素

swap                    交换两个list中的元素

clear                     清空list中的有效元素

因为要考虑迭代器失效的可能（在删除时所指向节点的消失）

#include
#include
using namespace std;
void test()
{
int array[] = { 1,2,3,4,5,6,7 };
list l(array, array + sizeof(array) / sizeof(array[0]));
auto it =l.begin();
while (it != l.end())
{
it=l.erase(it);
}
}

反向迭代器

template
class reverseiterator
{
public:
typedef typename iterator::ref   ref;
typedef typename  iterator::ptr  ptr;
typedef  reverseiterator  self;
public:
reverseiterator(iterator it)
:_it(it)
{ }
ref operator*()
{
iterator temp(_it);
--temp;
return *temp;
}
ptr operator->()
{
return &(operator*());
}
self& operator++()
{
--_it;
return *this;
}
self& operator++(int)
{
self temp(*this);
--_it;
return temp;
}
self& operator--()
{
++_it;
return *this;
}
self& operator(int)
{
self temp(*this);
++_it;
return temp;
}
bool operator!=(const self& l)const
{
return _it != l._it;
}
bool operator==(const self& l)const
{
return _it == l._it;
}
iterator _it;
};

vector                                         和                                              list的区别

1、动态顺序表，一段连续空间                                               带头节点的双向循环链表

2、支持随机访问，o(1）                                                        不支持随机访问为，o(n)

3、任意位置插入和删除效率低，需要搬移元素，                       任意位置插入删除效率高，为o(1)

时间复杂 度为O(N)，插入时有可能需要增容，增容：

开辟新空 间，拷贝元素，释放旧空间，导致效率更低

4、原生态指针                                                                          对原生态指针封装

5、在插入元素时，要给所有迭代器重新赋值，                            插入不影响，删除会导致当前迭                                                                                                            代器失效

因为插入元素有可能导致扩容，导致迭代器失效，删除时，

当前迭代器要重新赋值或则失效