C++ STL stack, queue and deque

简介

本部分主要介绍三种容器：

stack
queue
deque

他们分别是栈，队列（FIFO）, 双端队列（两侧可以出入）。

栈

模板参数包括两个：

_Tp
_Sequence

stack 这是一个简单的包装，它主要实现接口如下：

• top : 返回栈顶的元素， _Sequence.back()
• empty : 判断栈是否是空， _Sequence 同名方法
• push : 向栈中压入元素， _Sequence.push_back()
• pop : 删除栈顶元素， _Sequence.pop_back()
• size : 返回栈中元素个数， _Sequence 同名方法

这些都是依赖它所对应的 _Sequence 来实现的。默认的 _Sequence 是后面介绍的双端队列 deque

队列

队列和栈一样，也是一个 wrapper 。它也是对它所使用的 _Sequence 接口进行封装适配。

• front
• back
• push : _Sequence.push_back()
• pop : _Sequence.pop_front()
• empty
• size

队列默认的 _Sequence 是 deque 。

双端队列

栈和队列在默认情况都是使用 deque 来作为其实际的存储容器。 deque 作为双端队列，其可以在头和尾部 进行元素的插入和删除，都是 O(1) 的复杂度(通常情况下，不考虑内存扩张时的复制)。

deque 的内存管理

内存管理类似于操作系统的分页（当然比操作操作系统的段页式是弱的）。在 _Deque_iterator 中：

_M_cur
_M_first
_M_last
_M_node

当移动节点跨越边界时，会调用下述函数来进行页面的切换：

void _M_set_node(_Map_pointer __new_node) {
  _M_node = __new_node;
  _M_first = *__new_node;
  _M_last = _M_first + difference_type(_S_buffer_size());
}

注意在边界操作时， _M_cur 的变化：

• 往后移动时，先移动 ++_M_cur ，然后判断是否跨页，然后设置 _M_cur = _M_first
• 往前移动时, 先判断是否跨页，然后 --_M_cur

我们通过几个比较有意思的移动来看下分页管理上的一些复杂度：

求两个 iterator 之间的距离 operator- ：

• this 所在 iterator 位于 __x 的后面
  • 直观理解
• this 所在 iterator 位于 __x 的前面
  • 这个时候，第一部分是个负值，会发现有多减掉部分指针，所以加回去

difference_type operator-(const _Self& __x) const {
  return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
      (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
}

快速移动 iterator ， operator+= : 移动时需要注意当跨越 page 时需要重新设置存储 Map 对应的节点。

_Self& operator+=(difference_type __n)
{
  difference_type __offset = __n + (_M_cur - _M_first);
  if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
      _M_cur += __n;
  else {
      difference_type __node_offset =
          __offset > 0 ? __offset / difference_type(_S_buffer_size())
          : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
      _M_set_node(_M_node + __node_offset);
      _M_cur = _M_first +
          (__offset - __node_offset * difference_type(_S_buffer_size()));
  }
  return *this;
}

erase : 先判断哪部分元素少，然后再决定元素的移动， erase 的删除是 O(n)

iterator erase(iterator __pos) {
  iterator __next = __pos;
  ++__next;
  difference_type __index = __pos - _M_start;
  if (size_type(__index) < (this->size() >> 1)) {
    copy_backward(_M_start, __pos, __next);
    pop_front();
  }
  else {
    copy(__next, _M_finish, __pos);
    pop_back();
  }
  return _M_start + __index;
}

感兴趣地可以看下 _M_push_back_aux 、 _M_push_front_aux 和 _M_insert_aux 的实现。这些都是在页面 的边界时才会调用的代码。

本文完

.

• ← Previous Post