C++ STL源代码学习(map,set内部heap篇)
2023-09-14 09:10:25 时间
stl_heap.h
///STL中使用的是大顶堆 /// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. template <class _RandomAccessIterator, class _Distance, class _Tp> void __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __topIndex, _Tp __value) { _Distance __parent = (__holeIndex - 1) / 2; ///逐层上溯,查找要插入的位置 while (__holeIndex > __topIndex && *(__first + __parent) < __value) { *(__first + __holeIndex) = *(__first + __parent); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } ///找到位置,插入 *(__first + __holeIndex) = __value; } template <class _RandomAccessIterator, class _Distance, class _Tp> inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Distance*, _Tp*) { __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), _Tp(*(__last - 1))); } template <class _RandomAccessIterator> inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); __push_heap_aux(__first, __last, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } template <class _RandomAccessIterator, class _Distance, class _Tp, class _Compare> 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)) { *(__first + __holeIndex) = *(__first + __parent); __holeIndex = __parent; __parent = (__holeIndex - 1) / 2; } *(__first + __holeIndex) = __value; } template <class _RandomAccessIterator, class _Compare, class _Distance, class _Tp> inline void __push_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Distance*, _Tp*) { __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), _Tp(*(__last - 1)), __comp); } template <class _RandomAccessIterator, class _Compare> inline void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __push_heap_aux(__first, __last, __comp, __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); } ///将__holeIndex处的结点摘掉,并保持合法的大顶堆状态,然后插入__value ///运行此函数前,必须保证以__holeIndex为根节点构成的全然二叉树符合大顶堆的定义 template <class _RandomAccessIterator, class _Distance, class _Tp> void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value) { _Distance __topIndex = __holeIndex; _Distance __secondChild = 2 * __holeIndex + 2; ///向下遍历,从__holeIndex中找出两个孩子中较大的一个填入__holeIndex,并令__holeIndex ///等于该孩子,继续运行,直至__holeIndex无孩子或者仅仅有一个孩子(为了占被摘取的那个节点的位置) while (__secondChild < __len) { if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) __secondChild--; *(__first + __holeIndex) = *(__first + __secondChild); __holeIndex = __secondChild; __secondChild = 2 * (__secondChild + 1); } if (__secondChild == __len) { ///__holeIndex仅仅有一个孩子,补充上去 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); __holeIndex = __secondChild - 1; } ///至此,大顶堆合法,插入__value __push_heap(__first, __holeIndex, __topIndex, __value); } template <class _RandomAccessIterator, class _Tp, class _Distance> inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Distance*) { ///该函数并未删除弹出的那个元素,而仅仅是将它移动到最后面 *__result = *__first; __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); } template <class _RandomAccessIterator, class _Tp> inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) { __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator> inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); __pop_heap_aux(__first, __last, __VALUE_TYPE(__first)); } template <class _RandomAccessIterator, class _Distance, class _Tp, class _Compare> void __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, _Distance __len, _Tp __value, _Compare __comp) { _Distance __topIndex = __holeIndex; _Distance __secondChild = 2 * __holeIndex + 2; while (__secondChild < __len) { if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) __secondChild--; *(__first + __holeIndex) = *(__first + __secondChild); __holeIndex = __secondChild; __secondChild = 2 * (__secondChild + 1); } if (__secondChild == __len) { *(__first + __holeIndex) = *(__first + (__secondChild - 1)); __holeIndex = __secondChild - 1; } __push_heap(__first, __holeIndex, __topIndex, __value, __comp); } template <class _RandomAccessIterator, class _Tp, class _Compare, class _Distance> inline void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __result, _Tp __value, _Compare __comp, _Distance*) { *__result = *__first; __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value, __comp); } template <class _RandomAccessIterator, class _Tp, class _Compare> inline void __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*, _Compare __comp) { __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp, __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator, class _Compare> inline void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); } template <class _RandomAccessIterator, class _Tp, class _Distance> void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; ///因为__adjust_heap的要求,必须从最底层開始逐层向上调整. _Distance __parent = (__len - 2)/2; ///此时它的两个孩子分别为__len-1,len while (true) { __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent))); if (__parent == 0) return; __parent--; } } template <class _RandomAccessIterator> inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); __make_heap(__first, __last, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator, class _Compare, class _Tp, class _Distance> void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _Tp*, _Distance*) { if (__last - __first < 2) return; _Distance __len = __last - __first; _Distance __parent = (__len - 2)/2; while (true) { __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)), __comp); if (__parent == 0) return; __parent--; } } template <class _RandomAccessIterator, class _Compare> inline void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __make_heap(__first, __last, __comp, __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); } template <class _RandomAccessIterator> void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type, _LessThanComparable); ///因为pop_heap函数并未正真将结点删除,此函数得以实现 while (__last - __first > 1) pop_heap(__first, __last--); } template <class _RandomAccessIterator, class _Compare> void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator); while (__last - __first > 1) pop_heap(__first, __last--, __comp); }
相关文章
- C++ map用法总结(整理)
- c++ auto类型_auto C++
- C++算法与数据结构之map
- C++ 实现线程安全的map(OpenHarmony源码实现版)
- 读取QQ ClientKey C++版本[通俗易懂]
- Map的有序性_有序的map集合有哪些
- unordered_map/unordered_set/unorder_multiset/unorder_multimap-C++容器
- 《安富莱嵌入式周报》第294期:将C/C++代码转换为各种高级语言,超炫渲染着色器,VS2022新闻插件,基于以太网的开源步进电机控制器,Arduino PLC
- c++的链表-C++链表
- 数据结构小记【Python/C++版】——AVL树篇
- 【C++修炼之路】18.map和set
- C++面试必备:常见C++面试题汇总及详细解析
- C++运算符的重载详解编程语言
- C++ map插入数据(STL map插入数据)详解
- C++ map(STL map)构造元素(emplace和emplace_hint函数)详解
- 为什么C++ map容器emplace()、emplace_hint()的执行效率比insert()高?
- Redis有序Map:高效有序排列的利器(redis有序map)
- 查询Redis中Map的广泛应用(查询redis的map)
- 集Oracle中存储Map集的新方法(oracle保存map)
- 科学上网如何使用Oracle MAP(oracle map使用)
- c++判断奇数偶数实例介绍
- c/c++输出重定向的方法
- 基于C++map中key使用指针问题的详解
- 浅析C++中cout的运行机制
- C++实现图形界面时钟表盘代码
- VC++的combobox控件用法汇总