C++ young 程序库——y_algorithm.hpp

文件位置：young/y_algorithm.hpp

The young Library

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;

value_t temp = *first;

*first = *last;

*last = temp;

++first;

}

template< typename BidirectionalIterator >

void reverse_aux( BidirectionalIterator first, BidirectionalIterator last,

random_access_iterator_tag )

{

typedef typename iterator_traits<BidirectionalIterator>::value_type

value_t;

while( first < last )

{

--last;

value_t temp = *first;

*first = *last;

*last = temp;

++first;

}

//-----------------------------------------------------------------------------

template< typename BidirectionalIterator, typename OutputIterator >

inline OutputIterator reverse_copy( BidirectionalIterator first,

BidirectionalIterator last,

OutputIterator result )

{

typedef typename iterator_traits<BidirectionalIterator>::iterator_category

cate;

if( first == last )

return result;

else

return reverse_copy_aux( first, last, result, cate() );

}

template< typename BidirectionalIterator, typename OutputIterator >

OutputIterator reverse_copy_aux( BidirectionalIterator first,

BidirectionalIterator last,

OutputIterator result,

bidirectional_iterator_tag )

{

while( first != last )

{

--last;

*result = *last;

++result;

}

return result;

}

template< typename BidirectionalIterator, typename OutputIterator >

OutputIterator reverse_copy_aux( BidirectionalIterator first,

BidirectionalIterator last,

OutputIterator result,

random_access_iterator_tag )

{

typedef typename iterator_traits<BidirectionalIterator>::difference_type

diff_t;

for( diff_t n = last - first; n > 0; --n )

{

--last;

*result = *last;

++result;

}

return result;

}

//-----------------------------------------------------------------------------

template< typename RandomAccessIterator, typename Integer >

void __rotate_cycle( RandomAccessIterator first, RandomAccessIterator last,

RandomAccessIterator initial, Integer shift )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type

value_t;

value_t value = *initial;

RandomAccessIterator ptr1 = initial;

RandomAccessIterator ptr2 = ptr1 + shift;

while( ptr2 != initial )

{

*ptr1 = *ptr2;

ptr1 = ptr2;

if( last - ptr2 > shift )

ptr2 += shift;

else

ptr2 = first + ( shift - (last - ptr2) );

}

*ptr1 = value;

}

template< typename ForwardIterator >

inline void rotate( ForwardIterator first, ForwardIterator middle,

ForwardIterator last )

{

typedef typename iterator_traits<ForwardIterator>::iterator_category cate;

if( first == middle || middle == last )

return;

rotate_aux( first, middle, last, cate() );

}

template< typename ForwardIterator >

void rotate_aux( ForwardIterator first, ForwardIterator middle,

ForwardIterator last, forward_iterator_tag )

