_algo.c File Reference

#include <stl/_algo.h>
#include <stl/_tempbuf.h>

Go to the source code of this file.

Defines
#define	_STLP_ALGO_C
#define	__stl_threshold   16
Functions
template<class _BidirectionalIter , class _Distance , class _Compare >
_STLP_BEGIN_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE void	__merge_without_buffer (_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Compare __comp)
template<class _BidirectionalIter1 , class _BidirectionalIter2 , class _BidirectionalIter3 , class _Compare >
_BidirectionalIter3	__merge_backward (_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result, _Compare __comp)
template<class _Tp >
const _Tp &	__median (const _Tp &__a, const _Tp &__b, const _Tp &__c)
template<class _Tp , class _Compare >
const _Tp &	__median (const _Tp &__a, const _Tp &__b, const _Tp &__c, _Compare __comp)
template<class _ForwardIter1 , class _ForwardIter2 >
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter1	search (_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2)
template<class _RandomAccessIter , class _Integer , class _Tp , class _BinaryPred , class _Distance >
_STLP_MOVE_TO_PRIV_NAMESPACE _RandomAccessIter	__search_n (_RandomAccessIter __first, _RandomAccessIter __last, _Integer __count, const _Tp &__val, _BinaryPred __pred, _Distance *, const random_access_iterator_tag &)
template<class _ForwardIter , class _Integer , class _Tp , class _Distance , class _BinaryPred >
_ForwardIter	__search_n (_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp &__val, _BinaryPred __pred, _Distance *, const forward_iterator_tag &)
template<class _ForwardIter , class _Integer , class _Tp >
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter	search_n (_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp &__val)
template<class _ForwardIter , class _Integer , class _Tp , class _BinaryPred >
_ForwardIter	search_n (_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp &__val, _BinaryPred __binary_pred)
template<class _ForwardIter1 , class _ForwardIter2 >
_ForwardIter1	find_end (_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2)
template<class _InputIterator , class _OutputIterator , class _BinaryPredicate , class _Tp >
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP _OutputIterator	__unique_copy (_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, _Tp *)
template<class _InputIter , class _OutputIter , class _BinaryPredicate >
_OutputIter	__unique_copy (_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred, const output_iterator_tag &)
template<class _InputIter , class _ForwardIter , class _BinaryPredicate >
_STLP_INLINE_LOOP _ForwardIter	__unique_copy (_InputIter __first, _InputIter __last, _ForwardIter __result, _BinaryPredicate __binary_pred, const forward_iterator_tag &)
template<class _InputIter , class _OutputIter >
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter	unique_copy (_InputIter __first, _InputIter __last, _OutputIter __result)
template<class _InputIter , class _OutputIter , class _BinaryPredicate >
_OutputIter	unique_copy (_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred)
template<class _ForwardIter , class _Distance >
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter	__rotate_aux (_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last, _Distance *, const forward_iterator_tag &)
template<class _BidirectionalIter , class _Distance >
_BidirectionalIter	__rotate_aux (_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance *, const bidirectional_iterator_tag &)
template<class _EuclideanRingElement >
_STLP_INLINE_LOOP _EuclideanRingElement	__gcd (_EuclideanRingElement __m, _EuclideanRingElement __n)
template<class _RandomAccessIter , class _Distance , class _Tp >
_RandomAccessIter	__rotate_aux (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Distance *, _Tp *)
template<class _RandomAccessIter , class _Distance >
_RandomAccessIter	__rotate_aux (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Distance *__dis, const random_access_iterator_tag &)
template<class _ForwardIter >
_ForwardIter	__rotate (_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
template<class _ForwardIter >
_STLP_MOVE_TO_STD_NAMESPACE void	rotate (_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
template<class _Distance >
_STLP_MOVE_TO_PRIV_NAMESPACE _Distance	__random_number (_Distance __n)
template<class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE void	random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last)
template<class _RandomAccessIter , class _RandomNumberGenerator >
void	random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last, _RandomNumberGenerator &__rand)
template<class _ForwardIter , class _OutputIter , class _Distance >
_OutputIter	random_sample_n (_ForwardIter __first, _ForwardIter __last, _OutputIter __out_ite, const _Distance __n)
template<class _ForwardIter , class _OutputIter , class _Distance , class _RandomNumberGenerator >
_OutputIter	random_sample_n (_ForwardIter __first, _ForwardIter __last, _OutputIter __out_ite, const _Distance __n, _RandomNumberGenerator &__rand)
template<class _InputIter , class _RandomAccessIter , class _Distance >
_STLP_MOVE_TO_PRIV_NAMESPACE _RandomAccessIter	__random_sample (_InputIter __first, _InputIter __last, _RandomAccessIter __out_ite, const _Distance __n)
template<class _InputIter , class _RandomAccessIter , class _RandomNumberGenerator , class _Distance >
_RandomAccessIter	__random_sample (_InputIter __first, _InputIter __last, _RandomAccessIter __out_ite, _RandomNumberGenerator &__rand, const _Distance __n)
template<class _InputIter , class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE _RandomAccessIter	random_sample (_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last)
template<class _InputIter , class _RandomAccessIter , class _RandomNumberGenerator >
_RandomAccessIter	random_sample (_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last, _RandomNumberGenerator &__rand)
template<class _ForwardIter , class _Predicate >
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP _ForwardIter	__partition (_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const forward_iterator_tag &)
template<class _BidirectionalIter , class _Predicate >
_STLP_INLINE_LOOP _BidirectionalIter	__partition (_BidirectionalIter __first, _BidirectionalIter __last, _Predicate __pred, const bidirectional_iterator_tag &)
template<class _ForwardIter , class _Predicate >
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter	partition (_ForwardIter __first, _ForwardIter __last, _Predicate __pred)
template<class _ForwardIter , class _Predicate , class _Distance >
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter	__inplace_stable_partition (_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Distance __len, bool __pred_of_first, bool __pred_of_before_last)
template<class _ForwardIter , class _Pointer , class _Predicate , class _Distance >
_ForwardIter	__stable_partition_adaptive (_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size, bool __pred_of_first, bool __pred_of_before_last)
template<class _ForwardIter , class _Predicate , class _Tp , class _Distance >
_ForwardIter	__stable_partition_aux_aux (_ForwardIter __first, _ForwardIter __last, _Predicate __pred, _Tp *, _Distance *, bool __pred_of_before_last)
template<class _ForwardIter , class _Predicate >
_ForwardIter	__stable_partition_aux (_ForwardIter __first, _ForwardIter __last, _Predicate __pred, const forward_iterator_tag &)
template<class _BidirectIter , class _Predicate >
_BidirectIter	__stable_partition_aux (_BidirectIter __first, _BidirectIter __last, _Predicate __pred, const bidirectional_iterator_tag &)
template<class _ForwardIter , class _Predicate >
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter	stable_partition (_ForwardIter __first, _ForwardIter __last, _Predicate __pred)
template<class _RandomAccessIter , class _Tp , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE _RandomAccessIter	__unguarded_partition (_RandomAccessIter __first, _RandomAccessIter __last, _Tp __pivot, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Compare >
void	__unguarded_linear_insert (_RandomAccessIter __last, _Tp __val, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Compare >
void	__linear_insert (_RandomAccessIter __first, _RandomAccessIter __last, _Tp __val, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Compare >
void	__insertion_sort (_RandomAccessIter __first, _RandomAccessIter __last, _Tp *, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Compare >
void	__unguarded_insertion_sort_aux (_RandomAccessIter __first, _RandomAccessIter __last, _Tp *, _Compare __comp)
template<class _RandomAccessIter , class _Compare >
void	__unguarded_insertion_sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
template<class _RandomAccessIter , class _Compare >
void	__final_insertion_sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Size , class _Compare >
void	__introsort_loop (_RandomAccessIter __first, _RandomAccessIter __last, _Tp *, _Size __depth_limit, _Compare __comp)
template<class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE void	sort (_RandomAccessIter __first, _RandomAccessIter __last)
template<class _RandomAccessIter , class _Compare >
void	sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
template<class _RandomAccessIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE void	__inplace_stable_sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
template<class _RandomAccessIter1 , class _RandomAccessIter2 , class _Distance , class _Compare >
void	__merge_sort_loop (_RandomAccessIter1 __first, _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size, _Compare __comp)
template<class _RandomAccessIter , class _Distance , class _Compare >
void	__chunk_insertion_sort (_RandomAccessIter __first, _RandomAccessIter __last, _Distance __chunk_size, _Compare __comp)
template<class _RandomAccessIter , class _Pointer , class _Distance , class _Compare >
void	__merge_sort_with_buffer (_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance *, _Compare __comp)
template<class _BidirectionalIter1 , class _BidirectionalIter2 , class _Distance >
_BidirectionalIter1	__rotate_adaptive (_BidirectionalIter1 __first, _BidirectionalIter1 __middle, _BidirectionalIter1 __last, _Distance __len1, _Distance __len2, _BidirectionalIter2 __buffer, _Distance __buffer_size)
template<class _BidirectionalIter , class _Distance , class _Pointer , class _Compare >
void	__merge_adaptive (_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
template<class _RandomAccessIter , class _Pointer , class _Distance , class _Compare >
void	__stable_sort_adaptive (_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Distance , class _Compare >
void	__stable_sort_aux (_RandomAccessIter __first, _RandomAccessIter __last, _Tp *, _Distance *, _Compare __comp)
template<class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE void	stable_sort (_RandomAccessIter __first, _RandomAccessIter __last)
template<class _RandomAccessIter , class _Compare >
void	stable_sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE void	__partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp *, _Compare __comp)
template<class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE void	partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last)
template<class _RandomAccessIter , class _Compare >
void	partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Compare __comp)
template<class _InputIter , class _RandomAccessIter , class _Compare , class _Distance , class _Tp >
_STLP_MOVE_TO_PRIV_NAMESPACE _RandomAccessIter	__partial_sort_copy (_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp, _Distance *, _Tp *)
template<class _InputIter , class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE _RandomAccessIter	partial_sort_copy (_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last)
template<class _InputIter , class _RandomAccessIter , class _Compare >
_RandomAccessIter	partial_sort_copy (_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp)
template<class _RandomAccessIter , class _Tp , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE void	__nth_element (_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Tp *, _Compare __comp)
template<class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE void	nth_element (_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last)
template<class _RandomAccessIter , class _Compare >
void	nth_element (_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Compare __comp)
template<class _ForwardIter , class _Tp , class _Compare1 , class _Compare2 , class _Distance >
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter	__upper_bound (_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *)
template<class _ForwardIter , class _Tp , class _Compare1 , class _Compare2 , class _Distance >
pair< _ForwardIter, _ForwardIter >	__equal_range (_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *__dist)
template<class _InputIter1 , class _InputIter2 , class _OutputIter >
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter	merge (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_OutputIter	merge (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _BidirectionalIter , class _Tp , class _Distance , class _Compare >
void	__inplace_merge_aux (_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Tp *, _Distance *, _Compare __comp)
template<class _BidirectionalIter >
_STLP_MOVE_TO_STD_NAMESPACE void	inplace_merge (_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last)
template<class _BidirectionalIter , class _Compare >
void	inplace_merge (_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE bool	__includes (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _Compare >
_STLP_MOVE_TO_STD_NAMESPACE bool	includes (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Compare __comp)
template<class _InputIter1 , class _InputIter2 >
bool	includes (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter	__set_union (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter >
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter	set_union (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_OutputIter	set_union (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter	__set_intersection (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter >
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter	set_intersection (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_OutputIter	set_intersection (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter	__set_difference (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter >
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter	set_difference (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_OutputIter	set_difference (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE _OutputIter	__set_symmetric_difference (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _InputIter1 , class _InputIter2 , class _OutputIter >
_STLP_MOVE_TO_STD_NAMESPACE _OutputIter	set_symmetric_difference (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result)
template<class _InputIter1 , class _InputIter2 , class _OutputIter , class _Compare >
_OutputIter	set_symmetric_difference (_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp)
template<class _ForwardIter >
_ForwardIter	max_element (_ForwardIter __first, _ForwardIter __last)
template<class _ForwardIter , class _Compare >
_ForwardIter	max_element (_ForwardIter __first, _ForwardIter __last, _Compare __comp)
template<class _ForwardIter >
_ForwardIter	min_element (_ForwardIter __first, _ForwardIter __last)
template<class _ForwardIter , class _Compare >
_ForwardIter	min_element (_ForwardIter __first, _ForwardIter __last, _Compare __comp)
template<class _BidirectionalIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE bool	__next_permutation (_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp)
template<class _BidirectionalIter >
_STLP_MOVE_TO_STD_NAMESPACE bool	next_permutation (_BidirectionalIter __first, _BidirectionalIter __last)
template<class _BidirectionalIter , class _Compare >
bool	next_permutation (_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp)
template<class _BidirectionalIter , class _Compare >
_STLP_MOVE_TO_PRIV_NAMESPACE bool	__prev_permutation (_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp)
template<class _BidirectionalIter >
_STLP_MOVE_TO_STD_NAMESPACE bool	prev_permutation (_BidirectionalIter __first, _BidirectionalIter __last)
template<class _BidirectionalIter , class _Compare >
bool	prev_permutation (_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp)
template<class _RandomAccessIter , class _Distance , class _StrictWeakOrdering >
_STLP_MOVE_TO_PRIV_NAMESPACE bool	__is_heap (_RandomAccessIter __first, _StrictWeakOrdering __comp, _Distance __n)
template<class _RandomAccessIter >
_STLP_MOVE_TO_STD_NAMESPACE bool	is_heap (_RandomAccessIter __first, _RandomAccessIter __last)
template<class _RandomAccessIter , class _StrictWeakOrdering >
bool	is_heap (_RandomAccessIter __first, _RandomAccessIter __last, _StrictWeakOrdering __comp)
template<class _ForwardIter , class _StrictWeakOrdering >
_STLP_MOVE_TO_PRIV_NAMESPACE bool	__is_sorted (_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp)
Variables
const int	__stl_chunk_size = 7