algo.h

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

    ForwardIterator i = lower_bound(first, last, value);
    return i != last && !(value < *i);
}

template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
		   Compare comp) {
    ForwardIterator i = lower_bound(first, last, value, comp);
    return i != last && !comp(value, *i);
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
		     InputIterator2 first2, InputIterator2 last2,
		     OutputIterator result) {
    while (first1 != last1 && first2 != last2)
	if (*first2 < *first1)
	    *result++ = *first2++;
	else
	    *result++ = *first1++;
    return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
	  class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
		     InputIterator2 first2, InputIterator2 last2,
		     OutputIterator result, Compare comp) {
    while (first1 != last1 && first2 != last2)
	if (comp(*first2, *first1))
	    *result++ = *first2++;
	else
	    *result++ = *first1++;
    return copy(first2, last2, copy(first1, last1, result));
}

template <class BidirectionalIterator, class Distance>
void __merge_without_buffer(BidirectionalIterator first,
			    BidirectionalIterator middle,
			    BidirectionalIterator last,
			    Distance len1, Distance len2) {
    if (len1 == 0 || len2 == 0) return;
    if (len1 + len2 == 2) {
	if (*middle < *first) iter_swap(first, middle);
	return;
    }
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;
    if (len1 > len2) {
	len11 = len1 / 2;
	advance(first_cut, len11);
	second_cut = lower_bound(middle, last, *first_cut);
	distance(middle, second_cut, len22);
    } else {
	len22 = len2 / 2;
	advance(second_cut, len22);
	first_cut = upper_bound(first, middle, *second_cut);
	distance(first, first_cut, len11);
    }
    rotate(first_cut, middle, second_cut);
    BidirectionalIterator new_middle = first_cut;
    advance(new_middle, len22);
    __merge_without_buffer(first, first_cut, new_middle, len11, len22);
    __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
			   len2 - len22);
}

template <class BidirectionalIterator, class Distance, class Compare>
void __merge_without_buffer(BidirectionalIterator first,
			    BidirectionalIterator middle,
			    BidirectionalIterator last,
			    Distance len1, Distance len2, Compare comp) {
    if (len1 == 0 || len2 == 0) return;
    if (len1 + len2 == 2) {
	if (comp(*middle, *first)) iter_swap(first, middle);
	return;
    }
    BidirectionalIterator first_cut = first;
    BidirectionalIterator second_cut = middle;
    Distance len11 = 0;
    Distance len22 = 0;
    if (len1 > len2) {
	len11 = len1 / 2;
	advance(first_cut, len11);
	second_cut = lower_bound(middle, last, *first_cut, comp);
	distance(middle, second_cut, len22);
    } else {
	len22 = len2 / 2;
	advance(second_cut, len22);
	first_cut = upper_bound(first, middle, *second_cut, comp);
	distance(first, first_cut, len11);
    }
    rotate(first_cut, middle, second_cut);
    BidirectionalIterator new_middle = first_cut;
    advance(new_middle, len22);
    __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
    __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
			   len2 - len22, comp);
}


template <class InputIterator, class OutputIterator>
OutputIterator __borland_bugfix_copy(InputIterator first, InputIterator last,
		    OutputIterator result) {
// this is used in __rotate_adaptive to work around some obscure Borland
// bug. It is the same as copy, but with a different (and appropriate) name.
    while (first != last) *result++ = *first++;
    return result;
}

template <class BidirectionalIterator1, class BidirectionalIterator2,
	  class Distance>
BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first,
					 BidirectionalIterator1 middle,
					 BidirectionalIterator1 last,
					 Distance len1, Distance len2,
					 BidirectionalIterator2 buffer,
					 Distance buffer_size) {
    BidirectionalIterator2 buffer_end;
    if (len1 > len2 && len2 <= buffer_size) {
	buffer_end = __borland_bugfix_copy(middle, last, buffer);
	copy_backward(first, middle, last);
	return copy(buffer, buffer_end, first);
    } else if (len1 <= buffer_size) {
	buffer_end = __borland_bugfix_copy(first, middle, buffer);
	copy(middle, last, first);
	return copy_backward(buffer, buffer_end, last);
    } else  {
	rotate(first, middle, last);
	advance(first, len2);
	return first;
    }
}

