algo.h

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

	__linear_insert(first, i, value_type(first), comp);
}

template <class RandomAccessIterator, class T>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
				    RandomAccessIterator last, T*) {
    for (RandomAccessIterator i = first; i != last; ++i)
	__unguarded_linear_insert(i, T(*i));
}

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

template <class RandomAccessIterator, class T, class Compare>
void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
				    RandomAccessIterator last,
				    T*, Compare comp) {
    for (RandomAccessIterator i = first; i != last; ++i)
	__unguarded_linear_insert(i, T(*i), comp);
}

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

template <class RandomAccessIterator>
void __final_insertion_sort(RandomAccessIterator first, 
			    RandomAccessIterator last) {
    if (last - first > __stl_threshold) {
	__insertion_sort(first, first + __stl_threshold);
	__unguarded_insertion_sort(first + __stl_threshold, last);
    } else
	__insertion_sort(first, last);
}

template <class RandomAccessIterator, class Compare>
void __final_insertion_sort(RandomAccessIterator first, 
			    RandomAccessIterator last, Compare comp) {
    if (last - first > __stl_threshold) {
	__insertion_sort(first, first + __stl_threshold, comp);
	__unguarded_insertion_sort(first + __stl_threshold, last, comp);
    } else
	__insertion_sort(first, last, comp);
}

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last) {
    __quick_sort_loop(first, last);
    __final_insertion_sort(first, last);
}

template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
	  Compare comp) {
   __quick_sort_loop(first, last, comp);
   __final_insertion_sort(first, last, comp);
}

template <class RandomAccessIterator>
void __inplace_stable_sort(RandomAccessIterator first,
			   RandomAccessIterator last) {
    if (last - first < 15) {
	__insertion_sort(first, last);
	return;
    }
    RandomAccessIterator middle = first + (last - first) / 2;
    __inplace_stable_sort(first, middle);
    __inplace_stable_sort(middle, last);
    __merge_without_buffer(first, middle, last, middle - first, last - middle);
}

template <class RandomAccessIterator, class Compare>
void __inplace_stable_sort(RandomAccessIterator first,
			   RandomAccessIterator last, Compare comp) {
    if (last - first < 15) {
	__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);
}

template <class RandomAccessIterator1, class RandomAccessIterator2,
	  class Distance>
void __merge_sort_loop(RandomAccessIterator1 first,
		       RandomAccessIterator1 last, 
		       RandomAccessIterator2 result, Distance step_size) {
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
	result = merge(first, first + step_size,
		       first + step_size, first + two_step, result);
	first += two_step;
    }
    step_size = min(Distance(last - first), step_size);

    merge(first, first + step_size, first + step_size, last, result);
}

template <class RandomAccessIterator1, class RandomAccessIterator2,
	  class Distance, class Compare>
void __merge_sort_loop(RandomAccessIterator1 first,
		       RandomAccessIterator1 last, 
		       RandomAccessIterator2 result, Distance step_size,
		       Compare comp) {
    Distance two_step = 2 * step_size;

    while (last - first >= two_step) {
	result = merge(first, first + step_size,
		       first + step_size, first + two_step, result, comp);
	first += two_step;
    }
    step_size = min(Distance(last - first), step_size);

    merge(first, first + step_size, first + step_size, last, result, comp);
}

const int __stl_chunk_size = 7;
	
template <class RandomAccessIterator, class Distance>
void __chunk_insertion_sort(RandomAccessIterator first, 
			      RandomAccessIterator last, Distance chunk_size) {
    while (last - first >= chunk_size) {
	__insertion_sort(first, first + chunk_size);
	first += chunk_size;
    }
    __insertion_sort(first, last);
}

template <class RandomAccessIterator, class Distance, class Compare>
void __chunk_insertion_sort(RandomAccessIterator first, 
			    RandomAccessIterator last,
			    Distance chunk_size, Compare comp) {
    while (last - first >= chunk_size) {
	__insertion_sort(first, first + chunk_size, comp);
	first += chunk_size;
    }
    __insertion_sort(first, last, comp);
}

