algo.h

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

	RandomAccessIterator cut = __unguarded_partition
	    (first, last, T(__median(*first, *(first + (last - first)/2), 
				     *(last - 1), comp)), comp);
	if (cut <= nth)
	    first = cut;
	else 
	    last = cut;
    }
    __insertion_sort(first, last, comp);
}

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

template <class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
			      const T& value, Distance*,
			      forward_iterator_tag) {
    Distance len = 0;
    distance(first, last, len);
    Distance half;
    ForwardIterator middle;

    while (len > 0) {
	half = len / 2;
	middle = first;
	advance(middle, half);
	if (*middle < value) {
	    first = middle;
	    ++first;
	    len = len - half - 1;
	} else
	    len = half;
    }
    return first;
}

template <class ForwardIterator, class T, class Distance>
inline ForwardIterator __lower_bound(ForwardIterator first,
				     ForwardIterator last,
				     const T& value, Distance*,
				     bidirectional_iterator_tag) {
    return __lower_bound(first, last, value, (Distance*)0,
			 forward_iterator_tag());
}

template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
				   RandomAccessIterator last, const T& value,
				   Distance*, random_access_iterator_tag) {
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle;

    while (len > 0) {
	half = len / 2;
	middle = first + half;
	if (*middle < value) {
	    first = middle + 1;
	    len = len - half - 1;
	} else
	    len = half;
    }
    return first;
}

template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
				   const T& value) {
    return __lower_bound(first, last, value, distance_type(first),
			 iterator_category(first));
}

template <class ForwardIterator, class T, class Compare, class Distance>
ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
			      const T& value, Compare comp, Distance*,
			      forward_iterator_tag) {
    Distance len = 0;
    distance(first, last, len);
    Distance half;
    ForwardIterator middle;

    while (len > 0) {
	half = len / 2;
	middle = first;
	advance(middle, half);
	if (comp(*middle, value)) {
	    first = middle;
	    ++first;
	    len = len - half - 1;
	} else
	    len = half;
    }
    return first;
}

template <class ForwardIterator, class T, class Compare, class Distance>
inline ForwardIterator __lower_bound(ForwardIterator first,
				     ForwardIterator last,
				     const T& value, Compare comp, Distance*,
				     bidirectional_iterator_tag) {
    return __lower_bound(first, last, value, comp, (Distance*)0,
			 forward_iterator_tag());
}

template <class RandomAccessIterator, class T, class Compare, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
				   RandomAccessIterator last,
				   const T& value, Compare comp, Distance*,
				   random_access_iterator_tag) {
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle;

    while (len > 0) {
	half = len / 2;
	middle = first + half;
	if (comp(*middle, value)) {
	    first = middle + 1;
	    len = len - half - 1;
	} else
	    len = half;
    }
    return first;
}

template <class ForwardIterator, class T, class Compare>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
				   const T& value, Compare comp) {
    return __lower_bound(first, last, value, comp, distance_type(first),
			 iterator_category(first));
}

template <class ForwardIterator, class T, class Distance>
ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
			      const T& value, Distance*,
			      forward_iterator_tag) {
    Distance len = 0;
    distance(first, last, len);
    Distance 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 <class ForwardIterator, class T, class Distance>
inline ForwardIterator __upper_bound(ForwardIterator first,
				     ForwardIterator last,
				     const T& value, Distance*,
				     bidirectional_iterator_tag) {
    return __upper_bound(first, last, value, (Distance*)0,
			 forward_iterator_tag());
}

template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __upper_bound(RandomAccessIterator first,
				   RandomAccessIterator last, const T& value,
				   Distance*, random_access_iterator_tag) {
    Distance len = last - first;
    Distance half;
    RandomAccessIterator 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 <class ForwardIterator, class T>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
				   const T& value) {
    return __upper_bound(first, last, value, distance_type(first),
			 iterator_category(first));
}

template <class ForwardIterator, class T, class Compare, class Distance>
ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
			      const T& value, Compare comp, Distance*,
			      forward_iterator_tag) {
    Distance len = 0;
    distance(first, last, len);
    Distance half;
    ForwardIterator middle;

    while (len > 0) {
	half = len / 2;
	middle = first;
	advance(middle, half);
	if (comp(value, *middle))
	    len = half;
	else {
	    first = middle;
	    ++first;
	    len = len - half - 1;
	}
    }
    return first;
}

template <class ForwardIterator, class T, class Compare, class Distance>
inline ForwardIterator __upper_bound(ForwardIterator first,
				     ForwardIterator last,
				     const T& value, Compare comp, Distance*,
				     bidirectional_iterator_tag) {
    return __upper_bound(first, last, value, comp, (Distance*)0,
			 forward_iterator_tag());
}

template <class RandomAccessIterator, class T, class Compare, class Distance>
RandomAccessIterator __upper_bound(RandomAccessIterator first,
				   RandomAccessIterator last,
				   const T& value, Compare comp, Distance*,
				   random_access_iterator_tag) {
    Distance len = last - first;
    Distance half;
    RandomAccessIterator 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 <class ForwardIterator, class T, class Compare>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
				   const T& value, Compare comp) {
    return __upper_bound(first, last, value, comp, distance_type(first),
			 iterator_category(first));
}

template <class ForwardIterator, class T, class Distance>
pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
	      Distance*, forward_iterator_tag) {
    Distance len = 0;
    distance(first, last, len);
    Distance half;
    ForwardIterator middle, left, right;

    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 <class ForwardIterator, class T, class Distance>
inline pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
	      Distance*, bidirectional_iterator_tag) {
    return __equal_range(first, last, value, (Distance*)0, 
			 forward_iterator_tag());
}

template <class RandomAccessIterator, class T, class Distance>
pair<RandomAccessIterator, RandomAccessIterator>
__equal_range(RandomAccessIterator first, RandomAccessIterator last,
	      const T& value, Distance*, random_access_iterator_tag) {
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle, left, right;

    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<RandomAccessIterator, RandomAccessIterator>(left,
								    right);
	}
    }
    return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}

template <class ForwardIterator, class T>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
    return __equal_range(first, last, value, distance_type(first),
			 iterator_category(first));
}

template <class ForwardIterator, class T, class Compare, class Distance>
pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
	      Compare comp, Distance*, forward_iterator_tag) {
    Distance len = 0;
    distance(first, last, len);
    Distance half;
    ForwardIterator middle, left, right;

    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 <class ForwardIterator, class T, class Compare, class Distance>
inline pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
	      Compare comp, Distance*, bidirectional_iterator_tag) {
    return __equal_range(first, last, value, comp, (Distance*)0, 
			 forward_iterator_tag());
}

template <class RandomAccessIterator, class T, class Compare, class Distance>
pair<RandomAccessIterator, RandomAccessIterator>
__equal_range(RandomAccessIterator first, RandomAccessIterator last,
	      const T& value, Compare comp, Distance*,
	      random_access_iterator_tag) {
    Distance len = last - first;
    Distance half;
    RandomAccessIterator middle, left, right;

    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<RandomAccessIterator, RandomAccessIterator>(left,
								    right);
	}
    }
    return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}           

template <class ForwardIterator, class T, class Compare>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value,
	    Compare comp) {
    return __equal_range(first, last, value, comp, distance_type(first),
			 iterator_category(first));
}    

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
		   const T& value) {