template <class BidirectionalIterator1, class BidirectionalIterator2,
	  class BidirectionalIterator3>
BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
					BidirectionalIterator1 last1,
					BidirectionalIterator2 first2,
					BidirectionalIterator2 last2,
					BidirectionalIterator3 result) {
    if (first1 == last1) return copy_backward(first2, last2, result);
    if (first2 == last2) return copy_backward(first1, last1, result);
    --last1;
    --last2;
    while (true) {
	if (*last2 < *last1) {
	    *--result = *last1;
	    if (first1 == last1) return copy_backward(first2, ++last2, result);
	    --last1;
	} else {
	    *--result = *last2;
	    if (first2 == last2) return copy_backward(first1, ++last1, result);
	    --last2;
	}
    }
}

template <class BidirectionalIterator1, class BidirectionalIterator2,
	  class BidirectionalIterator3, class Compare>
BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
					BidirectionalIterator1 last1,
					BidirectionalIterator2 first2,
					BidirectionalIterator2 last2,
					BidirectionalIterator3 result,
					Compare comp) {
    if (first1 == last1) return copy_backward(first2, last2, result);
    if (first2 == last2) return copy_backward(first1, last1, result);
    --last1;
    --last2;
    while (true) {
	if (comp(*last2, *last1)) {
	    *--result = *last1;
	    if (first1 == last1) return copy_backward(first2, ++last2, result);
	    --last1;
	} else {
	    *--result = *last2;
	    if (first2 == last2) return copy_backward(first1, ++last1, result);
	    --last2;
	}
    }
}

template <class BidirectionalIterator, class Distance, class Pointer, class T>
void __merge_adaptive(BidirectionalIterator first, 
		      BidirectionalIterator middle, 
		      BidirectionalIterator last, Distance len1, Distance len2,
		      Pointer buffer, Distance buffer_size, T*) {
    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;
	Distance len11 = 0;
	Distance len22 = 0;
	if (len1 > len2) {
	    len11 = len1 / 2;
	    advance(first_cut, len11);
	    second_cut = lower_bound(middle, last, *first_cut);
	    distance(middle, second_cut, len22);   
	} else {
	    len22 = len2 / 2;
	    advance(second_cut, len22);
	    first_cut = upper_bound(first, middle, *second_cut);
	    distance(first, first_cut, len11);
	}
	BidirectionalIterator new_middle =
	    __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
			      len22, buffer, buffer_size);
	__merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
			 buffer_size, (T*)0);
	__merge_adaptive(new_middle, second_cut, last, len1 - len11,
			 len2 - len22, buffer, buffer_size, (T*)0);
    }
}

template <class BidirectionalIterator, class Distance, class Pointer, class T,
	  class Compare>
void __merge_adaptive(BidirectionalIterator first, 
		      BidirectionalIterator middle, 
		      BidirectionalIterator last, Distance len1, Distance len2,
		      Pointer buffer, Distance buffer_size, T*, Compare 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;
	Distance len11 = 0;
	Distance len22 = 0;
	if (len1 > len2) {
	    len11 = len1 / 2;
	    advance(first_cut, len11);
	    second_cut = lower_bound(middle, last, *first_cut, comp);
	    distance(middle, second_cut, len22);   
	} else {
	    len22 = len2 / 2;
	    advance(second_cut, len22);
	    first_cut = upper_bound(first, middle, *second_cut, comp);
	    distance(first, first_cut, len11);
	}
	BidirectionalIterator new_middle =
	    __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
			      len22, buffer, buffer_size);
	__merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
			 buffer_size, (T*)0, comp);
	__merge_adaptive(new_middle, second_cut, last, len1 - len11,
			 len2 - len22, buffer, buffer_size, (T*)0, comp);
    }
}

