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++基础 文章被收录于专栏
C/C++ 语言基础
顺丰集团工作强度 276人发布