6 算法

算法的标准样式：需要传进去两个指针

6.1 算法源码

6.1.1 accumulate

两个版本：

1. 元素累加到 init 上

   template <class InputIterator, class T>
   T accumulate(InputIterator first, InputIterator last, T init)
   {
   	for (; first != last; ++first)
   		init = init + *first; // 累加到init
   	return init;
   }

2. 元素累运算到 init 上

   template <class InputIterator, class T, class BinaryOperation>
   T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op)
   {
   	for (; first != last; ++first)
   		init = binary_op(init, *first); // 累运算到init上
   	return init;
   }

   这里可以用任意的二元操作（可以是函数，也可以是仿函数）

测试：

#include <iostream>     // std::cout
#include <functional>   // std::minus
#include <numeric>      // std::accumulate

// 函数
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()
{
  cout << "\ntest_accumulate().......... \n";	
  int init = 100;
  int nums[] = {10,20,30};

  cout << "using default accumulate: ";
  cout << accumulate(nums,nums+3,init);  //160
  cout << '\n';

  cout << "using functional's minus: ";
  cout << accumulate(nums, nums+3, init, minus<int>()); //40
  cout << '\n';

  cout << "using custom function: ";
  cout << accumulate(nums, nums+3, init, myfunc);	//220
  cout << '\n';

  cout << "using custom object: ";
  cout << accumulate(nums, nums+3, init, myobj);	//280
  cout << '\n';
}

6.1.2 for_each

让范围里的所有元素都依次做同一件事情

Function 可以是函数也可以是仿函数

template <class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f)
{
	for (; first != last; ++first) {
		f(*first);
	}
	return f;
}

与C++11中的 range-based for statement 差不多

6.1.3 replace...

• replace：范围内的所有等于 old_value 的，都被 new_value 取代

  template <class ForwardIterator, class T>
  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：范围内所有满足 pred() 为 true 的元素都被 new_value 取代

  template <class ForwardIterator,class Predicate, class T>
  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：范围内的元素全部 copy 到新地方，其中所有等于 old_value 的，都被替代为 new_value

  template <class InputIterator, class OutputIterator, class T>
  OutputIterator replace_copy(InputIterator first, InputIterator last,
  	OutputIterator result, const T& old_value, const T& new_value)
  {
  	for (; first != last; ++first, ++result)
  	{
  		*result = (*first == old_value) ? new_value : *first;
  	}
  	return result;
  }

6.1.4 count...

• count：在范围中计数值等于 value 的个数

  template <class InputIterator, class T>
  typename iterator_traits<InputIterator>::difference_type // 返回类型
  count (InputIterator first, InputIterator last, const T& value)
  {
  	typename iterator_traits<InputIterator>::difference_type n = 0;
  	for (; first != last; ++first)
  	{
  		if (*first == value) ++n;
  	}
  	return n;
  }

• count_if：在范围中计数满足条件 pred() 的个数

  template <class InputIterator, class Predicate>
  typename iterator_traits<InputIterator>::difference_type // 返回类型
  count_if (InputIterator first, InputIterator last, Predicate pred)
  {
  	typename iterator_traits<InputIterator>::difference_type n = 0;
  	for (; first != last; ++first)
  	{
  		if (pred(*first)) ++n;
  	}
  	return n;
  }

• 容器不带成员函数 count()：array，vector，forward_list，deque
• 容器自带成员函数 count()：set / multiset，map / multimap，unordered_set / unordered_multiset，unordered_map / unorderd_multimap —— 所有关联式容器

6.1 5 find...

• find：在范围内找到值等于 value 的元素

  template <class InputIterator, class T>
  InputIterator find(InputIterator first, InputIterator last, const T& value)
  {
  	while (first != last && *first != value) ++first;
  	return first;
  }

• find_if：在范围内找到满足 pred() 的元素

  template <class InputIterator, class Predicate>
  InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
  {
  	while (first != last && !pred(*first)) ++first;
  	return first;
  }

