C++ STL源码学习之算法篇(五)
or bidirectional iterators. template
_BidirectionalIter1 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag) { typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; _RevIter1 __rlast1(__first1); _RevIter2 __rlast2(__first2); ///使用reverse_iterator查找 _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, _RevIter2(__last2), __rlast2); if (__rresult == __rlast1) return __last1; else { ///找到出现序列的一个元素的位置 _BidirectionalIter1 __result = __rresult.base(); advance(__result, -distance(__first2, __last2)); return __result; } } /// is_heap, a predicate testing whether or not a range is /// a heap. This function is an extension, not part of the C++ /// standard. template
bool __is_heap(_RandomAccessIter __first, _Distance __n) { _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { if (__first[__parent] < __first[__child]) ///子节点不得大于其父节点 return false; if ((__child & 1) == 0) ///__child为偶数 ++__parent; } return true; }