内容简介:STL 中提供了单向链表和双向链表。(好像单向链表并没有进入 C++ 标准)支持常见的操作单向链表,顾名思义只能往一个方向去访问:每个节点含有指向下个节点的指针以及本节点所存储的元素。
简介
STL 中提供了单向链表和双向链表。(好像单向链表并没有进入 C++ 标准)
slist list
支持常见的操作
-
push/pop_back
: 双向链表 -
push/pop_front
-
front
-
back
: 双向链表 -
remove
-
reverse
-
unique
-
merge
: 归并两个有序链表 -
sort
: 会单独介绍,链表的 sort 是归并。STL 中的 sort 不适合链表 -
splice
-
splice_after
: 单链表- 这个函数的入参有点奇怪
单链表
单向链表,顾名思义只能往一个方向去访问:每个节点含有指向下个节点的指针以及本节点所存储的元素。
struct _Slist_node_base { _Slist_node_base* _M_next; }; template <class _Tp> struct _Slist_node : public _Slist_node_base { _Tp _M_data; };
单向链表只支持 operator++
,其实现就是移动相关的指针。在单向链表结构中存储的结构 _M_head
实际上 不是真正的头节点。它的下一个节点是头结点,它属于 before_first
。单链表的插入都是在表头:
-
push_front/pop_front
所以如果我们需要构造一个链表的话,有点类似于栈一样,需要方向插入节点。
单向链表结构在面试中会经常遇到,例如单向列表的反转,单向链表的去重和合并。
链表反转
inline _Slist_node_base* __slist_reverse(_Slist_node_base* __node) { _Slist_node_base* __result = __node; __node = __node->_M_next; __result->_M_next = 0; while(__node) { _Slist_node_base* __next = __node->_M_next; __node->_M_next = __result; __result = __node; __node = __next; } return __result; }
链表删除指定元素
这里 _M_head
并不是真正的头节点,这个类似于 dummy 节点的头结点会简化程序。因为我们不需要判断头 节点被删除的场景。
template <class _Tp, class _Alloc> void slist<_Tp,_Alloc>::remove(const _Tp& __val) { _Node_base* __cur = &this->_M_head; while (__cur && __cur->_M_next) { if (((_Node*) __cur->_M_next)->_M_data == __val) | this->_M_erase_after(__cur); else | __cur = __cur->_M_next; } }
链表合并
链表的合并,假定两个链表都是各自有序的。
template <class _Tp, class _Alloc> void slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) { _Node_base* __n1 = &this->_M_head; while (__n1->_M_next && __x._M_head._M_next) { if (((_Node*) __x._M_head._M_next)->_M_data < | ((_Node*) __n1->_M_next)->_M_data) | __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); __n1 = __n1->_M_next; } if (__x._M_head._M_next) { __n1->_M_next = __x._M_head._M_next; __x._M_head._M_next = 0; } }
__slist_splice_after
函数作用是什么呢?
其作用是将 _first
, _before_last
之间的元素插入到 __pos
位置, 然后元素拼接起来
__pos->__first->__before_last->__pos.next
这个函数的入参有一点奇怪,不是正常的节点,而节点的上一个节点。STL 中所有区间的描述都是左闭右开的 [first, last)
,这里的 __before_first
应该是某个 slist
的 _M_head
,因为程序把它的下游指向 了 __last
节点
inline void __slist_splice_after(_Slist_node_base* __pos, | | | | | | | |_Slist_node_base* __before_first, | | | | | | | |_Slist_node_base* __before_last) { if (__pos != __before_first && __pos != __before_last) { _Slist_node_base* __first = __before_first->_M_next; _Slist_node_base* __after = __pos->_M_next; __before_first->_M_next = __before_last->_M_next; __pos->_M_next = __first; __before_last->_M_next = __after; } } inline void __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) { _Slist_node_base* __before_last = __slist_previous(__head, 0); if (__before_last != __head) { _Slist_node_base* __after = __pos->_M_next; __pos->_M_next = __head->_M_next; __head->_M_next = 0; __before_last->_M_next = __after; } }
单链表排序
slist __counter[64]
__counter[0]
存储一个节点, __counter[1]
存储两个节点, __counter[n]
存储 2^n
次方个节点。 每次都从原始的节点列表中合并掉 2^n
个节点。
具体执行流程:
__slist_splice_after __counter[0]
例如当前状态 __counter[2]
中存储了 4 个节点, __counter[0]
和 __counter[1]
都是空。这个时候会 先去填满 __counter[0]
,然后填满 __counter[1]
,清空 __counter[0]
,然后填满 __counter[0]
,这个 时候再到达一个节点,会不断往上合并, __counter
状态是 [1,2,4,0,0...0]
。然后会不断合并,最终生成 [0,0,0,8,0...0]
template <class _Tp, class _Alloc> void slist<_Tp,_Alloc>::sort() { if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { slist __carry; slist __counter[64]; int __fill = 0; while (!empty()) { | __slist_splice_after(&__carry._M_head, | | | | | | &this->_M_head, this->_M_head._M_next); | int __i = 0; | while (__i < __fill && !__counter[__i].empty()) { | __counter[__i].merge(__carry); | __carry.swap(__counter[__i]); | ++__i; | } | __carry.swap(__counter[__i]); | if (__i == __fill) | ++__fill; } for (int __i = 1; __i < __fill; ++__i) | __counter[__i].merge(__counter[__i-1]); this->swap(__counter[__fill-1]); } }
双向链表
双向链表相对于单向链表,增加了前向的节点,支持的移动方式会增加一种,向前向后都可以。
struct _List_node_base { _List_node_base* _M_next; _List_node_base* _M_prev; }; template <class _Tp> struct _List_node : public _List_node_base { _Tp _M_data; };
双向链表也有一个 dummy 节点,这个 dummy 节点再最开始时指向自己,所以 empty()
的实现如下:
bool empty() const { return _M_node->_M_next == _M_node; }
<<STL 源码剖析>>中说,这个会节约一个 Node 的存储空间
splice
void splice(iterator __position, list& __x) void splice(iterator __position, list&, iterator __i) void splice(iterator __position, list&, iterator __first, iterator __last)
主要依赖 transfer
实现, transfer
功能是要将 __position
位置的元素替换为 [__first, __last]
。 这个过程中维护 __position
和 __first
、 __last
前序和后序之间的关系。
void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { /* Remove [first, last) from its old position. */ __last._M_node->_M_prev->_M_next = __position._M_node; __first._M_node->_M_prev->_M_next = __last._M_node; __position._M_node->_M_prev->_M_next = __first._M_node; /* Splice [first, last) into its new position. */ _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } }
总结
STL 中很多通用的算法是不能直接用在链表上。一般这些算法会要求 random_access_iterator
。STL 的链表 实现中的 排序 、反转对于面试中有很多借鉴意义。
本文完
.
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Defensive Design for the Web
37signals、Matthew Linderman、Jason Fried / New Riders / 2004-3-2 / GBP 18.99
Let's admit it: Things will go wrong online. No matter how carefully you design a site, no matter how much testing you do, customers still encounter problems. So how do you handle these inevitable bre......一起来看看 《Defensive Design for the Web》 这本书的介绍吧!