函数 max_elements 求 __first 到 __last 之间最大的元素。如果有多个最大元素则取第一个元素。
template <class _ForwardIter>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_LessThanComparable);
if (__first == __last) return __first;
_ForwardIter __result = __first;
while (++__first != __last)
if (*__result < *__first)
__result = __first;
return __result;
}
函数 min_elements 求 __first 到 __last 之间的最小元素，如果有多个最小元素则取第一个元素。
template <class _ForwardIter>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_LessThanComparable);
if (__first == __last) return __first;
_ForwardIter __result = __first;
while (++__first != __last)
if (*__first < *__result)
__result = __first;
return __result;
}
函数 next_permutation 用来检测 __first 到 __last 组成的元素序列是否存在下一个全排列。
函数从最尾部的一个元素开始向前查找，找到第一个比它的下一个位置的元素小的元素，令 __i 是第一个满足比它的下一个元素小的元素，令 __ii 是它的下一个元素。令 __j 是 __last 的前一个元素所在的位置，然后 __j 不断的向前移动，直到 __j 所在位置的元素大于 __i 所在位置的元素 (__j 不会移动到超过 __ii ，因为 __ii 所在的位置上的元素要比 __i 所在位置的元素大)。
然后交换 __i 和 __j 所在位置的元素。因为交换之前 __i 所在位置的元素 比 __j 之后的元素都大(__j 所在位置的元素是从 __last - 1 开始往前第一个比__i 所在位置的元素大的元素)。而且 __i 所在位置的元素比 __ii 到 __j 之间的元素都要小(__j 比 __ii 到其之前位置之间的元素都要小，而 __i 所在位置的元素比 __j 所在位置的元素要小)。因此交换之后 __ii 到 __last 之间的元素是逆序排列的，在将这个逆序在逆序一遍，使其变成顺序，则就得到了下一个全排列，如果这样的全排列是存在的，则返回 true ，否则返回 false 。
template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
__STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
__STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
_LessThanComparable);
if (__first == __last)
return false;
_BidirectionalIter __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;) {
_BidirectionalIter __ii = __i;
--__i;
if (*__i < *__ii) {
_BidirectionalIter __j = __last;
while (!(*__i < *--__j))
{}
iter_swap(__i, __j);
reverse(__ii, __last);
return true;
}
if (__i == __first) {
reverse(__first, __last);
return false;
}
}
}
函数 prev_permutation 用来判断 __first 到 __last 之间的元素组成的序列的上一个全排列是否存在。
函数从位置 __last - 1 开始往前查找，找到第一个比它的下一个元素要大的元素，令 __i 是第一个满足条件的元素所在的位置， __ii 是其下一个位置。令 __j 从 __last - 1 的位置开始向前移动，直到 __j 所在位置的元素比 __i 要小。
则此时 __i 所在位置的元素同样比 __ii 到 __j 之间的元素要大，因__j 所在位置的元素要比 __ii 到 __j 之间的元素要大，而 __i 所在位置的元素比 __j 所在位置的元素要大，所以 __i 所在位置的元素要比 __ii 到 __j 之间的元素要大，同样因为 __j 是从 __last - 1 开始第一个比 __i 所在位置的元素要小的元素所在的位置，因此它之后的元素应该都比 __i 所在位置的元素要大。
此时交换 __i 所在位置的元素和 __j 所在位置的元素，交换之后，__i 所在位置之后的元素是以升序排列的，将这个升序序列逆序，则所得的序列就是当前 __first 到 __last 之间的元素序列的上一个全排列，如果这样的全排列存在，则返回 true ，否则返回 false 。
template <class _BidirectionalIter>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
__STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator);
__STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type,
_LessThanComparable);
if (__first == __last)
return false;
_BidirectionalIter __i = __first;
++__i;
if (__i == __last)
return false;
__i = __last;
--__i;
for(;;) {
_BidirectionalIter __ii = __i;
--__i;
if (*__ii < *__i) {
_BidirectionalIter __j = __last;
while (!(*--__j < *__i))
{}
iter_swap(__i, __j);
reverse(__ii, __last);
return true;
}
if (__i == __first) {
reverse(__first, __last);
return false;
}
}
}
函数 find_first_of 查找从 __first1 开始到 __last1 第一次出现 __first2 到 __last2 之间的元素的位置。直接用两层 for 循环进行蛮力搜索。
template <class _InputIter, class _ForwardIter>
_InputIter find_first_of(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2)
{
__STL_REQUIRES(_InputIter, _InputIterator);
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,
typename iterator_traits<_InputIter>::value_type,
typename iterator_traits<_ForwardIter>::value_type);
for ( ; __first1 != __last1; ++__first1)
for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
if (*__first1 == *__iter)
return __first1;
return __last1;
}
函数 __find_end 用来查找 __first2 到 __last2 组成的元素序列是否出现在 __first1 到 __last1 之间。如果出现了，则返回它最后一次出现的位置。函数直接调用 search 函数来实现查找。
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
_ForwardIter2 __first2, _ForwardIter2 __last2,
forward_iterator_tag, forward_iterator_tag)
{
if (__first2 == __last2)
return __last1;
else {
_ForwardIter1 __result = __last1;
while (1) {
_ForwardIter1 __new_result
= search(__first1, __last1, __first2, __last2);
if (__new_result == __last1)
return __result;
else {
__result = __new_result;
__first1 = __new_result;
++__first1;
}
}
}
}
函数 __find_end 查找 __first2 到 __last2 组成的元素序列是否存在于 __first1 到 __last1 组成的元素序列中，如果在，则返回其最后一次出现的位置。
因为迭代器类型为 bidirectional_iterator。因此用 __first1 和 __last1 构造反向迭代器得到 __first1 到 __last1 组成的序列的一个逆序，同样的方式得到 __first2 到 __last2 组成的序列的一个逆序，用 search 函数查找 __first2 到 __last2 的逆序是否出现在 __first1 到 __last1 的逆序中，如果出现，则由它逆序第一次出现的位置可以计算出原始序列最后一次出现的位置。因此整个查找过程只需要调用一次 search 函数。
template <class _BidirectionalIter1, class _BidirectionalIter2>
_BidirectionalIter1
__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
_BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
bidirectional_iterator_tag, bidirectional_iterator_tag)
{
__STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator);
__STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator);
typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
_RevIter1 __rlast1(__first1);
_RevIter2 __rlast2(__first2);
_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 用来判断 __first 到 __last 的序列是否组成一个最大堆。
template <class _RandomAccessIter, class _Distance>
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)
++__parent;
}
return true;
}
函数 __is_sorted 用来判断 __first 到 __last 的序列是否是有序的。
template <class _ForwardIter>
bool is_sorted(_ForwardIter __first, _ForwardIter __last)
{
__STL_REQUIRES(_ForwardIter, _ForwardIterator);
__STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,
_LessThanComparable);
if (__first == __last)
return true;
_ForwardIter __next = __first;
for (++__next; __next != __last; __first = __next, ++__next) {
if (*__next < *__first)
return false;
}
return true;
}
STL 的 算法 (algo) 分析（一）</br> STL 的 算法 (algo) 分析（二）</br> STL 的 算法 (algo) 分析（三）</br> STL 的 算法 (algo) 分析（四）</br> STL 的 算法 (algo) 分析（五）</br> STL 的 算法 (algo) 分析（六）</br> STL 的 算法 (algo) 分析（七）</br> STL 的 算法 (algo) 分析（八）</br>