stl算法实现（lower_bound,upper_bound,binary_search，find，find_if,next_premutation,prev

[TOC]
# 解释
- lower_bound
可插入value的第一个位置
- upper_bound
可插入value的最后一个合适的位置

# lower_bound
```
template<typename ForwardIterator,typename T,typename Distance>
inline ForwardIterator __mylower_bound(ForwardIterator first, ForwardIterator second, const T &value, Distance *, forward_iterator_tag);
{
	Distance len = 0;
	distance(first, second, len);
	Distance half;
	ForwardIterator middle;

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

template<typename ForwardIterator,typename T>
inline ForwardIterator mylower_bound(ForwardIterator first, ForwardIterator second, const T &value)
{
	return __mylower_bound(first, second, value, distance_type(first), iterator_category(first));
}
```

# upper_bound
```
template<typename ForwardIterator, typename T, typename Distance>
inline ForwardIterator __myupper_bound(ForwardIterator first, ForwardIterator second, const T &value, Distance *, forward_iterator_tag);
{
	Distance len = 0;
	distance(first, second, len);
	Distance half;
	ForwardIterator middle;

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

template<typename ForwardIterator, typename T>
inline ForwardIterator myupper_bound(ForwardIterator first, ForwardIterator second, const T &value)
{
	return __myupper_bound(first, second, value, distance_type(first), iterator_category(first));
}
```

# binary_search

```
template<typename ForwardIterator, typename T>
inline ForwardIterator mybinary_search(ForwardIterator first, ForwardIterator second, const T &value)
{
	ForwardIterator i = mylower_bound(first, second, value);
	return i != last && !(value < *i);
}
```

# find
```
template<typename InputIterator,typename T>
InputIterator find(InputIterator first, InputIterator last, const T &value)
{
	while (first != last&&*first != value) ++first;
	return first;
}
```
# find_if
```
template<typename InputIterator,typename Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
{
	while (first != last && !pred(*first)) ++first;
	return first;
}
```

# next_premutation
```
template<typename BidirectionalIterator>
bool mynext_premutation(BidirectionalIterator first, BidirectionalIterator last)
{
	if (first == last) return false;
	BidirectionalIterator i = first;
	++i;
	if (i == last) return false;
	i = last;
	--i;
	for (;;)
	{
		BidirectionalIterator ii = i;
		--i;
		if (*i < *ii)
		{
			BidirectionalIterator j = last;
			while (!(*i < *--j));
			std::iter_swap(i, j);
			std::reverse(ii, last);
			return true;
		}
		if (i == first)
		{
			std::reverse(first, last);
			return false;
		}
	}
}
```

# prev_premutation
```
template<typename BidirectionalIterator>
bool myprev_premutation(BidirectionalIterator first, BidirectionalIterator last)
{
	if (first == last) return false;
	BidirectionalIterator i = first;
	++i;
	if (i == last) return false;
	i = last;
	--i;
	for (;;)
	{
		BidirectionalIterator ii = i;
		--i;
		if (*ii < *i)
		{
			BidirectionalIterator j = last;
			while (!(*--j < *i));
			std::iter_swap(i, j);
			std::reverse(ii, last);
			return true;
		}
		if (i == first)
		{
			std::reverse(first, last);
			return false;
		}
	}
}
```
## premutation测试
```
template<typename Arg,typename Result>
struct unary_function
{
	typedef Arg argument_type;
	typedef Result result_type;
};

template<typename T>
struct display:public unary_function<T,void>
{
	void operator()(T &x) const { std::cout << " " << x;};
};
void testPremutation()
{
	std::cout << "next:" << std::endl;
	int a[] = { 2,1,5,7 };
	std::vector<int> v(a, a + 4);
	std::sort(v.begin(), v.end());
	do {
		//std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
		std::for_each(v.begin(), v.end(), display<int>());
		std::cout << std::endl;
	} while (mynext_premutation(v.begin(), v.end()));

std::cout << "prev:" << std::endl;
	int a1[] = { 2,1,5,7 };
	std::vector<int> v1(a1, a1 + 4);
	std::sort(v1.begin(), v1.end(),std::greater<int>());
	do {
		//std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
		std::for_each(v1.begin(), v1.end(), display<int>());
		std::cout << std::endl;
	} while (myprev_premutation(v1.begin(), v1.end()));
}

结果：
next:
1 2 5 7
1 2 7 5
1 5 2 7
1 5 7 2
1 7 2 5
1 7 5 2
2 1 5 7
2 1 7 5
2 5 1 7
2 5 7 1
2 7 1 5
2 7 5 1
5 1 2 7
5 1 7 2
5 2 1 7
5 2 7 1
5 7 1 2
5 7 2 1
7 1 2 5
7 1 5 2
7 2 1 5
7 2 5 1
7 5 1 2
7 5 2 1
prev:
7 5 2 1
7 5 1 2
7 2 5 1
7 2 1 5
7 1 5 2
7 1 2 5
5 7 2 1
5 7 1 2
5 2 7 1
5 2 1 7
5 1 7 2
5 1 2 7
2 7 5 1
2 7 1 5
2 5 7 1
2 5 1 7
2 1 7 5
2 1 5 7
1 7 5 2
1 7 2 5
1 5 7 2
1 5 2 7
1 2 7 5
1 2 5 7
```

Simon 's Blog

导航

OHH,最近发表

这里随便填填,没事