# C++中list的用法实例讲解

## 前言

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

## 一、list的节点

```template
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 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::iterator it = l.begin();
while (it != l.end())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
```

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

```template
struct __list_iterator {
typedef __list_iterator             iterator;
typedef __list_iterator const_iterator;
typedef __list_iterator           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() {}
__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 __list_node
{
public:
__list_node(const T& val = T())//用一个全缺省比较好
:_next(nullptr)
,_pre(nullptr)
,node(val)
{}
public:
__list_node* _next;
__list_node* _pre;
T node;
};

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

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

list相比vector，正因为他们的底层结构不相同，list的迭代器在插入操作和接合操作（splice）都不会造成迭代器失效，只有删除的时候，只有那个被删除元素的迭代器失效，而不影响后面的，而vector就统统失效了。

### 2.3 修改方法

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

template
class __list_itertaor
{
public:
typedef __list_node  Node;
__list_itertaor(Node* node)
{
_node = node;
}

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

template
class list
{
typedef __list_node  Node;
public:
typedef __list_itertaor iterator;
typedef __list_itertaor 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
void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
```

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

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

```void test_list()
{

list l;
l.push_back(5);
list::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;
```