# 前言

list相较于vector来说会显得复杂，它的好处是在任意位置插入,删除都是一个O(1)的时间复杂度。

# 一、list的节点

``````template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};

``````

``````class list  --> list() { empty_initialize();

void empty_initialize() {
node = get_node();
node->next = node;
node->prev = node;
}
``````

# 二、list的迭代器

``````int main()
{
list<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
l.push_back(6);

list<int>::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
``````
• 我们从list< int >当中定义一个iterator对象，然后让他去访问我们的节点
• 并且他所支持的操作有++，解引用，当然还有 --等等

stl3.0当中的迭代器实现：

``````template<class T, class Ref, class Ptr>
struct __list_iterator {
typedef __list_iterator<T, T&, T*>             iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
typedef __list_iterator<T, Ref, Ptr>           self;

typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;

__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}

bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
reference operator*() const { return (*node).data; }

#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

self& operator++() {
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
``````

``````	template<class T>
class __list_node
{
public:
__list_node(const T& val = T())//用一个全缺省比较好
:_next(nullptr)
,_pre(nullptr)
,node(val)
{}
public:
__list_node<T>* _next;
__list_node<T>* _pre;
T node;
};

template<class T>
class __list_itertaor//这里是迭代器
{
public:
typedef __list_node<T>  Node;
__list_itertaor(Node* node)
{
_node = node;
}

bool operator!=(const __list_itertaor<T>& it)
{
return _node != it._node;
}
__list_itertaor<T>& operator++()
{
_node = _node->_next;
return *this;
}
T& operator*()
{
return _node->node;
}
private:
Node* _node;
};
``````

• 我们通过对节点的操作，重载了operator++等接口实现了对一个节点的访问，访问的时候实际上也就是创建迭代器对象，对我们的数据进行访问，所以我们封装的时候是将节点的指针进行封装。
• list相比vector，正因为他们的底层结构不相同，list的迭代器在插入操作和接合操作（splice）`都不会造成迭代器失效`，只有删除的时候，只有那个`被删除元素的迭代器失效`，而不影响后面的，而vector就统统失效了。

## 2.3 修改方法

``````template<class T>
class __list_node
{
public:
__list_node(const T& val = T())//用一个全缺省比较好
:_next(nullptr)
,_pre(nullptr)
,node(val)
{}
public:
__list_node<T>* _next;
__list_node<T>* _pre;
T node;
};

template<class T,class Ref>
class __list_itertaor
{
public:
typedef __list_node<T>  Node;
__list_itertaor(Node* node)
{
_node = node;
}

bool operator!=(const __list_itertaor<T,Ref>& it)
{
return _node != it._node;
}
__list_itertaor<T,Ref>& operator++()
{
_node = _node->_next;
return *this;
}
Ref operator*()//返回Ref，返回值就有区别啦
{
return _node->node;
}
private:
Node* _node;
};

template<class T>
class list
{
typedef __list_node<T>  Node;
public:
typedef __list_itertaor<T,T&> iterator;
typedef __list_itertaor<T, const T&> const_iterator;//修改
iterator begin()
{
return iterator(_node->_next);
}
iterator end()
{
return iterator(_node);
}
const_iterator begin()const
{
return const_iterator(_node->_next);
}
const_iterator end()const
{
return const_iterator(_node);
}
list()
{
_node = new Node;
_node->_next = _node;
_node->_pre = _node;
}
void push_back(const T& val)
{
Node* newnode = new Node(val);
Node* tail = _node->_pre;
tail->_next = newnode;
newnode->_pre = tail;
newnode->_next = _node;
_node->_pre = newnode;
}
private:
Node* _node;
};
``````

–》码云链接《–

# 二、美中不足

list上面说的仿佛都是优点

• 不支持随机访问
• 排序的效率慢，库中的sort用的是归并排序–>快排需要三数取中，对于链表来说实现出来效率也低，所以当链表的元素需要进行排序的时候，我们通常也都会拷贝到vector当中，再用vector当中的排序。
• 同理链表的逆置效率也不高！

# 三、迭代器的分类

• 单向： 单链表迭代器（forward_list）/哈希表迭代器；这些只支持单向++；
• 双向： 双链表迭代器/map迭代器；这些支持的++/- -操作；
• 随机迭代器： string/vector/deque；这些是支持++/- -/+/-操作的，类似原生指针一般。

``````//sort的函数声明
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
``````

``````std::reverse
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
``````

## 3.x std::find的一个报错

``````void test_list()
{

list<int> l;
l.push_back(5);
list<int>::iterator it = std::find(l.begin(), l.end(), 5);
}
``````

stl_list.h当中为迭代器添加了如下声明来解决这个问题。

``````		typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef ptrdiff_t difference_type;
``````

# 总结

list的讲解就到这里啦，看到这里不妨一键三连。

THE END