template <class BidirectionalIterator, class Distance, class Pointer, class T>
void __inplace_merge(BidirectionalIterator first,
		     BidirectionalIterator middle, 
		     BidirectionalIterator last, Distance len1, Distance len2,
		     pair<Pointer, Distance> p, T*) {
    if (p.first == 0) {
	__merge_without_buffer(first, middle, last, len1, len2);
	return;
    }
    Distance len = min(p.second, len1 + len2);
    fill_n(raw_storage_iterator<Pointer, T>(p.first), len, *first);
    __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0);
    destroy(p.first, p.first + len);
    return_temporary_buffer(p.first);
}

template <class BidirectionalIterator, class Distance, class Pointer, class T,
	  class Compare>
void __inplace_merge(BidirectionalIterator first,
		     BidirectionalIterator middle, 
		     BidirectionalIterator last, Distance len1, Distance len2,
		     pair<Pointer, Distance> p, T*, Compare comp) {
    if (p.first == 0) {
	__merge_without_buffer(first, middle, last, len1, len2, comp);
	return;
    }
    Distance len = min(p.second, len1 + len2);
    fill_n(raw_storage_iterator<Pointer, T>(p.first), len, *first);
    __merge_adaptive(first, middle, last, len1, len2, p.first, p.second, (T*)0,
		     comp); 
    destroy(p.first, p.first + len);
    return_temporary_buffer(p.first);
}

template <class BidirectionalIterator, class T, class Distance>
inline void __inplace_merge_aux(BidirectionalIterator first,
				BidirectionalIterator middle,
				BidirectionalIterator last, T*, Distance*) {
    Distance len1 = 0;
    distance(first, middle, len1);
    Distance len2 = 0;
    distance(middle, last, len2);
    __inplace_merge(first, middle, last, len1, len2,
		    get_temporary_buffer(len1 + len2, (T*)0), (T*)0);
}

template <class BidirectionalIterator, class T, class Distance, class Compare>
inline void __inplace_merge_aux(BidirectionalIterator first,
				BidirectionalIterator middle,
				BidirectionalIterator last, T*, Distance*,
				Compare comp) {
    Distance len1 = 0;
    distance(first, middle, len1);
    Distance len2 = 0;
    distance(middle, last, len2);
    __inplace_merge(first, middle, last, len1, len2,
		    get_temporary_buffer(len1 + len2, (T*)0), (T*)0,
		    comp);
}

template <class BidirectionalIterator>
inline void inplace_merge(BidirectionalIterator first,
			  BidirectionalIterator middle,
			  BidirectionalIterator last) {
    if (first == middle || middle == last) return;
    __inplace_merge_aux(first, middle, last, value_type(first),
			distance_type(first));
}

template <class BidirectionalIterator, class Compare>
inline void inplace_merge(BidirectionalIterator first,
			  BidirectionalIterator middle,
			  BidirectionalIterator last, Compare comp) {
    if (first == middle || middle == last) return;
    __inplace_merge_aux(first, middle, last, value_type(first),
			distance_type(first), comp);
}

template <class InputIterator1, class 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 <class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
	      InputIterator2 first2, InputIterator2 last2, Compare comp) {
    while (first1 != last1 && first2 != last2)
	if (comp(*first2, *first1))
	    return false;
	else if(comp(*first1, *first2)) 
	    ++first1;
	else
	    ++first1, ++first2;

    return first2 == last2;
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result) {
    while (first1 != last1 && first2 != last2)
	if (*first1 < *first2)
	    *result++ = *first1++;
	else if (*first2 < *first1)
	    *result++ = *first2++;
	else {
	    *result++ = *first1++;
	    first2++;
	}
    return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator,
	  class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
			 InputIterator2 first2, InputIterator2 last2,
			 OutputIterator result, Compare comp) {
    while (first1 != last1 && first2 != last2)
	if (comp(*first1, *first2))
	    *result++ = *first1++;
	else if (comp(*first2, *first1))
	    *result++ = *first2++;
	else {
	    *result++ = *first1++;
	    ++first2;
	}
    return copy(first2, last2, copy(first1, last1, result));
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
				InputIterator2 first2, InputIterator2 last2,
				OutputIterator result) {
    while (fi