list是双向带头链表。所以迭代器end()相当于哨兵卫的头。
list不支持+和[]重载，原因在于list空间不是连续的，+和[]的代价比较大。
访问第n个节点，只能用for循环，++来实现
list<int> l;
l.push_back(0);
l.push_back(1);
l.push_back(2);
l.push_back(3);
auto li=l.begin();
//访问第3个节点
for(size_t i=0;i<3;i++)
{
li++;
}
list的insert不会失效，但是erase会迭代器失效。
list是双向迭代器
迭代器可以简单分为：单向迭代器(forward)++，双向迭代器(bidirectional) ++/-- 随机迭代器(random acess)+/-/++/--
不同的数据结构的迭代器决定了可以使用不同的算法。其中随机迭代器代器的范围最广，可以用的算法最多。
std:sort只能是随机迭代器用，list不能使用，list也有自己的sort算法但是效率并不高。
list实现
大概思路先不考虑迭代器，链表分为两个类，一个类表示节点，另外一个类表示链表。
节点模板类
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())
:_next(nullptr)
,_prev(nullptr)
,_val(val)
{
}
};这里有个注意的点，模板类的类名不是类型，list_node只是类名，不是对应的自定义类型，所以是
list_node<T>* _next;而不是list_node* _next。
编译器优化
拷贝构造写类名也可以
模拟实现的代码
namespace my_list
{
template<class T>
struct list_node
{
list_node<T>* _prev;
list_node<T>* _next;
T _val;
list_node(const T& val=T())
:_next(nullptr)
,_prev(nullptr)
,_val(val)
{}
};
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->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
Ptr operator->()
{
return &_node->_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;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator const_begin()
{
return _head->_next;
}
const_iterator const_end()
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void push_back(const T& x)
{/*
Node* tail =_head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;*/
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_begin()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
return newnode;
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return next;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
}
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
sz++;
}
return sz;
}
private:
Node* _head;
Node* _tail;
};
}
