C++ STL 容器 -- stack/queue
8、stack/queue/priority_queue
这三者确切来讲,并不属于 STL 的容器,而是容器适配器:将容器封装成特定接口。
8.1、stack
stack 是栈数据结构,遵循先进后出(First in last out, FILO),有入栈和出栈两个操作,默认使用 std::deque 实现,入栈和出栈也是直接操作 deque 的接口。
/// stl_stack.h template<typename _Tp, typename _Sequence = deque<_Tp> > class stack { public: typedef typename _Sequence::value_type value_type; typedef typename _Sequence::reference reference; typedef typename _Sequence::const_reference const_reference; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; protected: // See queue::c for notes on this name. _Sequence c; /* ...*/ };
入栈 push() 函数调用 deque 的 push_back() 函数,将元素插入到 deque 末尾;出栈 pop() 调用 deque 的 pop_back() 函数,取出末尾(最新插入)元素。
/// stl_stack.h _GLIBCXX_NODISCARD bool empty() const { return c.empty(); } _GLIBCXX_NODISCARD size_type size() const { return c.size(); } _GLIBCXX_NODISCARD reference top() { __glibcxx_requires_nonempty(); return c.back(); } void push(const value_type& __x) { c.push_back(__x); } #if __cplusplus >= 201103L void push(value_type&& __x) { c.push_back(std::move(__x)); } #if __cplusplus > 201402L template<typename... _Args> decltype(auto) emplace(_Args&&... __args) { return c.emplace_back(std::forward<_Args>(__args)...); } #else template<typename... _Args> void emplace(_Args&&... __args) { c.emplace_back(std::forward<_Args>(__args)...); } #endif #endif void pop() { __glibcxx_requires_nonempty(); c.pop_back(); }
8.2、queue
queue 是队列数据结构,遵循先进先出(First in first out, FIFO),有入队和出队两个操作,默认使用 std::deque 实现,入队和出队也是直接操作 deque 的接口。
/// stl_queue.h template<typename _Tp, typename _Sequence = deque<_Tp> > class queue { public: typedef typename _Sequence::value_type value_type; typedef typename _Sequence::reference reference; typedef typename _Sequence::const_reference const_reference; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; protected: /// @c c is the underlying container. _Sequence c; /* ...*/ };
入队 push() 直接调用 deque::push_back() 函数,将元素插入到 deque 末尾;出队 pop() 调用 deque::pop_front() 函数,取出 deque 的第一个元素。
/// stl_queue.h _GLIBCXX_NODISCARD reference front() { __glibcxx_requires_nonempty(); return c.front(); } _GLIBCXX_NODISCARD const_reference front() const { __glibcxx_requires_nonempty(); return c.front(); } _GLIBCXX_NODISCARD reference back() { __glibcxx_requires_nonempty(); return c.back(); } _GLIBCXX_NODISCARD const_reference back() const { __glibcxx_requires_nonempty(); return c.back(); } void push(const value_type& __x) { c.push_back(__x); } #if __cplusplus >= 201103L void push(value_type&& __x) { c.push_back(std::move(__x)); } #if __cplusplus > 201402L template<typename... _Args> decltype(auto) emplace(_Args&&... __args) { return c.emplace_back(std::forward<_Args>(__args)...); } #else template<typename... _Args> void emplace(_Args&&... __args) { c.emplace_back(std::forward<_Args>(__args)...); } #endif #endif void pop() { __glibcxx_requires_nonempty(); c.pop_front(); }
8.3、priority_queue
prority_queue 是优先队列,每次出队都返回队列中“最小”元素(也可以是最大,用户可以传入比较器),默认使用 vector 容器。
为了高效地找到队列中最小元素,priority_queue 借助 vector 容器,维护一个”堆“的数据结构,插入元素后破坏堆结构后,需要调整以维持堆的特性。
/// stl_queue.h template<typename _Tp, typename _Sequence = vector<_Tp>, typename _Compare = less<typename _Sequence::value_type> > class priority_queue { public: typedef typename _Sequence::value_type value_type; typedef typename _Sequence::reference reference; typedef typename _Sequence::const_reference const_reference; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 2684. priority_queue lacking comparator typedef typedef _Compare value_compare; protected: // See queue::c for notes on these names. _Sequence c; _Compare comp; /* ... */ };
构造函数中构造堆
/// stl_queue.h template<typename _InputIterator, typename = std::_RequireInputIter<_InputIterator>> priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x = _Compare()) : c(__first, __last), comp(__x) { std::make_heap(c.begin(), c.end(), comp); }
入队 push() 和 出队 pop() 分别调用 push_heap() 和 pop_heap() 函数,向堆中插入一个元素,和从堆删除一个元素。
/// stl_queue.h void push(const value_type& __x) { c.push_back(__x); std::push_heap(c.begin(), c.end(), comp); } void pop() { __glibcxx_requires_nonempty(); std::pop_heap(c.begin(), c.end(), comp); c.pop_back(); }
8.4、heap
STL 并没有提供 heap 数据结构,而是提供了函数接口,可以用于构造 heap,向 heap 插入和从 heap 中删除元素。
首先堆是一棵完全二叉树,并且有大顶堆和小顶堆之分。大顶堆每个节点都不小于其左右子树的值,而小顶堆每个节点都不大于其左右子树的值。
下面基于分析小顶堆分析堆的操作。向小顶堆插入或者从小顶堆删除一个元素时,使得剩余部分不再维持小顶堆特性,可以通过 DownHeap 和 UpHead 调整,使得重新成为小顶堆,并且整个过程可以在 O(lgN) 的时间内完成。
下面是 DownHeap 示例:将左右子树节点最小值和自己交换,直到叶子节点或者满足了小顶堆特性。
下面是 UpHeap 操作示例:如果小于父节点,就和父节点交换,直到根节点或者已经满足小顶堆特性。
从头开始创建一个小顶堆也是重复使用 DownHeap 操作:从最后一个非叶子开始,直到叶子节点,对于每个节点都执行 DownHeap 调整。
heap 一般使用数组存储,如果从 0 开始,对于索引为 index 的节点
- 父节点索引为 (index - 1) / 2
- 左子树 index * 2 + 1
- 右子树 index * 2 + 2,或者 (index + 1) * 2
- 最后一个非叶子节点 (len - 2) / 2
8.4.1、make_heap
std::make_heap() 函数用于将 [first, last) 区间构造成堆。make_heap() 函数接受比较器 comp,如果没有指定,默认使用 less 语义比较器。make_heap() 函数之间调用 __make_heap() 函数。
/// stl_heap.h template<typename _RandomAccessIterator> _GLIBCXX20_CONSTEXPR inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive(__first, __last); __gnu_cxx::__ops::_Iter_less_iter __comp; std::__make_heap(__first, __last, __comp); } template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive_pred(__first, __last, __comp); typedef __decltype(__comp) _Cmp; __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); std::__make_heap(__first, __last, __cmp); }
__make_heap() 函数从最后一个非叶子节点开始,对每个节点都调用 __adjust_heap() 函数处理,直到到达根节点。__adjust_heap() 起始就是 DownHeap 操作,后面会做介绍。
/// stl_heap.h template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; if (__last - __first < 2) // 只有一个元素,不需要调整 return; const _DistanceType __len = __last - __first; _DistanceType __parent = (__len - 2) / 2; while (true) { _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent)); std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value), __comp); if (__parent == 0) // 到达根节点,返回 return; __parent--; // 下一个非叶子节点 } }
8.4.2、push_heap
sts::push_heap() 将 [first, last) 重新调整为堆。[first, last) 区间的元素需要满足,[first, last-1) 区间已经是堆,新插入的元素在 last-1 的位置上。push_heap() 函数将新插入,使用 UpHead 操作,将整个 [first, last) 都调整为堆。
/// stl_haep.h template<typename _RandomAccessIterator> _GLIBCXX20_CONSTEXPR inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_heap(__first, __last - 1); __gnu_cxx::__ops::_Iter_less_val __comp; _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), _GLIBCXX_MOVE(__value), __comp); } template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_heap_pred(__first, __last - 1, __comp); __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) __cmp(_GLIBCXX_MOVE(__comp)); _ValueType __value = _GLIBCXX_MOVE(*(__last - 1)); std::__push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), _GLIBCXX_MOVE(__value), __cmp); }
make_heap() 直接调用 __push_heap() 函数,参数含义
- first:[first, last) 区间
- holeIndex:新插入元素位置索引
- topIndex:根节点索引
- value:新插入元素值
- comp:比较器
__push_heap() 函数就是实现 UpHeap 操作:如果小于父节点,就和父节点交换,直到根节点或者已经满足堆特性。
/// stl_heap.h template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare> _GLIBCXX20_CONSTEXPR void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value, _Compare& __comp) { _Distance __parent = (__holeIndex - 1) / 2; // 父节点 while (__holeIndex > __topIndex && __comp(__first + __parent, __value)) { // parent 小于 value,和 parent 交换 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); __holeIndex = __parent; // 递归调整 __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = _GLIBCXX_MOVE(__value); }
8.4.3、pop_heap
std::pop_heap() 用于从堆中删除 first 元素,pop_heap() 返回后,[first, last-1) 是新的堆,last-1 就是被删除的元素。
/// stl_heap.h */ template<typename _RandomAccessIterator> _GLIBCXX20_CONSTEXPR inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_non_empty_range(__first, __last); __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_heap(__first, __last); if (__last - __first > 1) { --__last; __gnu_cxx::__ops::_Iter_less_iter __comp; std::__pop_heap(__first, __last, __last, __comp); } } template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_non_empty_range(__first, __last); __glibcxx_requires_heap_pred(__first, __last, __comp); if (__last - __first > 1) { typedef __decltype(__comp) _Cmp; __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); --__last; std::__pop_heap(__first, __last, __last, __cmp); } }
pop_heap() 直接调用的是 __pop_heap() 函数。__pop_heap() 参数含义
- first/last:[first, last) 表示需要重新调整的区间
- result:删除元素存放位置
- comp:比较器
从堆中删除 first 元素的方法是:将 first 和 last-1 元素交换,然后对于新的 first 元素执行 DownHeap 操作。
/// stl_heap.h template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Compare& __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; typedef typename iterator_traits<_RandomAccessIterator>::difference_type _DistanceType; _ValueType __value = _GLIBCXX_MOVE(*__result); *__result = _GLIBCXX_MOVE(*__first); std::__adjust_heap(__first, _DistanceType(0), _DistanceType(__last - __first), _GLIBCXX_MOVE(__value), __comp); }
__adjust_heap() 就是实现 DownHeap 调整:将左右子树节点最小值和自己交换,直到叶子节点或者满足了堆特性。
/// stl_heap.h template<typename _RandomAccessIterator, typename _Distance, typename _Tp, typename _Compare> _GLIBCXX20_CONSTEXPR void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value, _Compare __comp) { const _Distance __topIndex = __holeIndex; _Distance __secondChild = __holeIndex; while (__secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); if (__comp(__first + __secondChild, __first + (__secondChild - 1))) __secondChild--; // 左右子树两者最小,和父节点交换 *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); __holeIndex = __secondChild; } if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2) { // len 为偶数,特殊处理,最后一个非叶子节点只有左子树 __secondChild = 2 * (__secondChild + 1); *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + (__secondChild - 1))); __holeIndex = __secondChild - 1; } __decltype(__gnu_cxx::__ops::__iter_comp_val(_GLIBCXX_MOVE(__comp))) __cmp(_GLIBCXX_MOVE(__comp)); std::__push_heap(__first, __holeIndex, __topIndex, _GLIBCXX_MOVE(__value), __cmp); }
8.4.4、sort_heap
std::sort_heap() 是堆排序实现。
/// stl_heap.h template<typename _RandomAccessIterator> _GLIBCXX20_CONSTEXPR inline void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept< typename iterator_traits<_RandomAccessIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive(__first, __last); __glibcxx_requires_heap(__first, __last); __gnu_cxx::__ops::_Iter_less_iter __comp; std::__sort_heap(__first, __last, __comp); } template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR inline void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_irreflexive_pred(__first, __last, __comp); __glibcxx_requires_heap_pred(__first, __last, __comp); typedef __decltype(__comp) _Cmp; __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp)); std::__sort_heap(__first, __last, __cmp); }
__sort_heap() 就是重复调用 __pop_heap() 函数,每次将最小元素放到正确的位置。
/// stl_heap.h template<typename _RandomAccessIterator, typename _Compare> _GLIBCXX20_CONSTEXPR void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { while (__last - __first > 1) { --__last; std::__pop_heap(__first, __last, __last, __comp); } }
欢迎关注公众号“源知源为”,阅读更多技术干货
#23届找工作求助阵地##C++#C/C++ 语言基础