（十三）STL部分算法简介

• qsort不是c++标准库的算法，它们是c的函数

qsort(c.data(), ASIZE, sizeof(long), compareLongs);

long *pItem = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);

• c++标准库算法一定是在std中，且前几个参数一定都是迭代器，要使用这种方式访问容器数据

• accumulate是累计，也可以是传进去一个运算
• 有两种形式，第一个版本是累加，第二个版本是累计

template
T accumulate(InputIterator first, InputIterator last, T init)
{//传入三个参数，前两个表示容器中元素的范围，第三个参数是结果的初始值
	for(; first != last; ++first)
		init = init + *first;
	return init;
}

template
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
{//传入四个参数，前两个表示容器中元素的范围，第三个参数是结果的初始值
//第四个参数是运算方式
	for(; first != last; ++first)
		init = binary_op(init, *first);
	return init;

//示例
namespace test
{

int myfunc(int x, int y){ return x+2*y;}

struct myclass{
	int operator()(int x, int y){ return x+3*y;]
}myobj;

void test_accumulate()
{
	int init = 100;
	int nums[] = {10, 20, 30};

	cout << accumulate(nums, nums+3, init) << endl;//160
	cout<< accumulate(nums, nums+3, init, minus())< 
算法for_each 
template
Function for_each(InputIterator first, InputIterator last, Function f)
{
	for(; first != last; ++first)
		f(*first);
	return f;
}

//示例
for_each(myvec.begin(), myvec.end(), myfunc);
 
算法replace、replace_if、replace_copy 
replace
 
//replace将范围内的old_value用new_value替换
template
void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value){
	for(; first != last; ++first)
		if(*first == old_value)
			*first = new_value;
}
 
replace_if
Predicate表示判断式，返回一个bool值
 
//将满足判断式的元素用性值替换
template
void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value)
	for(; first!=last; ++first)
		if(pred(*first))
			*first = new_value;
}
 
replace_copy
 
//将范围内等于旧值的元素都以新值的形式放到新的区间中，不等于就放入原值
template
OutputIterator replace_copy(InputIterator first, OutputIterator result, const T& old_value, const T& new_value){
	for(; first!=last; ++first)
		*result = *first == old_val ? new_val : *first;
	return result;
}
 
算法count、count_if 
count
容器不带count()成员函数 
  
array、vector、list、forward_list、deque
 
容器带有成员函数count() 
  
set / multiset
map / multimap
unordered_set / unordered_multiset
unordered_map / unordered_multimap
 
关联型容器相当于一个小型数据库，它有自己较为快速的查找方法
 
//统计容器中给定范围内给定值的数量
template
typename iterator_traits::difference_type
count(InputIterator first, InputIterator last, const T& value){
//n是一个初值为0的计算机
	typename iterator_traits::difference_type n = 0;
	for(; first!=last; ++first)
		if(*first == value)
			++n;
	return n;
}
 
count_if
 
template
typename iterator_traits::differencce_type
count_if(InputIterator first, InputIterator last, Predicate pred){
//n是一个初值为0的计数器
	typename iterator_traits::difference_type n = 0;
	for(; first != last; ++first)
		if(pred(*first))
			++n;
	return n;
}
 
算法find、find_if 
find是一种循序查找，效率较低
容器不带find()成员函数 
  
array、vector、list、forward_list、deque
 
容器带有成员函数find() 
  
set / multiset
map / multimap
unordered_set / unordered_multiset
unordered_map / unordered_multimap
 
find()
 
template
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
	while(first != last && first != value)
		++first;
	return first;
}
 
find_if()
 
template
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
{
	while(first != last && !pred(*first))
		++first;
	return first;
}
 
算法sort 
容器不带有成员函数sort() 
  
array、vector、deque
set / multiset
map / multimap
unordered_set / unordered_multiset
unordered_map / unordered_multimap
 
容器带有成员函数sort() 
  
list
forward_list
 
sort要求迭代器是随机访问迭代器
 
算法binary_search 
二分查找必需是在有序序列上
 
template
bool binary_search(ForwardIterator first, ForwardIterator last, const T& val)
{
	first = std::lower_bound(first, last, val);
	return (first!=last && !(val <*first));
 
template
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const T& val)
{
	ForwardIterator it;
	iterator_traits::difference_type count, step;
	count = distance(first, last);
	while(count>0)
	{
		it = first; step = count / 2;
		advance(it, step);
		if(*it < val){
			dirst = ++it;
			count -= step + 1;
		}
		else count = step;
	}
	return first;
}