C++ STL list and slit

栏目: 编程工具 · 发布时间: 6年前

内容简介: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 的链表 实现中的 排序 、反转对于面试中有很多借鉴意义。

本文完

C++ STL list and slit

This work is licensed under a CC A-S 4.0 International License

.


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Defensive Design for the Web

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》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具