都是循序查找，效率低

• 容器不带成员函数 find()：array，vector，forward_list，deque
• 容器自带成员函数 find()：set / multiset，map / multimap，unordered_set / unordered_multiset，unordered_map / unorderd_multimap —— 所有关联式容器

6.1.6 sort

源码复杂

测试：

// 函数
bool myfunc (int i,int j) { return (i<j); }

//仿函数
struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobj;

// 定义向量
int myints[] = {32,71,12,45,26,80,53,33};
vector<int> myvec(myints, myints+8);          // 32 71 12 45 26 80 53 33

// 用默认的比较(operator <)
sort(myvec.begin(), myvec.begin()+4);         //(12 32 45 71)26 80 53 33

// 用自己的函数作比较
sort(myvec.begin()+4, myvec.end(), myfunc); 	// 12 32 45 71(26 33 53 80)

// 用自己的仿函数作比较
sort(myvec.begin(), myvec.end(), myobj);      //(12 26 32 33 45 53 71 80)


// 用反向迭代器 reverse iterator 和默认的比较(operator <)
sort(myvec.rbegin(), myvec.rend());           // 80 71 53 45 33 32 26 12

// 用显式默认比较(operator <)
sort(myvec.begin(), myvec.end(), less<int>()); // 12 26 32 33 45 53 71 80   

// 使用另一个比较标准(operator >)
sort(myvec.begin(), myvec.end(), greater<int>()); // 80 71 53 45 33 32 26 12

• 容器不带成员函数 sort()：array，vector，deque，所有关联式容器（本身就排好序了）
• 容器自带成员函数 sort()：list，forward_list（只能用自带）

reverse iterator：

其中用的是 reverse_iterator —— iterator adapter

6.1.7 binary_search

二分查找是否存在目标元素（并不给予位置），使用前必须先排序；其主要使用 lower_bound() 来找到能放入 val 的最低位置，再判断该元素是否存在

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value)
{
	first = lower_bound(first, last, value);
	return (first != last && !(value < *first));
    // first == last 就是序列中所有元素都小于value
    // first == last 时，*first是没有值的，所以需要先检查
    // value < *first 就是序列中没有等于value的
    
}

lower_bound()：用于在有序序列中查找==第一个大于等于==该值的元素（包括目标值本身），并返回一个指向该位置的迭代器

• 如果目标值在序列中多次出现，返回第一个出现的位置
• 如果目标值在序列中不存在，它将返回指向比目标值大的第一个元素位置，或者返回 last

upper_bound()：用于在有序序列中查找==第一个大于==该值的元素（不包括目标值本身），并返回一个指向该位置的迭代器

• 如果目标值在序列中多次出现，返回第一个大于目标值的位置
• 如果目标值在序列中不存在，它将返回与 lower_bound() 一样的位置

一样是前闭后开的原则，且他们都用的是二分查找的方法

7 仿函数

仿函数专门为算法服务，设计成一个函数/仿函数是为了能传入算法

STL中的每个仿函数都继承了 binary_function / unary_function—— 融入到STL中

STL规定每个 Adaptable Function（之后可以改造的函数）都应该继承其中一个（因为之后 Function Adapter 将会提问）

 // 一个操作数的操作，例如“!”
 template <class Arg, class Result>
 struct unary_function
 {
     typedef Arg argument_type;
     typedef Result result_type;
 };
 
 // 两个操作数的操作，例如“+”
 template <class Arg1, class Arg2, class Result>
 struct binary_function
 {
     typedef Arg1 first_argument_type;
     typedef Arg2 second_argument_type;
     typedef Result result_type;
 };
 
 // 理论大小都是0，实际上可能是1（如果有人继承，那就一定是0）

防函数是我们自己可能会写的，所以自己写的时候，如果想要融入STL，就要继承上面的两个之一