{

ForwardIterator iter = middle;

while( 1 )

{

iter_swap( first, iter );

++first;

++iter;

if( first == middle ) //前半区间遍历完毕

{

if( iter == last ) //区间遍历完成

return;

middle = iter;

}

else if( iter == last ) //后半区间遍历完毕

iter = middle;

}

template< typename ForwardIterator >

void rotate_aux( ForwardIterator first, ForwardIterator middle,

ForwardIterator last, bidirectional_iterator_tag )

{

reverse( first, middle );

reverse( middle, last );

reverse( first, last );

}

template< typename ForwardIterator >

void rotate_aux( ForwardIterator first, ForwardIterator middle,

ForwardIterator last, random_access_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

typedef typename iterator_traits<ForwardIterator>::value_type value_t;

diff_t n = gcd( last - first, middle - first );

while( n-- )

__rotate_cycle( first, last, first + n, middle - first );

}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename OutputIterator >

inline

OutputIterator rotate_copy( ForwardIterator first, ForwardIterator middle,

ForwardIterator last, OutputIterator result )

{

result = copy( middle, last, result );

return copy( first, middle, result );

}

//-----------------------------------------------------------------------------

template< typename BidirectionalIterator >

bool prev_permutation( BidirectionalIterator first,

BidirectionalIterator last )

{

if( first == last )

return false;

BidirectionalIterator iter_before = first;

++iter_before;

if( iter_before == last )

return false;

iter_before = last;

--iter_before; //指向倒数第一个元素

while( 1 )

{

BidirectionalIterator iter_after = iter_before;

--iter_before; //指向前一个元素

if( *iter_after < *iter_before ) //后一个元素小于前一个元素

{

BidirectionalIterator temp = last;

while( !(*--temp < *iter_before) ) ; //寻找比*iter_before小的值位置

iter_swap( iter_before, temp );

reverse( iter_after, last );

return true;

}

if( iter_before == first )

{

reverse( first, last );

return false;

}

template< typename BidirectionalIterator, typename StrictWeakOrdering >

bool prev_permutation( BidirectionalIterator first,

BidirectionalIterator last,

StrictWeakOrdering comp )

{

if( first == last )

return false;

BidirectionalIterator iter_before = first;

++iter_before;

if( iter_before == last )

return false;

iter_before = last;

--iter_before;

while( 1 )

{

BidirectionalIterator iter_after = iter_before;

--iter_before;

if( comp(*iter_after, *iter_before) )

{

BidirectionalIterator temp = last;

while( !comp(*--temp, *iter_before) ) ;

iter_swap( iter_before, temp );

reverse( iter_after, last );

return true;

}

if( iter_before == first )

{

reverse( first, last );

return false;

}

//-----------------------------------------------------------------------------

template< typename BidirectionalIterator >

bool next_permutation( BidirectionalIterator first,

BidirectionalIterator last )

{

if( first == last )

return false;

BidirectionalIterator iter_before = first;

++iter_before;

if( iter_before == last )

return false;

iter_before = last;

--iter_before; //指向倒数第一个元素

while( 1 )

{

BidirectionalIterator iter_after = iter_before;

--iter_before; //指向前一个元素

if( *iter_before < *iter_after ) //后一个元素大于前一个元素

{

BidirectionalIterator temp = last;

while( !(*iter_before < *--temp) ) ; //寻找比*iter_before大的值位置

iter_swap( iter_before, temp );

reverse( iter_after, last );

return true;

}

if( iter_before == first )

{

reverse( first, last );

return false;

}

template< typename BidirectionalIterator, typename StrictWeakOrdering >

bool next_permutation( BidirectionalIterator first,

BidirectionalIterator last,

StrictWeakOrdering comp )

{

if( first == last )

return false;

BidirectionalIterator iter_before = first;

++iter_before;

if( iter_before == last )

return false;

iter_before = last;

--iter_before;

while( 1 )

{

BidirectionalIterator iter_after = iter_before;

--iter_before;

if( comp(*iter_before, *iter_after) )

{

BidirectionalIterator temp = last;

while( !comp(*iter_before, *--temp) ) ;

iter_swap( iter_before, temp );

reverse( iter_after, last );

return true;

}

if( iter_before == first )

{

reverse( first, last );

return false;

}

//-----------------------------------------------------------------------------

//*****************************************************************************

// 分割算法

// partition stable_partition

//*****************************************************************************

//-----------------------------------------------------------------------------

template< typename BidirectionalIterator, typename Predicate >

BidirectionalIterator partition( BidirectionalIterator first,

BidirectionalIterator last,

Predicate pred )

{

while( 1 )

{

while( 1 ) //从前面查找不符合条件的数据

{

if( first == last )

return first;

else if( pred(*first) )

++first;

else

break;

}

--last;

while( 1 ) //从后面查找符合条件的数据

{

if( first == last )

return first;

else if( !pred(*last) )

--last;

else

break;

}

iter_swap( first, last ); //前后数据交换

++first;

}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename Predicate >

inline ForwardIterator stable_partition( ForwardIterator first,

ForwardIterator last,

Predicate pred )

{

typedef typename iterator_traits<ForwardIterator>::value_type value_t;

if( first == last )

return first;

temporary_buffer<ForwardIterator, value_t> buf( first, last );

if( buf.size() > 0 ) //临时缓冲区申请成功

return stable_partition_adaptive( first, last, pred,

buf.requested_size(), buf.begin(),

buf.size() );

else

return inplace_stable_partition( first, last, pred,

buf.requested_size() );

}

template< typename ForwardIterator, typename Predicate, typename Integer >

ForwardIterator inplace_stable_partition( ForwardIterator first,

ForwardIterator last,

Predicate pred,

Integer len )

{

if( len == 1 )

return ( pred(*first) ? last : first );

ForwardIterator middle = first;

advance( middle, len / 2 );

ForwardIterator first_cut = inplace_stable_partition( first, middle,

pred, len / 2 );

ForwardIterator second_cut = inplace_stable_partition( middle, last,

pred, len / 2 );

rotate( first_cut, middle, second_cut );

len = distance( middle, second_cut );

advance( first_cut, len );

return first_cut;

}

template< typename ForwardIterator, typename Predicate, typename Integer,

typename Pointer >

ForwardIterator stable_partition_adaptive( ForwardIterator first,

ForwardIterator last,

Predicate pred,

Integer len,

Pointer buffer,

Integer buffer_size )

{

if( len <= buffer_size ) //缓存空间可以容纳所有的数据

{

ForwardIterator result = first;

Pointer temp = buffer;

for( ; first != last; ++first )

{

if( pred(*first) ) //符合条件的数据

{

*result = *first;

++result;

}

else //不符合条件的数据放进缓存内

{

*temp = *first;

++temp;

}

copy( buffer, temp, result );

return result;

}

else //缓存空间无法容纳所有的数据

{

ForwardIterator middle = first;

advance( middle, len / 2 );

ForwardIterator first_cut =

stable_partition_adaptive( first, middle, pred, len / 2,

buffer, buffer_size );

ForwardIterator second_cut =

stable_partition_adaptive( middle, last, pred, len / 2,

buffer, buffer_size );

//将后半部分满足条件的数据和前半部分不满足条件的数据调换

rotate( first_cut, middle, second_cut );

len = distance( middle, second_cut );

advance( first_cut, len );

return first_cut;

}

//-----------------------------------------------------------------------------

//*****************************************************************************

// 随机重排与抽样算法

// random_shuffle random_sample random_sample_n

//*****************************************************************************

//-----------------------------------------------------------------------------

template< typename RandomAccessIterator >

void random_shuffle( RandomAccessIterator first,

RandomAccessIterator last )

{

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

if( first != last )

{

diff_t len = last - first;

for( diff_t i = 1; i < len; ++i )

iter_swap( first + i, first + (std::rand() % (i + 1)) );

}

template< typename RandomAccessIterator, typename RandomNumberGenerator >

void random_shuffle( RandomAccessIterator first,

RandomAccessIterator last,

RandomNumberGenerator& rand )

{

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

if( first != last )

{

diff_t len = last - first;

for( diff_t i = 1; i < len; ++i )

iter_swap( first + i, first + rand(i + 1) );

}

//-----------------------------------------------------------------------------

template< typename InputIterator, typename RandomAccessIterator >

RandomAccessIterator random_sample( InputIterator first,

InputIterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last )

{

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

diff_t len = result_last - result_first;

diff_t m = 0, n = len;

for( ; first != last && m < len; ++first,++m )

*(result_first + m) = *first;

while( first != last )

{

++n;

diff_t num = std::rand() % n;

if( num < len )

*(result_first + num) = *first;

++first;

}

return ( result_first + m );

}

template< typename InputIterator, typename RandomAccessIterator,

typename RandomNumberGenerator >

RandomAccessIterator random_sample( InputIterator first,

InputIterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last,

RandomNumberGenerator& rand )

{

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

diff_t len = result_last - result_first;

diff_t m = 0, n = len;

for( ; first != last && m < len; ++first,++m )

*(result_first + m) = *first;

while( first != last )

{

++n;

diff_t num = rand( n );

if( num < len )

*(result_first + num) = *first;

++first;

}

return ( result_first + m );

}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename OutputIterator, typename Integer >

OutputIterator random_sample_n( ForwardIterator first, ForwardIterator last,

OutputIterator result, Integer count )

{

Integer len = distance( first, last );

Integer n = min( count, len );

while( n > 0 )

{

if( std::rand() % len < n )

{

*result = *first;

++result;

--n;

}

--len;

++first;

}

return result;

}

template< typename ForwardIterator, typename OutputIterator, typename Integer,

typename RandomNumberGenerator >

OutputIterator random_sample_n( ForwardIterator first, ForwardIterator last,

OutputIterator result, Integer count,

RandomNumberGenerator& rand )

{

Integer len = distance( first, last );

Integer n = min( count, len );

while( n > 0 )

{

if( rand(len) < n )

{

*result = *first;

++result;

--n;

}

--len;

++first;

}

return result;

}

//-----------------------------------------------------------------------------

//*****************************************************************************

// 二分查找算法

// upper_bound equal_range binary_search

//*****************************************************************************

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename T >

inline

ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last,

const T& value )

{

typedef typename iterator_traits<ForwardIterator>::iterator_category cate;

if( first == last )

return first;

else

return upper_b_aux( first, last, value, cate() );

}

template< typename ForwardIterator, typename T >

ForwardIterator upper_b_aux( ForwardIterator first, ForwardIterator last,

const T& value, forward_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = distance( first, last );

diff_t half;

ForwardIterator middle;

while( len > 0 )

{

half = len / 2;

middle = first;

advance( middle, half );

if( value < *middle) //要查找的值在前半部分

len = half;

else //要查找的值在后半部分

{

first = middle;

++first;

len = len - half - 1;

}

return first;

}

template< typename ForwardIterator, typename T >

ForwardIterator upper_b_aux( ForwardIterator first, ForwardIterator last,

const T& value, random_access_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = last - first;

diff_t half;

ForwardIterator middle;

while( len > 0 )

{

half = len / 2;

middle = first + half;

if( value < *middle ) //要查找的值在前半部分

len = half;

else //要查找的值在后半部分

{

first = middle + 1;

len = len - half - 1;

}

return first;

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

inline

ForwardIterator upper_bound( ForwardIterator first, ForwardIterator last,

const T& value, StrictWeakOrdering comp )

{

typedef typename iterator_traits<ForwardIterator>::iterator_category cate;

if( first == last )

return first;

else

return upper_b_aux( first, last, value, comp, cate() );

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

ForwardIterator upper_b_aux( ForwardIterator first, ForwardIterator last,

const T& value, StrictWeakOrdering comp,

forward_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = distance( first, last );

diff_t half;

ForwardIterator middle;

while( len > 0 )

{

half = len / 2;

middle = first;

advance( middle, half );

if( comp(value, *middle) ) //要查找的值在前半部分

{

first = middle;

++first;

len = len - half - 1;

}

else //要查找的值在后半部分

len = half;

}

return first;

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

ForwardIterator upper_b_aux( ForwardIterator first, ForwardIterator last,

const T& value, StrictWeakOrdering comp,

random_access_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = last - first;

diff_t half;

ForwardIterator middle;

while( len > 0 )

{

half = len / 2;

middle = first + half;

if( comp(value, *middle) ) //要查找的值在前半部分

len = half;

else //要查找的值在后半部分

{

first = middle + 1;

len = len - half - 1;

}

return first;

}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename T >

inline pair<ForwardIterator, ForwardIterator>

equal_range( ForwardIterator first, ForwardIterator last, const T& value )

{

typedef typename iterator_traits<ForwardIterator>::iterator_category cate;

if( first == last )

return first;

else

return eq_range_aux( first, last, value, cate() );

}

template< typename ForwardIterator, typename T >

pair<ForwardIterator, ForwardIterator>

eq_range_aux( ForwardIterator first, ForwardIterator last, const T& value,

forward_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = distance( first, last );

diff_t half = 0;

ForwardIterator middle, left, righ;

while( len > 0 )

{

half = len / 2;

middle = first;

advance( middle, half );

if( *middle < value ) //在后半部分

{

first = middle;

++first;

len = len - half - 1;

}

else if( value < *middle ) //在前半部分

len = half;

else

{

left = lower_bound( first, middle, value );

advance( first, len );

right = upper_bound( ++middle, first, value );

return pair<ForwardIterator, ForwardIterator>( left, right );

}

return pair<ForwardIterator, ForwardIterator>( first, first );

}

template< typename ForwardIterator, typename T >

pair<ForwardIterator, ForwardIterator>

eq_range_aux( ForwardIterator first, ForwardIterator last, const T& value,

random_access_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = last - first;

diff_t half = 0;

ForwardIterator middle, left, righ;

while( len > 0 )

{

half = len / 2;

middle = first + half;

if( *middle < value ) //在后半部分

{

first = middle + 1;

len = len - half - 1;

}

else if( value < *middle ) //在前半部分

len = half;

else

{

left = lower_bound( first, middle, value );

right = upper_bound( ++middle, first + len, value );

return pair<ForwardIterator, ForwardIterator>( left, right );

}

return pair<ForwardIterator, ForwardIterator>( first, first );

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

inline pair<ForwardIterator, ForwardIterator>

equal_range( ForwardIterator first, ForwardIterator last, const T& value,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<ForwardIterator>::iterator_category cate;

if( first == last )

return first;

else

return eq_range_aux( first, last, value, comp, cate() );

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

pair<ForwardIterator, ForwardIterator>

eq_range_aux( ForwardIterator first, ForwardIterator last, const T& value,

StrictWeakOrdering comp, forward_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = distance( first, last );

diff_t half = 0;

ForwardIterator middle, left, righ;

while( len > 0 )

{

half = len / 2;

middle = first;

advance( middle, half );

if( comp(*middle, value) ) //在后半部分

{

first = middle;

++first;

len = len - half - 1;

}

else if( comp(value, *middle) ) //在前半部分

len = half;

else

{

left = lower_bound( first, middle, value, comp );

advance( first, len );

right = upper_bound( ++middle, first, value, comp );

return pair<ForwardIterator, ForwardIterator>( left, right );

}

return pair<ForwardIterator, ForwardIterator>( first, first );

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

pair<ForwardIterator, ForwardIterator>

eq_range_aux( ForwardIterator first, ForwardIterator last, const T& value,

StrictWeakOrdering comp, random_access_iterator_tag )

{

typedef typename iterator_traits<ForwardIterator>::difference_type diff_t;

diff_t len = last - first;

diff_t half = 0;

ForwardIterator middle, left, righ;

while( len > 0 )

{

half = len / 2;

middle = first + half;

if( comp(*middle, value) ) //在后半部分

{

first = middle + 1;

len = len - half - 1;

}

else if( comp(value, *middle) ) //在前半部分

len = half;

else

{

left = lower_bound( first, middle, value, comp );

right = upper_bound( ++middle, first + len, value, comp );

return pair<ForwardIterator, ForwardIterator>( left, right );

}

return pair<ForwardIterator, ForwardIterator>( first, first );

}

//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename T >

bool binary_search( ForwardIterator first, ForwardIterator last,

const T& value )

{

ForwardIterator i = lower_bound( first, last, value );

return ( i != last && !(value < *i) );

}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >

bool binary_search( ForwardIterator first, ForwardIterator last,

const T& value, StrictWeakOrdering comp )

{

ForwardIterator i = lower_bound( first, last, value, comp );

return ( i != last && !comp(value, *i) );

}

//-----------------------------------------------------------------------------

//*****************************************************************************

// 区间合并算法

// merge merge_backward inplace_merge

//*****************************************************************************

//-----------------------------------------------------------------------------

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator >

OutputIterator merge( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result )

{

for( ; first1 != last1 && first2 != last2; ++result )

{

if( *first2 < *first1 )

{

*result = *first2;

++first2;

}

else

{

*result = *first1;

++first1;

}

result = copy( first1, last1, result );

return copy( first2, last2, result );

}

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator, typename StrictWeakOrdering >

OutputIterator merge( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result, StrictWeakOrdering comp )

{

for( ; first1 != last1 && first2 != last2; ++result )

{

if( comp(*first2, *first1) )

{

*result = *first2;

++first2;

}

else

{

*result = *first1;

++first1;

}

result = copy( first1, last1, result );

return copy( first2, last2, result );

}

//-----------------------------------------------------------------------------

template< typename BidirectionalIterator1, typename BidirectionalIterator2,

typename BidirectionalIterator3 >

BidirectionalIterator3 merge_backward( BidirectionalIterator1 first1,

BidirectionalIterator1 last1,

BidirectionalIterator2 first2,

BidirectionalIterator2 last2,

BidirectionalIterator3 result_last )

{

if( first1 == last1 )

return copy_backward( first2, last2, result_last );

if( first2 == last2 )

return copy_backward( first1, last1, result_last );

--last1;

--last2;

while( 1 )

{

if( *last2 < *last1 )

{

*--result_last = *last1;

if( first1 == last1 )

return copy_backward( first2, ++last2, result_last );

--last1;

}

else

{

*--result_last = *last2;

if( first2 == last2 )

return copy_backward( first1, ++last1, result_last );

--last2;

}

template< typename BidirectionalIterator1, typename BidirectionalIterator2,

typename BidirectionalIterator3, typename StrictWeakOrdering >

BidirectionalIterator3 merge_backward( BidirectionalIterator1 first1,

BidirectionalIterator1 last1,

BidirectionalIterator2 first2,

BidirectionalIterator2 last2,

BidirectionalIterator3 result_last,

StrictWeakOrdering comp )

{

if( first1 == last1 )

return copy_backward( first2, last2, result_last );

if( first2 == last2 )

return copy_backward( first1, last1, result_last );

--last1;

--last2;

while( 1 )

{

if( comp(*last2, *last1) )

{

*--result_last = *last1;

if( first1 == last1 )

return copy_backward( first2, ++last2, result_last );

--last1;

}

else

{

*--result_last = *last2;

if( first2 == last2 )

return copy_backward( first1, ++last1, result_last );

--last2;

}

//-----------------------------------------------------------------------------

template< typename BidirectionalIterator1, typename BidirectionalIterator2,

typename Integer >

BidirectionalIterator1 __rotate_adaptive( BidirectionalIterator1 first,

BidirectionalIterator1 middle,

BidirectionalIterator1 last,

Integer len1, Integer len2,

BidirectionalIterator2 buffer,

Integer buffer_size )

{

BidirectionalIterator2 buffer_end;

//前半区间比后半区间小并可以放入缓冲区

if( len1 <= len2 && len1 <= buffer_size )

{

buffer_end = copy( first, middle, buffer );

copy( middle, last, first );

return copy_backward( buffer, buffer_end, last );

}

else if( len2 <= buffer_size ) //后半区间比前半区间小并可放入缓冲区

{

buffer_end = copy( middle, last, buffer );

copy_backward( first, middle, last );

return copy( buffer, buffer_end, first );

}

else

{

rotate( first, middle, last );

advance( first, len2 );

return first;

}

template< typename BidirectionalIterator >

inline void inplace_merge( BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last )

{

typedef typename iterator_traits<BidirectionalIterator>::value_type

value_t;

typedef typename iterator_traits<BidirectionalIterator>::difference_type

diff_t;

if( first == middle || middle == last )

return;

diff_t len1 = distance( first, middle );

diff_t len2 = distance( middle, last );

temporary_buffer<BidirectionalIterator, value_t> buffer( first, last );

if( buffer.size() > 0 ) //缓冲区申请成功

__merge_adaptive( first, middle, last, len1, len2,

buffer.begin(), diff_t(buffer.size()) );

else

__merge_without_buffer( first, middle, last, len1, len2 );

}

template< typename BidirectionalIterator, typename Integer, typename Pointer >

void __merge_adaptive( BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last,

Integer len1, Integer len2,

Pointer buffer, Integer buffer_size )

{

//前半区间比后半区间小并可以放入缓冲区，则可直接使用归并算法

if( len1 <= len2 && len1 <= buffer_size )

{

Pointer end_buffer = copy( first, middle, buffer );

merge( buffer, end_buffer, middle, last, first );

}

else if( len2 <= buffer_size ) //后半区间比前半区间小并可放入缓冲区

{

Pointer end_buffer = copy( middle, last, buffer );

merge_backward( first, middle, buffer, end_buffer, last );

}

else

{

BidirectionalIterator first_cut = first;

BidirectionalIterator second_cut = middle;

Integer len1_mid = 0;

Integer len2_mid = 0;

if( len1 > len2 )

{

len1_mid = len1 / 2;

advance( first_cut, len1_mid );

second_cut = lower_bound( middle, last, *first_cut );

len2_mid = distance( middle, second_cut );

}

else

{

len2_mid = len2 / 2;

advance( second_cut, len2_mid );

first_cut = upper_bound( first, middle, *second_cut );

len1_mid = distance( first, first_cut );

}

BidirectionalIterator new_middle = __rotate_adaptive( first_cut, middle,

second_cut, len1 - len1_mid,

len2_mid, buffer, buffer_size );

__merge_adaptive( first, first_cut, new_middle, len1_mid, len2_mid,

buffer, buffer_size );

__merge_adaptive( new_middle, second_cut, last, len1 - len1_mid,

len2 - len2_mid, buffer, buffer_size );

}

template< typename BidirectionalIterator, typename Integer >

void __merge_without_buffer( BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last,

Integer len1, Integer len2 )

{

if( len1 < 2 && len2 < 2 )

{

if( *middle < *first )

iter_swap( first, middle );

return;

}

BidirectionalIterator first_cut = first;

BidirectionalIterator second_cut = middle;

Integer len1_mid = 0;

Integer len2_mid = 0;

if( len1 > len2 ) //前半区间更大

{

len1_mid = len1 / 2;

advance( first_cut, len1_mid );

//在后半区间寻找可以插入[first_cut, middle)的位置

second_cut = lower_bound( middle, last, *first_cut );

len2_mid = distance( middle, second_cut );

}

else

{

len2_mid = len2 / 2;

advance( second_cut, len2_mid );

//在前半区间寻找可以插入[second_cut, last)的位置

first_cut = upper_bound( first, middle, *second_cut );

len1_mid = distance( first, first_cut );

}

rotate( first_cut, middle, second_cut );

BidirectionalIterator new_middle = first_cut;

advance( new_middle, len2_mid );

__merge_without_buffer( first, first_cut, new_middle, len1_mid, len2_mid );

__merge_without_buffer( new_middle, second_cut, last, len1 - len1_mid,

len2 - len2_mid );

}

//使用functor进行比较的inplace_merge

template< typename BidirectionalIterator, typename StrictWeakOrdering >

inline void inplace_merge( BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<BidirectionalIterator>::value_type

value_t;

typedef typename iterator_traits<BidirectionalIterator>::difference_type

diff_t;

if( first == middle || middle == last )

return;

diff_t len1 = distance( first, middle );

diff_t len2 = distance( middle, last );

temporary_buffer<BidirectionalIterator, value_t> buffer( first, last );

if( buffer.size() > 0 )

__merge_adaptive( first, middle, last, len1, len2,

buffer.begin(), diff_t(buffer.size()), comp );

else

__merge_without_buffer( first, middle, last, len1, len2, comp );

}

template< typename BidirectionalIterator, typename Integer, typename Pointer,

typename StrictWeakOrdering >

void __merge_adaptive( BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last,

Integer len1, Integer len2,

Pointer buffer, Integer buffer_size,

StrictWeakOrdering comp )

{

if( len1 <= len2 && len1 <= buffer_size )

{

Pointer end_buffer = copy( first, middle, buffer );

merge( buffer, end_buffer, middle, last, first, comp );

}

else if( len2 <= buffer_size )

{

Pointer end_buffer = copy( middle, last, buffer );

merge_backward( first, middle, buffer, end_buffer, last, comp );

}

else

{

BidirectionalIterator first_cut = first;

BidirectionalIterator second_cut = middle;

Integer len1_mid = 0;

Integer len2_mid = 0;

if( len1 > len2 )

{

len1_mid = len1 / 2;

advance( first_cut, len1_mid );

second_cut = lower_bound( middle, last, *first_cut, comp );

len2_mid = distance( middle, second_cut );

}

else

{

len2_mid = len2 / 2;

advance( second_cut, len2_mid );

first_cut = upper_bound( first, middle, *second_cut, comp );

len1_mid = distance( first, first_cut );

}

BidirectionalIterator new_middle = __rotate_adaptive( first_cut, middle,

second_cut, len1 - len1_mid,

len2_mid, buffer, buffer_size );

__merge_adaptive( first, first_cut, new_middle, len1_mid, len2_mid,

buffer, buffer_size, comp );

__merge_adaptive( new_middle, second_cut, last, len1 - len1_mid,

len2 - len2_mid, buffer, buffer_size, comp );

}

template< typename BidirectionalIterator, typename Integer,

typename StrictWeakOrdering >

void __merge_without_buffer( BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last,

Integer len1, Integer len2,

StrictWeakOrdering comp )

{

if( len1 < 2 && len2 < 2 )

{

if( comp(*middle, *first) )

iter_swap( first, middle );

return;

}

BidirectionalIterator first_cut = first;

BidirectionalIterator second_cut = middle;

Integer len1_mid = 0;

Integer len2_mid = 0;

if( len1 > len2 )

{

len1_mid = len1 / 2;

advance( first_cut, len1_mid );

second_cut = lower_bound( middle, last, *first_cut, comp );

len2_mid = distance( middle, second_cut );

}

else

{

len2_mid = len2 / 2;

advance( second_cut, len2_mid );

first_cut = upper_bound( first, middle, *second_cut, comp );

len1_mid = distance( first, first_cut );

}

rotate( first_cut, middle, second_cut );

BidirectionalIterator new_middle = first_cut;

advance( new_middle, len2_mid );

__merge_without_buffer( first, first_cut, new_middle,

len1_mid, len2_mid, comp );

__merge_without_buffer( new_middle, second_cut, last,

len1 - len1_mid, len2 - len2_mid, comp );

}

//-----------------------------------------------------------------------------

//*****************************************************************************

// 区间集合算法

// includes set_union set_intersection

// set_difference set_symmetric_difference

//*****************************************************************************

//-----------------------------------------------------------------------------

//此系列算法要求输入的两个序列都必须为有序序列

//[first2, last2) 是否包含于 [first1, last1)

template< typename InputIterator1, typename InputIterator2 >

bool includes( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2 )

{

while( first1 != last1 && first2 != last2 )

{

if( *first2 < *first1 )

return false;

else if( *first1 < *first2 )

++first1;

else

{

++first1;

++first2;

}

return ( first2 == last2 );

}

template< typename InputIterator1, typename InputIterator2,

typename StrictWeakOrdering >

bool includes( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

StrictWeakOrdering comp )

{

while( first1 != last1 && first2 != last2 )

{

if( comp(*first2, *first1) )

return false;

else if( comp(*first1, *first2) )

++first1;

else

{

++first1;

++first2;

}

return ( first2 == last2 );

}

//-----------------------------------------------------------------------------

//返回[first1, last1)和[first2, last2)中的所有元素

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator >

OutputIterator set_union( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result )

{

while( first1 != last1 && first2 != last2 )

{

if( *first1 < *first2 )

{

*result = *first1;

++first1;

}

else if( *first2 < *first1 )

{

*result = *first2;

++first2;

}

else

{

*result = *first1;

++first1;

++first2;

}

++result;

}

result = copy( first1, last1, result );

return copy( first2, last2, result );

}

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator, typename StrictWeakOrdering >

OutputIterator set_union( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result,

StrictWeakOrdering comp )

{

while( first1 != last1 && first2 != last2 )

{

if( comp(*first1, *first2) )

{

*result = *first1;

++first1;

}

else if( comp(*first2, *first1) )

{

*result = *first2;

++first2;

}

else

{

*result = *first1;

++first1;

++first2;

}

++result;

}

result = copy( first1, last1, result );

return copy( first2, last2, result );

}

//-----------------------------------------------------------------------------

//返回在[first1, last1)中出现同时也在[first2, last2)中也出现的元素

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator >

OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result )

{

while( first1 != last1 && first2 != last2 )

{

if( *first1 < *first2 )

++first1;

else if( *first2 < *first1 )

++first2;

else

{

*result = *first1;

++first1;

++first2;

++result;

}

return result;

}

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator, typename StrictWeakOrdering >

OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result,

StrictWeakOrdering comp )

{

while( first1 != last1 && first2 != last2 )

{

if( comp(*first1, *first2) )

++first1;

else if( comp(*first2, *first1) )

++first2;

else

{

*result = *first1;

++first1;

++first2;

++result;

}

return result;

}

//-----------------------------------------------------------------------------

//返回在[first1, last1)中出现，在[first2, last2)中不出现的元素

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator >

OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result )

{

while( first1 != last1 && first2 != last2 )

{

if( *first1 < *first2 )

{

*result = *first1;

++first1;

++result;

}

else if( *first2 < *first1 )

++first2;

else

{

++first1;

++first2;

}

return copy( first1, last1, result );

}

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator, typename StrictWeakOrdering >

OutputIterator set_difference( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, InputIterator2 last2,

OutputIterator result,

StrictWeakOrdering comp )

{

while( first1 != last1 && first2 != last2 )

{

if( comp(*first1, *first2) )

{

*result = *first1;

++first1;

++result;

}

else if( comp(*first2, *first1) )

++first2;

else

{

++first1;

++first2;

}

return copy( first1, last1, result );

}

//-----------------------------------------------------------------------------

//返回在[first1, last1)中出现在[first2, last2)中不出现，

//以及在[first2, last2)中出现在[first1, last1)中不出现的元素

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator >

OutputIterator set_symmetric_difference( InputIterator1 first1,

InputIterator1 last1,

InputIterator2 first2,

InputIterator2 last2,

OutputIterator result )

{

while( first1 != last1 && first2 != last2 )

{

if( *first1 < *first2 )

{

*result = *first1;

++first1;

++result;

}

else if( *first2 < *first1 )

{

*result = *first2;

++first2;

++result;

}

else

{

++first1;

++first2;

}

result = copy( first1, last1, result );

return copy( first2, last2, result );

}

template< typename InputIterator1, typename InputIterator2,

typename OutputIterator, typename StrictWeakOrdering >

OutputIterator set_symmetric_difference( InputIterator1 first1,

InputIterator1 last1,

InputIterator2 first2,

InputIterator2 last2,

OutputIterator result,

StrictWeakOrdering comp )

{

while( first1 != last1 && first2 != last2 )

{

if( comp(*first1, *first2) )

{

*result = *first1;

++first1;

++result;

}

else if( comp(*first2, *first1) )

{

*result = *first2;

++first2;

++result;

}

else

{

++first1;

++first2;

}

result = copy( first1, last1, result );

return copy( first2, last2, result );

}

//-----------------------------------------------------------------------------

//*****************************************************************************

// 排序算法

// is_sorted sort stable_sort

// partial_sort partial_sort_copy nth_element

//*****************************************************************************

//-----------------------------------------------------------------------------

template< typename ForwardIterator >

bool is_sorted( ForwardIterator first, ForwardIterator last )

{

if( first != last )

{

ForwardIterator next = first;

for( ++next; next != last; ++next )

{

if( *next < *first )

return false;

first = next;

}

return true;

}

template< typename ForwardIterator, typename StrictWeakOrdering >

bool is_sorted( ForwardIterator first, ForwardIterator last,

StrictWeakOrdering comp )

{

if( first != last )

{

ForwardIterator next = first;

for( ++next; next != last; ++next )

{

if( comp(*next, *first) )

return false;

first = next;

}

return true;

}

//-----------------------------------------------------------------------------

//以下为sort的辅助函数，执行插入排序算法

template< typename RandomAccessIterator >

void insertion_sort( RandomAccessIterator first, RandomAccessIterator last )

{

if( first == last )

return;

//对[first, last)中的数据依次进行线性插入

for( RandomAccessIterator iter = first + 1; iter != last; ++iter )

__linear_insert( first, iter );

}

template< typename RandomAccessIterator >

inline void __linear_insert( RandomAccessIterator first,

RandomAccessIterator last )

{

//注意：该函数的有效区间为[first, last]

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

value_t new_value = *last;

if( new_value < *first ) //比第一个元素小则直接置于起始位置

{

copy_backward( first, last, last + 1 );

*first = new_value;

}

else

__unguarded_linear_insert( last, new_value );

}

template< typename RandomAccessIterator, typename T >

void __unguarded_linear_insert( RandomAccessIterator last, T new_value )

{

//last参数表示最后一个有效的迭代器，实际上new_value就是last所指的值

//new_value自prev起往前迭代，与每一个迭代器所指的值进行比较，

//直到遇到不大于new_value值的位置才停止，每一次比较中比new_value大的

//值全部都往后移一个位置

RandomAccessIterator prev = last;

RandomAccessIterator result = last;

--prev;

while( new_value < *prev )

{

*result = *prev;

result = prev;

--prev;

}

if( result != last ) //赋值的开销可能会很大，所以加上这个判断

*result = new_value;

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void insertion_sort( RandomAccessIterator first, RandomAccessIterator last,

StrictWeakOrdering comp )

{

if( first == last )

return;

for( RandomAccessIterator iter = first + 1; iter != last; ++iter )

__linear_insert( first, iter, comp );

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

inline void __linear_insert( RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

value_t last_value = *last;

if( comp(last_value, *first) )

{

copy_backward( first, last, last + 1 );

*first = last_value;

}

else

__unguarded_linear_insert( last, last_value, comp );

}

template< typename RandomAccessIterator, typename T,

typename StrictWeakOrdering >

void __unguarded_linear_insert( RandomAccessIterator last, T new_value,

StrictWeakOrdering comp )

{

RandomAccessIterator prev = last;

RandomAccessIterator result = last;

--prev;

while( comp(new_value, *prev) )

{

*result = *prev;

result = prev;

--prev;

}

if( result != last )

*result = new_value;

}

//-----------------------------------------------------------------------------

//应用于排序算法中的分割算法

template< typename RandomAccessIterator, typename T >

RandomAccessIterator __unguarded_partition( RandomAccessIterator first,

RandomAccessIterator last,

T pivot )

{

while( 1 )

{

while( *first < pivot )

++first;

--last;

while( pivot < *last )

--last;

if( !(first < last) )

return first;

iter_swap( first, last );

++first;

}

template< typename RandomAccessIterator, typename T,

typename StrictWeakOrdering >

RandomAccessIterator __unguarded_partition( RandomAccessIterator first,

RandomAccessIterator last,

T pivot,

StrictWeakOrdering comp )

{

while( 1 )

{

while( comp(*first, pivot) )

++first;

--last;

while( comp(pivot, *last) )

--last;

if( !(first < last) )

return first;

iter_swap( first, last );

++first;

}

//-----------------------------------------------------------------------------

template< typename RandomAccessIterator >

void partial_sort( RandomAccessIterator first, RandomAccessIterator middle,

RandomAccessIterator last )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type

value_t;

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

diff_t len = middle - first;

make_heap( first, middle );

for( RandomAccessIterator i = middle; i < last; ++i )

{

if( *i < *first )

{

value_t temp = *i;

*i = *first;

adjust_heap( first, diff_t(0), len, temp );

}

sort_heap( first, middle );

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void partial_sort( RandomAccessIterator first, RandomAccessIterator middle,

RandomAccessIterator last, StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type

value_t;

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

diff_t len = middle - first;

make_heap( first, middle, comp );

for( RandomAccessIterator i = middle; i < last; ++i )

{

if( *i < *first )

{

value_t temp = *i;

*i = *first;

adjust_heap( first, diff_t(0), len, temp, comp );

}

sort_heap( first, middle, comp );

}

//-----------------------------------------------------------------------------

template< typename InputIterator, typename RandomAccessIterator >

inline

RandomAccessIterator partial_sort_copy( InputIterator first,

InputIterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last )

{

typedef typename iterator_traits<InputIterator>::value_type

value_t1;

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t2;

if( result_first == result_last )

return result_first;

RandomAccessIterator temp = copy_range( first, last,

result_first, result_last );

partial_sort( result_first, temp, result_last );

return temp;

}

template< typename InputIterator, typename RandomAccessIterator,

typename StrictWeakOrdering >

inline

RandomAccessIterator partial_sort_copy( InputIterator first,

InputIterator last,

RandomAccessIterator result_first,

RandomAccessIterator result_last,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<InputIterator>::value_type

value_t1;

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t2;

if( result_first == result_last )

return result_first;

RandomAccessIterator temp = copy_range( first, last,

result_first, result_last );

partial_sort( result_first, temp, result_last, comp );

return temp;

}

//-----------------------------------------------------------------------------

template< typename RandomAccessIterator >

void nth_element( RandomAccessIterator first, RandomAccessIterator nth,

RandomAccessIterator last )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type

value_t;

while( last - first > 3 )

{

value_t mid = median( *first, *(first + (last - first) / 2),

*(last - 1) );

RandomAccessIterator cut = __unguarded_partition( first, last, mid );

if( cut <= nth )

first = cut;

else

last = cut;

}

insertion_sort( first, last );

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void nth_element( RandomAccessIterator first, RandomAccessIterator nth,

RandomAccessIterator last, StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type

value_t;

while( last - first > 3 )

{

value_t mid = median( *first, *(first + (last - first) / 2),

*(last - 1), comp );

RandomAccessIterator cut = __unguarded_partition( first, last,

mid, comp );

if( cut <= nth )

first = cut;

else

last = cut;

}

insertion_sort( first, last, comp );

}

//-----------------------------------------------------------------------------

static const int sort_threshold = 16; //阈值

template< typename Integer >

inline Integer __loop_num( Integer n ) //2^i <= n

{

Integer i = 0;

for( ; n > 1; n /= 2 )

++i;

return i;

}

template< typename RandomAccessIterator >

inline void sort( RandomAccessIterator first, RandomAccessIterator last )

{

if( first != last )

{

__introsort_loop( first, last, __loop_num(last - first) * 2 );

__final_insertion_sort( first, last );

}

template< typename RandomAccessIterator, typename Integer >

void __introsort_loop( RandomAccessIterator first, RandomAccessIterator last,

Integer depth_limit )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

while( last - first > sort_threshold )

{

if( depth_limit == 0 ) //分割次数已到最大

{

partial_sort( first, last, last ); //使用堆排序

return;

}

--depth_limit;

//选择分割点

value_t mid = median( *first, *(first + (last - first) / 2),

*(last - 1) );

RandomAccessIterator cut = __unguarded_partition( first, last, mid );

if( cut - first >= last - cut )

{

__introsort_loop( cut, last, depth_limit ); //对后半部分进行递归

last = cut;

}

else

{

__introsort_loop( first, cut, depth_limit ); //对前半部分进行递归

first = cut;

}

} //end while

}

template< typename RandomAccessIterator >

void __final_insertion_sort( RandomAccessIterator first,

RandomAccessIterator last )

{

if( last - first > sort_threshold ) //区间元素总数大于阈值

{

insertion_sort( first, first + sort_threshold );

//大于阈值长度的部分进行最后的插入排序

__unguarded_insertion_sort( first + sort_threshold, last );

}

else

insertion_sort( first, last );

}

template< typename RandomAccessIterator >

void __unguarded_insertion_sort( RandomAccessIterator first,

RandomAccessIterator last )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

for( RandomAccessIterator iter = first; iter != last; ++iter )

__unguarded_linear_insert( iter, *iter );

}

//使用functor进行比较的sort算法

template< typename RandomAccessIterator, typename StrictWeakOrdering >

inline void sort( RandomAccessIterator first, RandomAccessIterator last,

StrictWeakOrdering comp )

{

if( first != last )

{

__introsort_loop( first, last, __loop_num(last - first) * 2, comp );

__final_insertion_sort( first, last, comp );

}

template< typename RandomAccessIterator, typename Integer,

typename StrictWeakOrdering >

void __introsort_loop( RandomAccessIterator first, RandomAccessIterator last,

Integer depth_limit, StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

while( last - first > sort_threshold )

{

if( depth_limit == 0 )

{

partial_sort( first, last, last, comp );

return;

}

--depth_limit;

value_t mid = median( *first, *(first + (last - first) / 2),

*(last - 1), comp );

RandomAccessIterator cut = __unguarded_partition( first, last,

mid, comp );

if( cut - first >= last - cut )

{

__introsort_loop( cut, last, depth_limit, comp );

last = cut;

}

else

{

__introsort_loop( first, cut, depth_limit, comp );

first = cut;

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void __final_insertion_sort( RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering comp )

{

if( last - first > sort_threshold )

{

insertion_sort( first, first + sort_threshold, comp );

__unguarded_insertion_sort( first + sort_threshold, last, comp );

}

else

insertion_sort( first, last, comp );

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void __unguarded_insertion_sort( RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

for( RandomAccessIterator iter = first; iter != last; ++iter )

__unguarded_linear_insert( iter, *iter, comp );

}

//-----------------------------------------------------------------------------

const int stable_sort_chunk_size = 7;

const int inplace_stable_sort_threshold = 15;

template< typename RandomAccessIterator >

void stable_sort( RandomAccessIterator first, RandomAccessIterator last )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

temporary_buffer<RandomAccessIterator, value_t> buf( first, last );

if( !buf.begin() )

__inplace_stable_sort( first, last );

else

__stable_sort_adaptive( first, last, buf.begin(), buf.size() );

}

template< typename RandomAccessIterator, typename Pointer, typename Integer >

void __stable_sort_adaptive( RandomAccessIterator first,

RandomAccessIterator last,

Pointer buf,

Integer buf_size )

{

Integer half_len = (last - first + 1) / 2;

RandomAccessIterator middle = first + half_len;

if( buf_size < half_len ) //缓冲区空间不够

{

//进行递归调用直至被分的区间足够放进缓冲区

__stable_sort_adaptive( first, middle, buf, buf_size );

__stable_sort_adaptive( middle, last, buf, buf_size );

}

else //缓冲区空间足够则调用排序辅助函数进行排序

{

__merge_sort_with_buffer( first, middle, buf );

__merge_sort_with_buffer( middle, last, buf );

}

//调用inplace_merge的辅助函数对排序后的各区间进行合并

__merge_adaptive( first, middle, last, middle - first, last - middle,

buf, buf_size );

}

template< typename RandomAccessIterator, typename Pointer >

void __merge_sort_with_buffer( RandomAccessIterator first,

RandomAccessIterator last,

Pointer buf )

{

//该函数的缓冲足够放进区间内所有的元素

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

diff_t len = last - first;

Pointer buf_last = buf + len;

diff_t chunk_size = stable_sort_chunk_size;

//先对区间进行分段排序

__chunk_insertion_sort( first, last, chunk_size );

//对分段排序后的区间进行合并

while( chunk_size < len )

{

__merge_sort_loop( first, last, buf, chunk_size );

chunk_size *= 2;

__merge_sort_loop( buf, buf_last, first, chunk_size );

chunk_size *= 2;

}

template< typename RandomAccessIterator, typename Integer >

void __chunk_insertion_sort( RandomAccessIterator first,

RandomAccessIterator last,

Integer chunk_size )

{

//将区间分成每个大小为chunk_size的子区间，并分别进行插入排序

while( last - first >= chunk_size )

{

insertion_sort( first, first + chunk_size );

first += chunk_size;

}

//最后将余下不足chunk_size的元素进行插入排序

insertion_sort( first, last );

}

template< typename RandomAccessIterator1, typename RandomAccessIterator2,

typename Integer >

void __merge_sort_loop( RandomAccessIterator1 first,

RandomAccessIterator1 last,

RandomAccessIterator2 result,

Integer chunk_size )

{

Integer double_chunk = chunk_size * 2;

//对相邻两个chunk_size大小的区间进行合并

while( last - first >= double_chunk )

{

result = merge( first, first + chunk_size,

first + chunk_size, first + double_chunk, result );

first += double_chunk;

}

chunk_size = min( Integer(last - first), chunk_size );

merge( first, first + chunk_size, first + chunk_size, last, result );

}

template< typename RandomAccessIterator >

void __inplace_stable_sort( RandomAccessIterator first,

RandomAccessIterator last )

{

if( last - first < inplace_stable_sort_threshold )

{

insertion_sort( first, last );

return;

}

RandomAccessIterator middle = first + (last - first) / 2;

__inplace_stable_sort( first, middle );

__inplace_stable_sort( middle, last );

//调用inplace_merge的辅助函数进行合并

__merge_without_buffer( first, middle, last,

middle - first, last - middle );

}

//使用functor进行比较的stable_sort算法

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void stable_sort( RandomAccessIterator first, RandomAccessIterator last,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::value_type value_t;

temporary_buffer<RandomAccessIterator, value_t> buf( first, last );

if( !buf.begin() )

__inplace_stable_sort( first, last, comp );

else

__stable_sort_adaptive( first, last, buf.begin(), buf.size(), comp );

}

template< typename RandomAccessIterator, typename Pointer, typename Integer,

typename StrictWeakOrdering >

void __stable_sort_adaptive( RandomAccessIterator first,

RandomAccessIterator last,

Pointer buf,

Integer buf_size,

StrictWeakOrdering comp )

{

Integer half_len = (last - first + 1) / 2;

RandomAccessIterator middle = first + half_len;

if( buf_size < half_len )

{

__stable_sort_adaptive( first, middle, buf, buf_size, comp );

__stable_sort_adaptive( middle, last, buf, buf_size, comp );

}

else

{

__merge_sort_with_buffer( first, middle, buf, comp );

__merge_sort_with_buffer( middle, last, buf, comp );

}

__merge_adaptive( first, middle, last, middle - first, last - middle,

buf, buf_size, comp );

}

template< typename RandomAccessIterator, typename Pointer,

typename StrictWeakOrdering >

void __merge_sort_with_buffer( RandomAccessIterator first,

RandomAccessIterator last,

Pointer buf,

StrictWeakOrdering comp )

{

typedef typename iterator_traits<RandomAccessIterator>::difference_type

diff_t;

diff_t len = last - first;

Pointer buf_last = buf + len;

diff_t chunk_size = stable_sort_chunk_size;

__chunk_insertion_sort( first, last, chunk_size, comp );

while( chunk_size < len )

{

__merge_sort_loop( first, last, buf, chunk_size, comp );

chunk_size *= 2;

__merge_sort_loop( buf, buf_last, first, chunk_size, comp );

chunk_size *= 2;

}

template< typename RandomAccessIterator, typename Integer,

typename StrictWeakOrdering >

void __chunk_insertion_sort( RandomAccessIterator first,

RandomAccessIterator last,

Integer chunk_size,

StrictWeakOrdering comp )

{

while( last - first >= chunk_size )

{

insertion_sort( first, first + chunk_size, comp );

first += chunk_size;

}

insertion_sort( first, last, comp );

}

template< typename RandomAccessIterator1, typename RandomAccessIterator2,

typename Integer, typename StrictWeakOrdering >

void __merge_sort_loop( RandomAccessIterator1 first,

RandomAccessIterator1 last,

RandomAccessIterator2 result,

Integer chunk_size,

StrictWeakOrdering comp )

{

Integer double_chunk = chunk_size * 2;

while( last - first >= double_chunk )

{

result = merge( first, first + chunk_size,

first + chunk_size, first + double_chunk,

result, comp );

first += double_chunk;

}

chunk_size = min( Integer(last - first), chunk_size );

merge( first, first + chunk_size, first + chunk_size, last, result, comp );

}

template< typename RandomAccessIterator, typename StrictWeakOrdering >

void __inplace_stable_sort( RandomAccessIterator first,

RandomAccessIterator last,

StrictWeakOrdering comp )

{

if( last - first < inplace_stable_sort_threshold )

{

insertion_sort( first, last, comp );

return;

}

RandomAccessIterator middle = first + (last - first) / 2;

__inplace_stable_sort( first, middle, comp );

__inplace_stable_sort( middle, last, comp );

__merge_without_buffer( first, middle, last,

middle - first, last - middle, comp );

}

//-----------------------------------------------------------------------------

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__

#endif

//-----------------------------------------------------------------------------