template <class RandomAccessIterator, class Pointer, class Distance, class T>
void __merge_sort_with_buffer(RandomAccessIterator first, 
			      RandomAccessIterator last,
			      Pointer buffer, Distance*, T*) {
    Distance len = last - first;
    Pointer buffer_last = buffer + len;

    Distance step_size = __stl_chunk_size;
    __chunk_insertion_sort(first, last, step_size);

    while (step_size < len) {
	__merge_sort_loop(first, last, buffer, step_size);
	step_size *= 2;
	__merge_sort_loop(buffer, buffer_last, first, step_size);
	step_size *= 2;
    }
}

template <class RandomAccessIterator, class Pointer, class Distance, class T,
	  class Compare>
void __merge_sort_with_buffer(RandomAccessIterator first, 
			      RandomAccessIterator last, Pointer buffer,
			      Distance*, T*, Compare comp) {
    Distance len = last - first;
    Pointer buffer_last = buffer + len;

    Distance step_size = __stl_chunk_size;
    __chunk_insertion_sort(first, last, step_size, comp);

    while (step_size < len) {
	__merge_sort_loop(first, last, buffer, step_size, comp);
	step_size *= 2;
	__merge_sort_loop(buffer, buffer_last, first, step_size, comp);
	step_size *= 2;
    }
}

template <class RandomAccessIterator, class Pointer, class Distance, class T>
void __stable_sort_adaptive(RandomAccessIterator first, 
			    RandomAccessIterator last, Pointer buffer,
			    Distance buffer_size, T*) {
    Distance len = (last - first + 1) / 2;
    RandomAccessIterator middle = first + len;
    if (len > buffer_size) {
	__stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0);
	__stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0);
    } else {
	__merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0);
	__merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0);
    }
    __merge_adaptive(first, middle, last, Distance(middle - first), 
		     Distance(last - middle), buffer, buffer_size, (T*)0);
}

template <class RandomAccessIterator, class Pointer, class Distance, class T,
	  class Compare>
void __stable_sort_adaptive(RandomAccessIterator first, 
			    RandomAccessIterator last, Pointer buffer,
			    Distance buffer_size, T*, Compare comp) {
    Distance len = (last - first + 1) / 2;
    RandomAccessIterator middle = first + len;
    if (len > buffer_size) {
	__stable_sort_adaptive(first, middle, buffer, buffer_size, (T*)0, comp);
	__stable_sort_adaptive(middle, last, buffer, buffer_size, (T*)0, comp);
    } else {
	__merge_sort_with_buffer(first, middle, buffer, (Distance*)0, (T*)0,
				 comp);
	__merge_sort_with_buffer(middle, last, buffer, (Distance*)0, (T*)0,
				 comp);
    }
    __merge_adaptive(first, middle, last, Distance(middle - first), 
		     Distance(last - middle), buffer, buffer_size, (T*)0, comp);
}

template <class RandomAccessIterator, class Pointer, class Distance, class T>
inline void __stable_sort(RandomAccessIterator first,
			  RandomAccessIterator last,
			  pair<Pointer, Distance> p, T*) {
    if (p.first == 0) {
	__inplace_stable_sort(first, last);
	return;
    }
    Distance len = min(p.second, last - first);
    copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first));
    __stable_sort_adaptive(first, last, p.first, p.second, (T*)0);
    destroy(p.first, p.first + len);
    return_temporary_buffer(p.first);
}

template <class RandomAccessIterator, class Pointer, class Distance, class T,
	  class Compare>
inline void __stable_sort(RandomAccessIterator first,
			  RandomAccessIterator last,
			  pair<Pointer, Distance> p, T*, Compare comp) {
    if (p.first == 0) {
	__inplace_stable_sort(first, last, comp);
	return;
    }
    Distance len = min(p.second, last - first);
    copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first));
    __stable_sort_adaptive(first, last, p.first, p.second, (T*)0, comp);
    destroy(p.first, p.first + len);
    return_temporary_buffer(p.first);
}

template <class RandomAccessIterator, class T, class Distance>
inline void __stable_sort_aux(RandomAccessIterator first,
			      RandomAccessIterator last, T*, Distance*) {
    __stable_sort(first, last, get_temporary_buffer(Distance(last - first),
						    (T*)0), (T*)0);
}

