STLC++STLSTL-list链表
HappyLadySauceSTL-list链表实现
STL中采用双向带头循环链表来实现 list，下面将使用 C++ 实现 STL list 链表。
list 类中包含两个主要部分，一个是指向哨兵位头节点的指针（_head），另一个是结构体类型的迭代器（__list_iterator）。
哨兵位头节点本身是不存储数据的，它只是用于简化代码实现操作的，让 list 的头插尾插更加的方便。在 list 中通过指向哨兵位头节点的指针（_head）用于链接节点，实现高效快速地访问头（_next）和尾（_prev）。
在 string 和 vector 中我们可以通过指针++访问下一个元素，这是因为它们俩都是顺序存储是一片连续不断的内存空间，自然地可以实现指针++访问下一个元素。所以它们俩的迭代器基本就是原生指针套了一个壳子叫 iterator 以配合STL的统一设计。
但是如果想实现遍历 list 容器，单靠指针++访问下一个元素是实现不了的，因为链表很灵活，每个节点的内存空间并不一定连续，所以不能单靠指针++访问下一个元素是做不到的。但是为了实现迭代器++访问下一个元素我们得对 list 的迭代器进行特殊的封装，以实现迭代器++访问下一个元素的操作。
节点模型
首先我们先来了解 list 的节点模型，list 中链接着许多的节点，每个节点都是一个节点模型的实现。都具有前后指针（_prev 和 _next），和一个数据值（_val）。
1
2
3
4
5
6
7
8
9
10
11
12
13
| template <typename T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())
:_val(val)
,_next(nullptr)
,_prev(nullptr)
{}
};
|
迭代器模型
下面我来详细解释一下 list 的迭代器模型。为了实现通过迭代器访问 list 节点的成员，我们需要在迭代器中封装 list_node 也就是节点模型。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
Ptr operator->()
{
return &_node->_val;
}
};
|
然后你会发现接下来你就看不懂了 typedef __list_iterator<T, Ref, Ptr> self; 一个迭代器要这么多模板参数干嘛使的？这是为 const 迭代器做铺垫，Ref 和 Ptr 都是用来区分是否使用 const 修饰函数的返回值。
1
2
| typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
|
下面我给出完整的 list 迭代器模型实现，迭代器内访问节点数据都是通过指向节点的指针 _node 来进行访问，迭代器的 ++ 和 -- 也是通过修改 _node 节点模型内的前后指针（_prev 和 _next）来实现的，并不是直接使用的**指针++、指针–**。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| 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;
}
Ptr operator->()
{
return &_node->_val;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
};
|
list 模型
了解完节点模型和迭代器模型，再来看 list 模型简直是轻松加愉快，不用多说都了解七七八八了。我就简单讲几个主要的函数，但是这里给出完整的 list 实现，方便大家进行全面的阅读。也可以跳过这一大段代码，看我解释完一些函数再回过头来学习。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
| template <typename 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 begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
list()
{
empty_init();
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
void push_back(const T& val)
{
insert(end(), val);
}
void push_front(const T& val)
{
insert(begin(), val);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
size_t size() const
{
return _size;
}
void swap(list<T> lt)
{
std::swap(_size, lt._size);
std::swap(_head, lt._head);
}
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
++_size;
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;
--_size;
return next;
}
void clear()
{
iterator it = begin();
while(it != end())
{
it = erase(it);
}
_size = 0;
}
private:
Node* _head;
size_t _size;
};
|
了解一个类，首先我们需要了解的是它的成员变量。list 中只存储哨兵位头节点，它具有标准的节点模型，还有一个 _size 用来方便计数链表的长度。
然后我们了解迭代器相关的内容：begin() 和 end()。哨兵位头节点的前面就是**尾 end()，后面就是头 begin()**。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
|
接下来我们需要了解一下 list 的默认成员函数。但是这部分没什么好看的，大家自行了解吧。
最后我再解释一下 list 的插入数据，其实也很简单。insert 函数用于在 pos 位置之前插入一个数据，我们首先需要得到 pos 位置的节点，然后得到它的前一个节点方便进行后续的链接。最后，前一个节点的 _next 指向新节点，新节点的 _prev 指向前一个节点；pos 位置节点的 _prev 指向新节点，新节点的 _next 指向 pos 位置的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
cur->_prev = newnode;
newnode->_next = cur;
++_size;
return newnode;
}
|
看到这里，我相信你对STL中的 list 链表底层实现应该不陌生了。也不是那么复杂对吧，但是我这个是简化版，STL源码的 list 实现比这复杂得多，更多的封装还有内存池的调用。
