【极客班】《 STL与泛型编程第二周》学习笔记

1. mem_fun 以及mem_func_ref

http://www.cplusplus.com/reference/functional/mem_fun/
http://www.cplusplus.com/reference/functional/mem_fun_ref/

看一小段代码（使用c++11语法，用clang++编译需要添加-std=c++11选项）：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

struct Test{
  Test(int value)
    : x(value)
  {}

  void Print()
  {
    cout << x << endl;
  }
  int x;
};

int main(void)
{
  vector<Test> v = {Test(1), Test(2), Test(3)};
  for_each(v.begin(), v.end(), mem_fun_ref(&Test::Print));

  return 0;
}

使用容器时，如果需要对容器对象的每个成员遍历调用其成员函数，通常需要用到mem_fun或者mem_fun_ref。
像上面的例子通常我们能想到的就是下面的用法：

for_each(v.begin(), v.end(), (&Test::Print));

但是编译时会产生下面的编译错误：

/usr/include//c++/4.6/bits/stl_algo.h:4379:2: error: called object type 'void (Test::*)()' is not a function or function pointer

这时候，我们可以使用mem_func或者mem_func_ref将函数转换成仿函数(functor)以便于调用。
mem_fun函数的声明如下：

template <class S, class T> mem_fun_t<S,T> mem_fun (S (T::*f)());
template <class S, class T, class A> mem_fun1_t<S,T,A> mem_fun (S (T::*f)(A));
template <class S, class T> const_mem_fun_t<S,T> mem_fun (S (T::*f)() const);
template <class S, class T, class A> const_mem_fun1_t<S,T,A> mem_fun (S (T::*f)(A) const);

需要注意的是mem_fun有4个版本的声明，分别用于无参数、单参数、const无参数、const单参数的情况。
mem_fun和mem_fun_ref的区别在于mem_fun用于指针（如果本例中使用Vector<int*>类型可以使用mem_fun），而mem_fun_ref用于对象的引用。
另外，在c++17中mem_fun和mem_fun_ref已经被废弃了，c++17中推荐使用mem_fn和bind来替代它们，这时候我们代码修改如下(编译时使用-std=c++1y选项)：

for_each(v.begin(), v.end(), mem_fn(&Test::Print)

2. 泛型算法--非变易算法

非变易算法是一系列模板函数，这类算法不会修改操作对象

下面依次说明。

1) for_each

http://en.cppreference.com/w/cpp/algorithm/for_each
for_each声明如下：

template< class InputIt, class UnaryFunction >UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );

for_each用于从first到last中每个元素，并调用给定函数

2)find

http://www.cplusplus.com/reference/algorithm/find/?kw=find
声明如下：

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);

find用于从first到last查找给定元素，返回相应迭代器，若不存在，返回last。
小例子：


#include <algorithm>
#include <iostream>

using namespace std;

int main(void)
{
  vector<int> v = {1,2,3,4,5};
  vector<int>::iterator it = find(v.begin(), v.end(), 3);
  cout << *it << endl;

  return 0;
}

3)find_if

http://www.cplusplus.com/reference/algorithm/find_if/

template <class InputIterator, class UnaryPredicate>
   InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);

find_if用于从first到last中满足条件的元素，若存在就返回给定迭代器。若不存在，返回last
小例子：

#include <algorithm>
#include <iostream>
using namespace std;

bool IsEven(int i)
{
  return (i % 2 == 0);
}
int main()
{
  vector<int> v = {1,2,3,4,5};
  vector<int>::iterator it = find_if(v.begin(), v.end(), IsEven);
  cout << *it << endl;

  return 0;
}

4)adjacent_find

http://www.cplusplus.com/reference/algorithm/adjacent_find/

template <class ForwardIterator>
   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class BinaryPredicate>
   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,
                                  BinaryPredicate pred);

adjacent_find有两个版本，分别表示判断从first到last之间是否有两个连续相等元素以及判断是否有两个连续元素满足pred。
小例子：

#include <algorithm>
#include <iostream>

using namespace std;
bool isSumEqualToTen(int i, int j)
{
  return i + j == 10;
}
int main(void)
{
  vector<int> v1 = {1,2,2,3,5};
  vector<int>::iterator it = adjacent_find(v1.begin(), v1.end());
  if(it != v1.end())
  {
    cout << *it << endl;
  }

  vector<int> v2 = {1,2,7,3,5};
  it = adjacent_find(v2.begin(), v2.end(),  isSumEqualToTen);
  if(it != v2.end())
  {
    cout << *it << endl;
  }
  return 0;
}

输出结果如下：

2
7

5)find_first_of

http://www.cplusplus.com/reference/algorithm/find_first_of/

template <class ForwardIterator1, class ForwardIterator2>
   ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1,
                                   ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
   ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1,
                                   ForwardIterator2 first2, ForwardIterator2 last2,
                                   BinaryPredicate pred);

find_first_of用于查找从[first1,last1)中与[first2,last2)中相等的元素或者满足条件pred的元素,若未找到，则返回last1.

6) count

http://www.cplusplus.com/reference/algorithm/count/

template <class InputIterator, class T>
  typename iterator_traits<InputIterator>::difference_type
    count (InputIterator first, InputIterator last, const T& val);

小例子(结果为3)：

#include <algorithm>
#include <iostream>

using namespace std;

int main(void)
{
    vector<int> v = {1,2,2,3,2};
    cout << count(v.begin(), v.end(), 2) << endl;
    return 0;
}

count用于查找[first, last)上与val相等的元素总数。

7) count_if

http://www.cplusplus.com/reference/algorithm/count_if/

template <class InputIterator, class UnaryPredicate>
  typename iterator_traits<InputIterator>::difference_type
    count_if (InputIterator first, InputIterator last, UnaryPredicate pred);

count_if用于查找[first,last)上满足pred函数的所有元素总数

8) mismatch

http://www.cplusplus.com/reference/algorithm/mismatch/?kw=mismatch

template <class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, BinaryPredicate pred);

第一个mismatch函数用于判断[first1,last1)上与从first2开始的序列中第一个不匹配的迭代器。
第二个mismatch函数用于判断[first1,last1)上与从first2开始序列中第一个不满足pred的迭代器。

9)equal

http://www.cplusplus.com/reference/algorithm/equal/?kw=equal

template <class InputIterator1, class InputIterator2>
  bool equal (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2);
template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  bool equal (InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, BinaryPredicate pred)

equal与mismatch相反，用于查找第一个相等或者满足pred的迭代器

10)search