SGI STL 标准库 slist 6

github源码分析仓库

slist 单链表


SGI STL提供单向链表(single linked list),slist不在标准规格之内。
slist和list的主要差别:slist迭代器是单向的Forward Iterator,list迭代器是双向的Bidirectional Iterator。slist消耗空间更小,某些操作更快。
slist和list插入、移除、接合等操作不会造成原有迭代器失效。
根据STL的习惯,插入操作会将新元素插入到指定位置之前,而slist由于没有方便的方法回头定位前一个位置,所以在插入新元素时,必须从头找起,效率低下。因此slist不提供push_back(),只提供push_front()

slist节点


slist的节点和迭代器的设计架构

slist的节点和迭代器的设计架构

1
2
3
4
5
6
7
8
9
10
11
12
//单向链表的节点基本结构
struct _Slist_node_base
{
_Slist_node_base* _M_next;
};

//单链表的节点结构
template <class _Tp>
struct _Slist_node : public _Slist_node_base
{
_Tp _M_data;
};

slist迭代器

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
//slist迭代器基本结构
struct _Slist_iterator_base
{
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef forward_iterator_tag iterator_category; //单向

_Slist_node_base* _M_node; //指向节点基本结构

_Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
void _M_incr() { _M_node = _M_node->_M_next; } //前进一个节点

bool operator==(const _Slist_iterator_base& __x) const {
return _M_node == __x._M_node;
}
bool operator!=(const _Slist_iterator_base& __x) const {
return _M_node != __x._M_node;
}
};

//slist迭代器结构
template <class _Tp, class _Ref, class _Ptr>
struct _Slist_iterator : public _Slist_iterator_base
{
typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self;

typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef _Slist_node<_Tp> _Node;

//在调用slist<T>::end()时会造成_Slist_iterator(0)会调用_Slist_iterator(_Node *__x)
_Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}

_Slist_iterator() : _Slist_iterator_base(0) {}
_Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}

reference operator*() const { return ((_Node*) _M_node)->_M_data; }
pointer operator->() const { return &(operator*()); }

_Self& operator++()
{
_M_incr();
return *this;
}
_Self operator++(int)
{
_Self __tmp = *this;
_M_incr();
return __tmp;
}
};

两个list迭代器相等判断会调用__Slist_iterator_base::operator==,根据定义,两个slist迭代器是否相等,根据其__Slist_node_base *node是否相等而定。