STL algorithm（转）
snowman 发表于 2007-03-08 16:33:37
/*
The young Library
Copyright (c) 2005 by 杨桓
Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
/*
基础算法: min, max, swap, *gcd, *median
复制算法: copy *copy_n copy_backward *copy_backward_n *copy_if *copy_range
比较算法: equal lexicographical_compare mismatch *matching
填充算法: fill, fill_n
线性查找算法: find, find_if, adiancent_find, find_first_of,
*find_all, *find_all_if
子序列匹配算法: search, find_end, search_n
计算元素个数算法: count, count_if
最大值与最小值算法: min_element, max_element
互换算法: iter_swap, swap_ranges
遍历区间算法: for_earch, generate, generate_n, transform
替换元素算法: replace, replace_if, replace_copy, replace_copy_if
移除元素算法: remove, remove_if, remove_copy, remove_copy_if,
unique, unique_copy
排列算法: reverse, reverse_copy, rotate, rotate_copy,
prev_permutation, next_permutation
分割算法: partition, stable_partition
随机重排与抽样算法: random_shuffle, *random_sample, *random_sample_n
二分查找算法: lower_bound, upper_bound, equal_range, binary_search
区间合并算法: merge, *merge_backward, inplace_merge
区间集合算法: includes, set_union, set_intersection, set_difference,
set_symmetric_difference
排序算法: *is_sorted, sort, stable_sort, partial_sort, partial_sort_copy,
nth_element
堆算法: push_heap, pop_heap, make_heap, sort_heap, *is_heap
*/
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_ALGORITHM_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_ALGORITHM_HEADER_FILE__
//-----------------------------------------------------------------------------
#include <cstdlib> //rand()函数
#include "y_temp_buffer.hpp"
#include "algorithm/y_algorithm_base.hpp"
#include "algorithm/y_algorithm_compare.hpp"
#include "algorithm/y_algorithm_copy.hpp"
#include "algorithm/y_algorithm_fill.hpp"
#include "algorithm/y_algorithm_heap.hpp"
#include "algorithm/y_algorithm_lower_bound.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename T >
T gcd( T m, T n ) //求最大公因数
{
while( n != 0 )
{
T x = m % n;
m = n;
n = x;
}
return m;
}
template< typename T >
const T& median( const T& a, const T& b, const T& c ) //求中间值
{
if( a < b )
{
if( b < c ) //a < b < c
return b;
else if( a < c ) //a < b && c <= b
return c;
else
return a;
}
else if( a < c ) //a >= b
return a;
else if( b < c ) //a >=b && a >=c
return c;
else
return b;
}
template< typename T, typename StrictWeakOrdering >
const T& median( const T& a, const T& b, const T& c,
StrictWeakOrdering comp )
{
if( comp(a, b) )
{
if( comp(b, c) )
return b;
else if( comp(a, c) )
return c;
else
return a;
}
else if( comp(a, c) )
return a;
else if( comp(b, c) )
return c;
else
return b;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 线性查找算法
//
// find find_if adiancent_find find_first_of find_all find_all_if
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename InputIterator, typename T >
inline InputIterator find( InputIterator first, InputIterator last,
const T& value )
{
typedef typename iterator_traits<InputIterator>::iterator_category cate;
return find_aux( first, last, value, cate() );
}
template< typename InputIterator, typename T >
InputIterator find_aux( InputIterator first, InputIterator last,
const T& value, input_iterator_tag )
{
while( first != last && *first != value )
++first;
return first;
}
template< typename InputIterator, typename T >
InputIterator find_aux( InputIterator first, InputIterator last,
const T& value, random_access_iterator_tag )
{
typedef typename iterator_traits<InputIterator>::difference_type diff_t;
diff_t n = last - first;
while( n > 0 && *first != value )
{
--n;
++first;
}
return first;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename UnaryPredicate >
inline InputIterator find_if( InputIterator first, InputIterator last,
UnaryPredicate pred )
{
typedef typename iterator_traits<InputIterator>::iterator_category cate;
return find_aux( first, last, pred, cate() );
}
template< typename InputIterator, typename UnaryPredicate >
InputIterator find_if_aux( InputIterator first, InputIterator last,
UnaryPredicate pred, input_iterator_tag )
{
while( first != last && !pred(*first) )
++first;
return first;
}
template< typename InputIterator, typename UnaryPredicate >
InputIterator find_if_aux( InputIterator first, InputIterator last,
UnaryPredicate pred, random_access_iterator_tag )
{
typedef typename iterator_traits<InputIterator>::difference_type diff_t;
diff_t n = last - first;
while( n > 0 && !pred(*first) )
{
--n;
++first;
}
return first;
}
//-----------------------------------------------------------------------------
//寻找[first, last)中第一次出现相邻值相等的位置
template< typename ForwardIterator >
inline
ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last )
{
typedef typename iterator_traits<ForwardIterator>::iterator_category cate;
if( first == last )
return last;
else
return ad_find_aux( first, last, cate() );
}
template< typename ForwardIterator >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
forward_iterator_tag )
{
ForwardIterator next = first;
++next;
for( ; next != last; ++next )
{
if( *first == *next )
return first;
else
first = next;
}
return last;
}
template< typename ForwardIterator >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
random_access_iterator_tag )
{
typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;
ForwardIterator next = first;
++next;
for( diff_t n = last - first; n > 0; --n,++next )
{
if( *first == *next )
return first;
else
first = next;
}
return last;
}
template< typename ForwardIterator, typename BinaryPredicate >
inline
ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last,
BinaryPredicate bin_pred )
{
typedef typename iterator_traits<ForwardIterator>::iterator_category cate;
if( first == last )
return last;
else
return ad_find_aux( first, last, bin_pred, cate() );
}
template< typename ForwardIterator, typename BinaryPredicate >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
BinaryPredicate bin_pred,
forward_iterator_tag )
{
ForwardIterator next = first;
++next;
for( ; next != last; ++next )
{
if( bin_pred(*first, *next) )
return first;
else
first = next;
}
return last;
}
template< typename ForwardIterator, typename BinaryPredicate >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
BinaryPredicate bin_pred,
random_access_iterator_tag )
{
typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;
ForwardIterator next = first;
++next;
for( diff_t n = last - first; n > 0; --n,++next )
{
if( bin_pred(*first, *next) )
return first;
else
first = next;
}
return last;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename ForwardIterator >
InputIterator find_first_of( InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2 )
{
for( ; first1 != last1; ++first1 )
{
for( ForwardIterator temp = first2; temp != last2; ++temp )
{
if( *first1 == *temp )
return first1;
}
}
return last1;
}
template< typename InputIterator, typename ForwardIterator,
typename BinaryPredicate >
InputIterator find_first_of( InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate bin_pred )
{
for( ; first1 != last1; ++first1 )
{
for( ForwardIterator temp = first2; temp != last2; ++temp )
{
if( bin_pred(*first1, *temp) )
return first1;
}
}
return last1;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename T, typename OutputIterator >
OutputIterator find_all( InputIterator first,
InputIterator last,
OutputIterator result_first,
OutputIterator result_last,
const T& value )
{
for( ; first != last && result_first != result_last; ++first )
{
if( *first == value )
{
*result_first = first;
++result_first;
}
}
return result_first;
}
template< typename InputIterator, typename Container, typename T >
void find_all( InputIterator first, InputIterator last, Container& result,
const T& value )
{
typename Container::iterator itr1 = result.begin();
typename Container::iterator itr2 = result.end();
for( ; first != last; ++first )
{
if( *first == value )
{
if( itr1 != itr2 )
{
*itr1 = first;
++itr1;
}
else
result.push_back( first );
}
}
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator,
typename UnaryPredicate >
OutputIterator find_all_if( InputIterator first,
InputIterator last,
OutputIterator result_first,
OutputIterator result_last,
UnaryPredicate pred )
{
for( ; first != last && result_first != result_last; ++first )
{
if( pred(*first) )
{
*result_first = first;
++result_first;
}
}
return result_first;
}
template< typename InputIterator, typename Container, typename UnaryPredicate >
void find_all_if( InputIterator first, InputIterator last, Container& result,
UnaryPredicate pred )
{
typename Container::iterator itr1 = result.begin();
typename Container::iterator itr2 = result.end();
for( ; first != last; ++first )
{
if( pred(*first) )
{
if( itr1 != itr2 )
{
*itr1 = first;
++itr1;
}
else
result.push_back( first );
}
}
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 子序列匹配算法
//
// search find_end search_n
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//[first2, last2)是否包含于[first1, last1)
template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 )
{
typedef typename iterator_traits<ForwardIterator1>::difference_type
diff_t1;
typedef typename iterator_traits<ForwardIterator2>::difference_type
diff_t2;
diff_t1 len1 = distance( first1, last1 );
diff_t2 len2 = distance( first2, last2 );
if( len1 < len2 )
return last1;
ForwardIterator1 current1 = first1;
ForwardIterator2 current2 = first2;
while( current2 != last2 )
{
if( *current1 == *current2 )
{
++current1;
++current2;
}
else //遇到不相等时的处理
{
if( len1 == len2 ) //此时first1再前进则len1<len2，匹配失败
return last1;
else
{
current1 = ++first1; //first1前进一个位置，重新开始匹配
current2 = first2;
--len1;
}
}
}
return first1;
}
template< typename ForwardIterator1, typename ForwardIterator2,
typename BinaryPredicate >
ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate bin_pred )
{
typedef typename iterator_traits<ForwardIterator1>::difference_type
diff_t1;
typedef typename iterator_traits<ForwardIterator2>::difference_type
diff_t2;
diff_t1 len1 = distance( first1, last1 );
diff_t2 len2 = distance( first2, last2 );
if( len1 < len2 )
return last1;
ForwardIterator1 current1 = first1;
ForwardIterator2 current2 = first2;
while( current2 != last2 )
{
if( bin_pred(*current1, *current2) )
{
++current1;
++current2;
}
else
{
if( len1 == len2 )
return last1;
else
{
current1 = ++first1;
current2 = first2;
--len1;
}
}
}
return first1;
}
//-----------------------------------------------------------------------------
//在 [first1, last1) 中查找 [first2, last2)
template< typename ForwardIterator1, typename ForwardIterator2 >
inline ForwardIterator1
find_end( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 )
{
typedef typename iterator_traits<ForwardIterator1>::iterator_category
cate1;
typedef typename iterator_traits<ForwardIterator2>::iterator_category
cate2;
if( first1 == last1 || first2 == last2 )
return last1;
else
return find_end_aux( first1, last1, first2, last2, cate1(), cate2() );
}
template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
forward_iterator_tag, forward_iterator_tag )
{
ForwardIterator1 result = last1;
while( 1 )
{
ForwardIterator1 new_result = search( first1, last1, first2, last2 );
if( new_result == last1 )
return result;
else
{
result = new_result;
first1 = new_result;
++first1;
}
} //end while
}
template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
bidirectional_iterator_tag, bidirectional_iterator_tag )
{
typedef Reverse_Iterator<ForwardIterator1> r_iter1;
typedef Reverse_Iterator<ForwardIterator2> r_iter2;
r_iter1 rlast1( first1 );
r_iter2 rlast2( first2 );
//反向匹配的第一个即为正向的最后一个
r_iter1 rresult = search( r_iter1(last1), rlast1, r_iter2(last2), rlast2 );
if( rresult = rlast1 )
return last1;
else
{
ForwardIterator1 result = rresult.base();
advance( result, -distance(first2, last2) ); //前进到匹配子序列的开头
return result;
}
}
template< typename ForwardIterator1, typename ForwardIterator2,
typename BinaryPredicate >
inline ForwardIterator1
find_end( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate bin_pred )
{
typedef typename iterator_traits<ForwardIterator1>::iterator_category
cate1;
typedef typename iterator_traits<ForwardIterator2>::iterator_category
cate2;
if( first1 == last1 || first2 == last2 )
return last1;
else
return find_end_aux( first1, last1, first2, last2, bin_pred,
cate1(), cate2() );
}
template< typename ForwardIterator1, typename ForwardIterator2,
typename BinaryPredicate >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate bin_pred,
forward_iterator_tag, forward_iterator_tag )
{
ForwardIterator1 result = last1;
while( 1 )
{
ForwardIterator1 new_result = search( first1, last1, first2, last2,
bin_pred );
if( new_result == last1 )
return result;
else
{
result = new_result;
first1 = new_result;
++first1;
}
}
}
template< typename ForwardIterator1, typename ForwardIterator2,
typename BinaryPredicate >
ForwardIterator1
find_end_aux( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate bin_pred,
bidirectional_iterator_tag, bidirectional_iterator_tag )
{
typedef Reverse_Iterator<ForwardIterator1> r_iter1;
typedef Reverse_Iterator<ForwardIterator2> r_iter2;
r_iter1 rlast1( first1 );
r_iter2 rlast2( first2 );
r_iter1 rresult = search( r_iter1(last1), rlast1, r_iter2(last2), rlast2,
bin_pred );
if( rresult = rlast1 )
return last1;
else
{
ForwardIterator1 result = rresult.base();
advance( result, -distance(first2, last2) );
return result;
}
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator, typename Integer, typename T >
ForwardIterator search_n( ForwardIterator first, ForwardIterator last,
Integer count, const T& value )
{
if( count < 1 )
return first;
first = find( first, last, value ); //找到第一个要查找的值
while( first != last )
{
Integer n = count - 1;
ForwardIterator itr = first;
++itr;
while( itr != last && n != 0 && *i == value ) //向后进行迭代并比较
{
++itr;
--n;
}
if( n == 0 )
return first;
else
first = find( itr, last, value );
}
return last;
}
template< typename ForwardIterator, typename Integer, typename T,
typename BinaryPredicate >
ForwardIterator search_n( ForwardIterator first, ForwardIterator last,
Integer count, const T& value,
BinaryPredicate bin_pred )
{
if( count < 1 )
return first;
while( first != last )
{
if( binary_pred(*first, value) )
break;
++first;
}
while( first != last )
{
Integer n = count - 1;
ForwardIterator itr = first;
++itr;
while( itr != last && n != 0 && bin_pred(*i, value) )
{
++itr;
--n;
}
if( n == 0 )
return first;
else
{
while( itr != last )
{
if( binary_pred(*itr, value) )
break;
++itr;
}
first = itr;
}
}
return last;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 计算元素个数算法
//
// count count_if
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename InputIterator, typename T >
inline typename iterator_traits<InputIterator>::difference_type
count( InputIterator first, InputIterator last, const T& value )
{
typedef typename iterator_traits<InputIterator>::iterator_category cate;
return count_aux( first, last, value, cate() );
}
template< typename InputIterator, typename T >
typename iterator_traits<InputIterator>::difference_type
count_aux( InputIterator first, InputIterator last, const T& value,
input_iterator_tag )
{
typename iterator_traits<InputIterator>::difference_type count = 0;
for( ; first != last; ++first )
{
if( *first == value )
++count;
}
return count;
}
template< typename InputIterator, typename T >
typename iterator_traits<InputIterator>::difference_type
count_aux( InputIterator first, InputIterator last, const T& value,
random_access_iterator_tag )
{
typename iterator_traits<InputIterator>::difference_type count = 0;
typename iterator_traits<InputIterator>::difference_type n = last - first;
for( ; n > 0; --n,++first )
{
if( *first == value )
++count;
}
return count;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename UnaryPredicate >
inline typename iterator_traits<InputIterator>::difference_type
count_if( InputIterator first, InputIterator last, UnaryPredicate pred )
{
typedef typename iterator_traits<InputIterator>::iterator_category cate;
return count_if_aux( first, last, pred, cate() );
}
template< typename InputIterator, typename UnaryPredicate >
typename iterator_traits<InputIterator>::difference_type
count_if_aux( InputIterator first, InputIterator last, UnaryPredicate pred,
input_iterator_tag )
{
typename iterator_traits<InputIterator>::difference_type count = 0;
for( ; first != last; ++first )
{
if( pred(*first) )
++count;
}
return count;
}
template< typename InputIterator, typename UnaryPredicate >
typename iterator_traits<InputIterator>::difference_type
count_if_aux( InputIterator first, InputIterator last, UnaryPredicate pred,
random_access_iterator_tag )
{
typename iterator_traits<InputIterator>::difference_type count = 0;
typename iterator_traits<InputIterator>::difference_type n = last - first;
for( ; n > 0; --n,++first )
{
if( pred(*first) )
++count;
}
return count;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 最大值与最小值算法
//
// min_element max_element
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename ForwardIterator >
ForwardIterator min_element( ForwardIterator first, ForwardIterator last )
{
if( first == last )
return first;
ForwardIterator result = first;
for( ; first != last; ++first )
{
if( *first < *result )
result = first;
}
return result;
}
template< typename ForwardIterator, typename StrictWeakOrdering >
ForwardIterator min_element( ForwardIterator first, ForwardIterator last,
StrictWeakOrdering comp )
{
if( first == last )
return first;
ForwardIterator result = first;
for( ; first != last; ++first )
{
if( comp(*first, *result) )
result = first;
}
return result;
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last )
{
if( first == last )
return first;
ForwardIterator result = first;
for( ; first != last; ++first )
{
if( *result < *first )
result = first;
}
return result;
}
template< typename ForwardIterator, typename StrictWeakOrdering >
ForwardIterator max_element( ForwardIterator first, ForwardIterator last,
StrictWeakOrdering comp )
{
if( first == last )
return first;
ForwardIterator result = first;
for( ; first != last; ++first )
{
if( comp(*result, *first) )
result = first;
}
return result;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 互换算法
//
// iter_swap swap_ranges
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename ForwardIterator1, typename ForwardIterator2 >
inline void iter_swap( ForwardIterator1 lhs, ForwardIterator2 rhs )
{
typename iterator_traits<ForwardIterator1>::value_type temp = *lhs;
*lhs = *rhs;
*rhs = temp;
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator1, typename ForwardIterator2 >
inline
ForwardIterator2 swap_ranges( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2 )
{
typedef typename iterator_traits<ForwardIterator1>::iterator_category cate;
return swap_r_aux( first1, last1, first2, cate() );
}
template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator2 swap_r_aux( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2,
forward_iterator_tag )
{
for( ; first1 != last1; ++first1,++first2 )
iter_swap( first1, first2 );
return first2;
}
template< typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator2 swap_r_aux( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2,
random_access_iterator_tag )
{
typedef typename iterator_traits<ForwardIterator1>::difference_type
diff_t1;
for( diff_t1 n = last1 - first1; n > 0; --n,++first1,++first2 )
iter_swap( first1, first2 );
return first2;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 使用Function Object遍历区间的算法
//
// for_earch generate generate_n transform
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename InputIterator, typename Function >
Function for_each( InputIterator first, InputIterator last, Function fun )
{
for( ; first != last; ++first )
fun( *first );
return fun;
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator, typename Generator >
void generate( ForwardIterator first, ForwardIterator last, Generator gen )
{
for( ; first != last; ++first )
*first = gen();
}
//-----------------------------------------------------------------------------
template< typename OutputIterator, typename Integer, typename Generator >
OutputIterator generate_n( OutputIterator first, Integer n, Generator gen )
{
typedef typename primal_type<Integer>::primal_t primal_int;
for( primal_int i = 0; i < n; ++i, ++first )
*first = gen();
return first;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator,
typename UnaryOperation >
OutputIterator transform( InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op )
{
for( ; first != last; ++first,++result )
*result = op( *first );
return result;
}
template< typename InputIterator1, typename InputIterator2,
typename OutputIterator, typename BinaryOperation >
OutputIterator transform( InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, OutputIterator result,
BinaryOperation bin_op )
{
for( ; first1 != last1; ++first1,++first2,++result )
*result = bin_op( *first1, *first2 );
return result;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 替换元素算法
//
// replace replace_if replace_copy replace_copy_if
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename ForwardIterator, typename T >
inline void replace( ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value )
{
typedef typename iterator_traits<ForwardIterator>::iterator_category cate;
replace_aux( first, last, old_value, new_value, cate() );
}
template< typename ForwardIterator, typename T >
void replace_aux( ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value,
forward_iterator_tag )
{
for( ; first != last; ++first )
{
if( *first == old_value )
*first = new_value;
}
}
template< typename ForwardIterator, typename T >
void replace_aux( ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value,
random_access_iterator_tag )
{
typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;
for( diff_t n = last - first; n > 0; --n,++first )
{
if( *first == old_value )
*first = new_value;
}
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator, typename UnaryPredicate, typename T >
inline void replace_if( ForwardIterator first, ForwardIterator last,
UnaryPredicate pred, const T& new_value )
{
typedef typename iterator_traits<ForwardIterator>::iterator_category cate;
replace_if_aux( first, last, pred, new_value, cate() );
}
template< typename ForwardIterator, typename UnaryPredicate, typename T >
void replace_if_aux( ForwardIterator first, ForwardIterator last,
UnaryPredicate pred, const T& new_value,
forward_iterator_tag )
{
for( ; first != last; ++first )
{
if( pred(*first) )
*first = new_value;
}
}
template< typename ForwardIterator, typename UnaryPredicate, typename T >
void replace_if_aux( ForwardIterator first, ForwardIterator last,
UnaryPredicate pred, const T& new_value,
random_access_iterator_tag )
{
typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;
for( diff_t n = last - first; n > 0; --n,++first )
{
if( pred(*first) )
*first = new_value;
}
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator, typename T >
inline OutputIterator replace_copy( InputIterator first, InputIterator last,
OutputIterator result,
const T& old_value, const T& new_value )
{
typedef typename iterator_traits<InputIterator>::iterator_category cate;
return replace_cp_aux( first, last, result, old_value, new_value, cate() );
}
template< typename InputIterator, typename OutputIterator, typename T >
OutputIterator replace_cp_aux( InputIterator first, InputIterator last,
OutputIterator result,
const T& old_value, const T& new_value,
input_iterator_tag )
{
for( ; first != last; ++first,++result )
{
if( *first == old_value )
*result = new_value;
else
*result = *first;
}
return result;
}
template< typename InputIterator, typename OutputIterator, typename T >
OutputIterator replace_cp_aux( InputIterator first, InputIterator last,
OutputIterator result,
const T& old_value, const T& new_value,
random_access_iterator_tag )
{
typedef typename iterator_traits<InputIterator>::difference_type diff_t;
for( diff_t n = last - first; n > 0; --n,++first,++result )
{
if( *first == old_value )
*result = new_value;
else
*result = *first;
}
return result;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator,
typename UnaryPredicate, typename T >
inline
OutputIterator replace_copy_if( InputIterator first, InputIterator last,
OutputIterator result,
UnaryPredicate pred, const T& new_value )
{
typedef typename iterator_traits<InputIterator>::iterator_category cate;
return replace_cp_if_aux( first, last, result, pred, new_value, cate() );
}
template< typename InputIterator, typename OutputIterator,
typename UnaryPredicate, typename T >
OutputIterator replace_cp_if_aux( InputIterator first, InputIterator last,
OutputIterator result,
UnaryPredicate pred, const T& new_value,
input_iterator_tag )
{
for( ; first != last; ++first,++result )
{
if( pred(*first) )
*result = new_value;
else
*result = *first;
}
return result;
}
template< typename InputIterator, typename OutputIterator,
typename UnaryPredicate, typename T >
OutputIterator replace_cp_if_aux( InputIterator first, InputIterator last,
OutputIterator result,
UnaryPredicate pred, const T& new_value,
random_access_iterator_tag )
{
typedef typename iterator_traits<InputIterator>::difference_type diff_t;
for( diff_t n = last - first; n > 0; --n,++first,++result )
{
if( pred(*first) )
*result = new_value;
else
*result = *first;
}
return result;
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 移除元素算法
//
// remove remove_if remove_copy remove_copy_if unique unique_copy
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator, typename T >
OutputIterator remove_copy( InputIterator first, InputIterator last,
OutputIterator result, const T& value )
{
for( ; first != last; ++first )
{
if( *first != value )
{
*result = *first;
++result;
}
}
return result;
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator, typename Predicate >
OutputIterator remove_copy_if( InputIterator first, InputIterator last,
OutputIterator result, Predicate pred )
{
for( ; first != last; ++first )
{
if( !pred(*first) )
{
*result = *first;
++result;
}
}
return result;
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator, typename T >
ForwardIterator remove( ForwardIterator first, ForwardIterator last,
const T& value )
{
while( first != last && *first != value ) //找到第一个出现value的位置
++first;
ForwardIterator next = first;
if( first == last )
return last;
else
return remove_copy( ++next, last, first, value );
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator, typename Predicate >
ForwardIterator remove_if( ForwardIterator first, ForwardIterator last,
Predicate pred )
{
while( first != last && !pred(*first) )
++first;
ForwardIterator next = first;
if( first == last )
return last;
else
return remove_copy( ++next, last, first, value );
}
//-----------------------------------------------------------------------------
template< typename InputIterator, typename OutputIterator >
inline OutputIterator unique_copy( InputIterator first, InputIterator last,
OutputIterator result )
{
typedef typename iterator_traits<OutputIterator>::iterator_category cate;
if( first == last )
return result;
return unique_copy_aux( first, last, result, cate() );
}
template< typename InputIterator, typename OutputIterator >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
OutputIterator result, output_iterator_tag )
{
typedef typename iterator_traits<OutputIterator>::value_type value_t;
value_t value = *first;
*result = value;
++first;
for( ; first != last; ++first )
{
if( value != *first )
{
value = *first;
*(++result) = value;
}
}
return ++result;
}
template< typename InputIterator, typename OutputIterator >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
OutputIterator result, forward_iterator_tag )
{
*result = *first;
++first;
for( ; first != last; ++first )
{
if( *result != *first )
*(++result) = *first;
}
return ++result;
}
template< typename InputIterator, typename OutputIterator,
typename BinaryPredicate >
inline OutputIterator unique_copy( InputIterator first, InputIterator last,
OutputIterator result,
BinaryPredicate bin_pred )
{
typedef typename iterator_traits<OutputIterator>::iterator_category cate;
if( first == last )
return result;
return unique_copy_aux( first, last, result, bin_pred, cate() );
}
template< typename InputIterator, typename OutputIterator,
typename BinaryPredicate >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
OutputIterator result,
BinaryPredicate bin_pred,
output_iterator_tag )
{
typedef typename iterator_traits<OutputIterator>::value_type value_t;
value_t value = *first;
*result = value;
++first;
for( ; first != last; ++first )
{
if( bin_pred(value, *first) )
{
value = *first;
*(++result) = value;
}
}
return ++result;
}
template< typename InputIterator, typename OutputIterator,
typename BinaryPredicate >
OutputIterator unique_copy_aux( InputIterator first, InputIterator last,
OutputIterator result,
BinaryPredicate bin_pred,
forward_iterator_tag )
{
*result = *first;
++first;
for( ; first != last; ++first )
{
if( bin_pred(*result, *first) )
*(++result) = *first;
}
return ++result;
}
//-----------------------------------------------------------------------------
template< typename ForwardIterator >
ForwardIterator unique( ForwardIterator first, ForwardIterator last )
{
ForwardIterator next = first;
++next;
for( ; next != last; ++next )
{
if( *first == *next )
return first;
else
first = next;
}
if( first == last )
return last;
else
return unique_copy( first, last, first );
}
template< typename ForwardIterator, typename BinaryPredicate >
ForwardIterator unique( ForwardIterator first, ForwardIterator last,
BinaryPredicate bin_pred )
{
ForwardIterator next = first;
++next;
for( ; next != last; ++next )
{
if( bin_pred(*first, *next) )
return first;
else
first = next;
}
if( first == last )
return last;
else
return unique_copy( first, last, first, bin_pred );
}
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
//*****************************************************************************
//*****************************************************************************
// 排列算法
//
// reverse reverse_copy rotate rotate_copy
// prev_permutation next_permutation
//*****************************************************************************
//*****************************************************************************
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
template< typename BidirectionalIterator >
inline void reverse( BidirectionalIterator first, BidirectionalIterator last )
{
typedef typename iterator_traits<BidirectionalIterator>::iterator_category
cate;
reverse_aux( first, last, cate() );
}
template< typename BidirectionalIterator >
void reverse_aux( BidirectionalIterator first, BidirectionalIterator last,
bidirectional_iterator_tag )
{
typedef typename iterator_traits<BidirectionalIterator>::value_type
value_t;
while( 1 )
{
if( first == last || first == --last )
return;
val
发表评论
相关推荐
自己根据编程原本与使用C++的经历写的STL的algorithm的实现，不好的地方请指出
stl map algorithm ppt 精品课件
#include <algorithm> #include #include #include void convertToTitleCase(std::string& str) { std::locale loc; std::transform(str.begin(), str.end(), str.begin(), loc, ::toupper); } // 使用方法.....
### STL中的Algorithm库函数详解：排序相关操作 在C++标准模板库(STL)中，`algorithm`头文件提供了一系列非常实用的算法函数，其中包括排序、查找、转换等操作。本文将详细介绍`algorithm`库中关于排序的部分函数，...
algorithm C++ STL
C++ STL--map 和 algorithm C++ STL 中的 map 和 algorithm 是两种非常重要的组件，map 是一种关联式容器，能帮助我们建立一一对应的关系，而 algorithm 则提供了一些常用的算法来处理数据。 Map 简介 map 是一种...
3. **算法(Algorithm)**：STL提供了一系列的算法，如排序、查找、拷贝等，这些算法可以作用于不同的容器，通过迭代器来访问元素，实现了数据处理的通用性。 4. **仿函数(Function object)**：也称为函数对象，它是...
- algorithm库中的常用算法，如binary_search、lower_bound、upper_bound用于有序容器的搜索。 3. **STL面试题.doc** 面试题可能包含各种实践问题，比如： - 如何使用STL实现高效的字符串反转？ - 如何在不复制...
例如，#include 、#include 和#include <algorithm>。 名字空间： 名字空间就好像一个信封，将标志符封装在另一个名字中，避免了和其他标志符冲突。例如，STL的sort()算法封装在名字空间std中，使用std::sort()...
STL中的库函数可以分为几大类：容器（Container）、算法（Algorithm）和迭代器（Iterator）。 容器（Container） 容器是STL中的一种基本数据结构，用于存储和管理数据。常用的容器有： * vector<T>：大小可变的...
在K-Studio-Demo的实现中，可能使用了C++ STL库中的`fstream`类来读取STL文件，`vector`来存储3D模型的顶点和面数据，还有可能使用了`algorithm`头文件中的函数进行数据处理。同时，为了实现预览功能，可能还涉及到...
STL的核心组件主要包括**算法（Algorithm）**、**容器（Container）**和**迭代器（Iterator）**。这三个概念构成了STL的基础，并且大部分代码都是通过模板类和模板函数的形式实现的，这使得代码具有高度的可重用性。...
STL 大致可以分为三大类：算法（algorithm）、容器（container）、迭代器（iterator）。STL 容器是一些模板类，提供了多种组织数据的常用方法，例如 vector（向量，类似于数组）、list（列表，类似于链表）、deque...
- **<stl_algorithm.h>**：包含了各种算法，如排序、查找、变换等，用于操作容器中的元素。 - **<stl_iterator.h>**：定义了各种迭代器，它们是访问容器元素的主要方式。 STL的源码通常会封装在编译器提供的库中，...
4.4.3 算法(Algorithm) 53 4.4.4 函数对象(Function Object) 54 4.4.5 适配器(Adapter) 55 4.4.6 内存分配器(Allocator) 56 4.4.7 概念(Concept)和模型(Model) 56 4.5 C++ STL存在的一些问题 57 4.6 本...
STL，全称为Standard Template Library，是C++标准库的核心组成部分，主要利用模板（Template）机制实现了泛型编程。它的引入极大地提升了C++语言的灵活性和可复用性，允许程序员编写不依赖于具体数据类型的高效算法...
- **算法(Algorithm)**：对容器进行操作的一系列通用函数，如sort、find等。 - **函数对象(Function Object)**：可以像函数一样被调用的对象，通常用于定制算法的行为。 - **适配器(Adapter)**：用于改变容器或算法...
STL，全称为Standard Template Library，是C++标准库的核心组成部分，主要由五大核心概念组成：迭代器（Iterator）、容器（Container）、算法（Algorithm）、适配器（Adaptors）和空间配置器（Allocator）。...