内容简介:本部分主要介绍三种容器:他们分别是栈,队列(FIFO), 双端队列(两侧可以出入)。模板参数包括两个:
简介
本部分主要介绍三种容器:
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
的实现。这些都是在页面 的边界时才会调用的代码。
本文完
.
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。