template <class RandomAccessIterator, class T, class Distance, class Compare>
inline void __stable_sort_aux(RandomAccessIterator first,
			      RandomAccessIterator last, T*, Distance*,
			      Compare comp) {
    __stable_sort(first, last, get_temporary_buffer(Distance(last - first),
						    (T*)0), (T*)0, comp);
}

template <class RandomAccessIterator>
inline void stable_sort(RandomAccessIterator first,
			RandomAccessIterator last) {
    __stable_sort_aux(first, last, value_type(first), distance_type(first));
}

template <class RandomAccessIterator, class Compare>
inline void stable_sort(RandomAccessIterator first,
			RandomAccessIterator last, Compare comp) {
    __stable_sort_aux(first, last, value_type(first), distance_type(first), 
		      comp);
}

template <class RandomAccessIterator, class T>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
		    RandomAccessIterator last, T*) {
    make_heap(first, middle);
    for (RandomAccessIterator i = middle; i < last; ++i)
	if (*i < *first) 
	  __pop_heap(first, middle, i, T(*i), distance_type(first));
    sort_heap(first, middle);
}

template <class RandomAccessIterator>
inline void partial_sort(RandomAccessIterator first,
			 RandomAccessIterator middle,
			 RandomAccessIterator last) {
    __partial_sort(first, middle, last, value_type(first));
}

template <class RandomAccessIterator, class T, class Compare>
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
		    RandomAccessIterator last, T*, Compare comp) {
    make_heap(first, middle, comp);
    for (RandomAccessIterator i = middle; i < last; ++i)
	if (comp(*i, *first))
	  __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
    sort_heap(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void partial_sort(RandomAccessIterator first,
			 RandomAccessIterator middle,
			 RandomAccessIterator last, Compare comp) {
    __partial_sort(first, middle, last, value_type(first), comp);
}

template <class InputIterator, class RandomAccessIterator, class Distance,
          class T>
RandomAccessIterator __partial_sort_copy(InputIterator first,
					 InputIterator last,
					 RandomAccessIterator result_first,
					 RandomAccessIterator result_last, 
					 Distance*, T*) {
    if (result_first == result_last) return result_last;
    RandomAccessIterator result_real_last = result_first;
    while(first != last && result_real_last != result_last)
	*result_real_last++ = *first++;
    make_heap(result_first, result_real_last);
    while (first != last) {
	if (*first < *result_first) 
	    __adjust_heap(result_first, Distance(0),
			  Distance(result_real_last - result_first), T(*first));
	++first;
    }
    sort_heap(result_first, result_real_last);
    return result_real_last;
}

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
		  RandomAccessIterator result_first,
		  RandomAccessIterator result_last) {
    return __partial_sort_copy(first, last, result_first, result_last, 
			       distance_type(result_first), value_type(first));
}

template <class InputIterator, class RandomAccessIterator, class Compare,
          class Distance, class T>
RandomAccessIterator __partial_sort_copy(InputIterator first,
					 InputIterator last,
					 RandomAccessIterator result_first,
					 RandomAccessIterator result_last,
					 Compare comp, Distance*, T*) {
    if (result_first == result_last) return result_last;
    RandomAccessIterator result_real_last = result_first;
    while(first != last && result_real_last != result_last)
	*result_real_last++ = *first++;
    make_heap(result_first, result_real_last, comp);
    while (first != last) {
	if (comp(*first, *result_first))
	    __adjust_heap(result_first, Distance(0),
			  Distance(result_real_last - result_first), T(*first),
			  comp);
	++first;
    }
    sort_heap(result_first, result_real_last, comp);
    return result_real_last;
}

template <class InputIterator, class RandomAccessIterator, class Compare>
inline RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
		  RandomAccessIterator result_first,
		  RandomAccessIterator result_last, Compare comp) {
    return __partial_sort_copy(first, last, result_first, result_last, comp,
			       distance_type(result_first), value_type(first));
}

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

template <class RandomAccessIterator>
inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
			RandomAccessIterator last) {
    __nth_element(first, nth, last, value_type(first));
}

template <class RandomAccessIterator, class T, class Compare>
void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
		   RandomAccessIterator last, T*, Compare comp) {
    while (last - first > 3) {