algo.h

C++标准库源代码_C++ STL Source Code 请不要修改任何文件

			   	  OutputIterator result,
				  BinaryPredicate binary_pred) {
    if (first == last) return result;
    return __unique_copy(first, last, result, binary_pred,
			 iterator_category(result));
}

template <class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last) {
    first = adjacent_find(first, last);
    return unique_copy(first, last, first);
}

template <class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
		       BinaryPredicate binary_pred) {
    first = adjacent_find(first, last, binary_pred);
    return unique_copy(first, last, first, binary_pred);
}

template <class BidirectionalIterator>
void __reverse(BidirectionalIterator first, BidirectionalIterator last, 
	       bidirectional_iterator_tag) {
    while (true)
        if (first == last || first == --last)
	    return;
        else
	    iter_swap(first++, last);
}

template <class RandomAccessIterator>
void __reverse(RandomAccessIterator first, RandomAccessIterator last,
	       random_access_iterator_tag) {
    while (first < last) iter_swap(first++, --last);
}

template <class BidirectionalIterator>
inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    __reverse(first, last, iterator_category(first));
}

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
			    BidirectionalIterator last,
			    OutputIterator result) {
    while (first != last) *result++ = *--last;
    return result;
}

template <class ForwardIterator, class Distance>
void __rotate(ForwardIterator first, ForwardIterator middle,
	      ForwardIterator last, Distance*, forward_iterator_tag) {
    for (ForwardIterator i = middle; ;) {
	iter_swap(first++, i++);
	if (first == middle) {
	    if (i == last) return;
	    middle = i;
	} else if (i == last)
	    i = middle;
    }
}

template <class BidirectionalIterator, class Distance>
void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
	      BidirectionalIterator last, Distance*,
	      bidirectional_iterator_tag) {
    reverse(first, middle);
    reverse(middle, last);
    reverse(first, last);
}

template <class EuclideanRingElement>
EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
{
    while (n != 0) {
	EuclideanRingElement t = m % n;
	m = n;
	n = t;
    }
    return m;
}

template <class RandomAccessIterator, class Distance, class T>
void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
		    RandomAccessIterator initial, Distance shift, T*) {
    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 <class RandomAccessIterator, class Distance>
void __rotate(RandomAccessIterator first, RandomAccessIterator middle,
	      RandomAccessIterator last, Distance*,
	      random_access_iterator_tag) {
    Distance n = __gcd(last - first, middle - first);
    while (n--)
	__rotate_cycle(first, last, first + n, middle - first,
		       value_type(first));
}

template <class ForwardIterator>
inline void rotate(ForwardIterator first, ForwardIterator middle,
		   ForwardIterator last) {
    if (first == middle || middle == last) return;
    __rotate(first, middle, last, distance_type(first),
	     iterator_category(first));
}

template <class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
			   ForwardIterator last, OutputIterator result) {
    return copy(first, middle, copy(middle, last, result));
}

unsigned long __long_random(unsigned long);

template <class RandomAccessIterator, class Distance>
void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
		      Distance*) {
    if (first == last) return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
	iter_swap(i, first + Distance(__long_random((i - first) + 1)));
}

template <class RandomAccessIterator>
inline void random_shuffle(RandomAccessIterator first,
			   RandomAccessIterator last) {
    __random_shuffle(first, last, distance_type(first));
}

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
		    RandomNumberGenerator& rand) {
    if (first == last) return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)
	iter_swap(i, first + rand((i - first) + 1));
}

template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
				BidirectionalIterator last, Predicate pred) {
    while (true) {
	while (true)
	    if (first == last)
		return first;
	    else if (pred(*first))
		++first;
	    else
		break;
	--last;
	while (true)
	    if (first == last)
		return first;
	    else if (!pred(*last))
		--last;
	    else
		break;
	iter_swap(first, last);
	++first;
    }
}

template <class ForwardIterator, class Predicate, class Distance>
ForwardIterator __inplace_stable_partition(ForwardIterator first,
					   ForwardIterator last,
					   Predicate pred, Distance 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 - len / 2);
    rotate(first_cut, middle, second_cut);
    len = 0;
    distance(middle, second_cut, len);
    advance(first_cut, len);
    return first_cut;
}

template <class ForwardIterator, class Pointer, class Predicate,
	  class Distance, class T>
ForwardIterator __stable_partition_adaptive(ForwardIterator first,
					    ForwardIterator last,
					    Predicate pred, Distance len,
					    Pointer buffer,
					    Distance buffer_size,
					    Distance& fill_pointer, T*) {
    if (len <= buffer_size) {
	len = 0;
	ForwardIterator result1 = first;
	Pointer result2 = buffer;
	while (first != last && len < fill_pointer)
	    if (pred(*first))
		*result1++ = *first++;
	    else {
		*result2++ = *first++;
		++len;
	    }
	if (first != last) {
	    raw_storage_iterator<Pointer, T> result3 = result2;
	    while (first != last)           
		if (pred(*first))
		    *result1++ = *first++;
		else {
		    *result3++ = *first++;
		    ++len;
		}
	    fill_pointer = len;
	}
	copy(buffer, buffer + len, result1);
	return result1;
    }
    ForwardIterator middle = first;
    advance(middle, len / 2);
    ForwardIterator first_cut = __stable_partition_adaptive
	(first, middle, pred, len / 2, buffer, buffer_size, fill_pointer, 
	 (T*)0);
    ForwardIterator second_cut = __stable_partition_adaptive
	(middle, last, pred, len - len / 2, buffer, buffer_size, 
	 fill_pointer, (T*)0);
    rotate(first_cut, middle, second_cut);
    len = 0;
    distance(middle, second_cut, len);
    advance(first_cut, len);
    return first_cut;
}

template <class ForwardIterator, class Predicate, class Pointer,
	  class Distance>
ForwardIterator __stable_partition(ForwardIterator first, ForwardIterator last,
				   Predicate pred, Distance len,
				   pair<Pointer, Distance> p) {
    if (p.first == 0)
	return __inplace_stable_partition(first, last, pred, len);
    Distance fill_pointer = 0;
    ForwardIterator result = 
	__stable_partition_adaptive(first, last, pred, len, p.first, p.second,
				    fill_pointer, value_type(first)); 
    destroy(p.first, p.first + fill_pointer);
    return_temporary_buffer(p.first);
    return result;
}

template <class ForwardIterator, class Predicate, class Distance>
inline ForwardIterator __stable_partition_aux(ForwardIterator first,
					      ForwardIterator last, 
					      Predicate pred, Distance*) {
    Distance len = 0;
    distance(first, last, len);
    return __stable_partition(first, last, pred, len,
			      get_temporary_buffer(len, value_type(first)));
}

template <class ForwardIterator, class Predicate>
inline ForwardIterator stable_partition(ForwardIterator first,
					ForwardIterator last, 
					Predicate pred) {
    return __stable_partition_aux(first, last, pred, distance_type(first));
}

template <class RandomAccessIterator, class 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 <class RandomAccessIterator, class T, class Compare>
RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
					   RandomAccessIterator last, 
					   T pivot, Compare comp) {
    while (1) {
	while (comp(*first, pivot)) ++first;
	--last;
	while (comp(pivot, *last)) --last;
	if (!(first < last)) return first;
	iter_swap(first, last);
	++first;
    }
}

const int __stl_threshold = 16;

template <class RandomAccessIterator, class T>
void __quick_sort_loop_aux(RandomAccessIterator first,
			   RandomAccessIterator last, T*) {
    while (last - first > __stl_threshold) {
	RandomAccessIterator cut = __unguarded_partition
	    (first, last, T(__median(*first, *(first + (last - first)/2),
				     *(last - 1))));
	if (cut - first >= last - cut) {
	    __quick_sort_loop(cut, last);
	    last = cut;
	} else {
	    __quick_sort_loop(first, cut);
	    first = cut;
	}
    }
}

template <class RandomAccessIterator>
inline void __quick_sort_loop(RandomAccessIterator first,
			      RandomAccessIterator last) {
    __quick_sort_loop_aux(first, last, value_type(first));
}

template <class RandomAccessIterator, class T, class Compare>
void __quick_sort_loop_aux(RandomAccessIterator first, 
			   RandomAccessIterator last, T*, Compare comp) {
    while (last - first > __stl_threshold) {
	RandomAccessIterator cut = __unguarded_partition
	    (first, last, T(__median(*first, *(first + (last - first)/2), 
				   *(last - 1), comp)), comp);
	if (cut - first >= last - cut) {
	    __quick_sort_loop(cut, last, comp);
	    last = cut;
	} else {
	    __quick_sort_loop(first, cut, comp);
	    first = cut;
	}
    }
}

template <class RandomAccessIterator, class Compare>
inline void __quick_sort_loop(RandomAccessIterator first, 
			      RandomAccessIterator last, Compare comp) {
    __quick_sort_loop_aux(first, last, value_type(first), comp);
}

template <class RandomAccessIterator, class T>
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
    RandomAccessIterator next = last;
    --next;
    while (value < *next) {
	*last = *next;
	last = next--;
    }
    *last = value;
}

template <class RandomAccessIterator, class T, class Compare>
void __unguarded_linear_insert(RandomAccessIterator last, T value, 
			       Compare comp) {
    RandomAccessIterator next = last;
    --next;  
    while (comp(value , *next)) {
	*last = *next;
	last = next--;
    }
    *last = value;
}

template <class RandomAccessIterator, class T>
inline void __linear_insert(RandomAccessIterator first, 
			    RandomAccessIterator last, T*) {
    T value = *last;
    if (value < *first) {
	copy_backward(first, last, last + 1);
	*first = value;
    } else
	__unguarded_linear_insert(last, value);
}

template <class RandomAccessIterator, class T, class Compare>
inline void __linear_insert(RandomAccessIterator first, 
			    RandomAccessIterator last, T*, Compare comp) {
    T value = *last;
    if (comp(value, *first)) {
	copy_backward(first, last, last + 1);
	*first = value;
    } else
	__unguarded_linear_insert(last, value, comp);
}

template <class RandomAccessIterator>
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first == last) return; 
    for (RandomAccessIterator i = first + 1; i != last; ++i)
	__linear_insert(first, i, value_type(first));
}

template <class RandomAccessIterator, class Compare>
void __insertion_sort(RandomAccessIterator first,
		      RandomAccessIterator last, Compare comp) {
    if (first == last) return;
    for (RandomAccessIterator i = first + 1; i != last; ++i)