第21章 非变易算法

   第21章 非变易算法
     Non-modifying sequence operations
   21.0 advance, distance
     为了了解模板，先了解一下这两个迭代器操作函数
   21.1 逐个容器元素for_each
     for_each  Apply function to range (template function)
   21.2 查找容器元素find
     find  Find value in range (function template)
   21.3 条件查找容器元素find_if
     find_if Find  element in range (function template)
   21.4 邻近查找容器元素adjacent_find
     adjacent_find  Find equal adjacent elements in range (function template)
   21.5 范围查找容器元素find_first_of
     find_first_of  Find element from set in range (function template)
   21.6 统计等于某值的容器元素个数count
     count  Count appearances of value in range (function template)
   21.7 条件统计容器元素个数count_if
     count_if  Return number of elements in range satisfying condition (function template)
   21.8 元素不匹配查找mismatch
     mismatch  Return first position where two ranges differ (function template)
   21.9 元素相等判断equal
     equal  Test whether the elements in two ranges are equal (function template)
   21.10 子序列搜索search
     search  Find subsequence in range (function template)
   21.11 重复元素子序列搜索search_n
     search_n  Find succession of equal values in range (function template)
   21.12 最后一个子序列搜索find_end
     find_end  Find last subsequence in range (function template)

   21.13 本章小结：

---

  

   第21章 非变易算法
     Non-modifying sequence operations

   21.0 advance, distance
     为了了解模板，先了解一下这两个迭代器操作函数

//  21.0 advance, distance ---------------------------------------------------------



/*

advance

http://www.cplusplus.com/reference/iterator/
http://www.cplusplus.com/reference/iterator/advance/

template <class InputIterator, class Distance>
  void advance (InputIterator& it, Distance n);

Advance iterator
Advances the iterator it by n element positions.

*/


// advance example
#include <iostream>     // std::cout
#include <iterator>     // std::advance
#include <list>         // std::list
using namespace std;

int main () {
  list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);
  list<int>::iterator it = mylist.begin();
  advance (it,5);
  cout << "The sixth element in mylist is: " << *it << '
';

  return 0;
}



// advance example, my test：测试参数负值、越界
#include <iostream> 
#include <iterator>
#include <vector>
using namespace std;

int main () {
  vector<int> v;
  for (int i=0; i<10; i++) v.push_back(i);
  vector<int>::iterator it = v.begin();
  advance (it,5);
  cout << "The sixth element in mylist is: " << *it << '
';

  advance(it,-2); // 第二个参数，可以接受负值
  cout << *it << endl;

  advance(it,-5); // 当越界时，如同数组下标越界，编译器不管嘀
  cout << *it << endl;

  return 0;
}



/*

distance

http://www.cplusplus.com/reference/iterator/distance/

template<class InputIterator>
  typename iterator_traits<InputIterator>::difference_type
    distance (InputIterator first, InputIterator last);

Return distance between iterators
Calculates the number of elements between first and last.


*/



// advance example
#include <iostream>     // std::cout
#include <iterator>     // std::distance
#include <list>         // std::list

int main () {
  std::list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);

  std::list<int>::iterator first = mylist.begin();
  std::list<int>::iterator last = mylist.end();

  std::cout << "The distance is: " << std::distance(first,last) << '
';

  return 0;
}



// distance, my test
#include <iostream> 
#include <iterator>
#include <vector>
using namespace std;

int main () {
  vector<int> v;
  for (int i=0; i<10; i++) v.push_back(i);
  vector<int>::iterator it = v.begin();
  
  cout << distance(it,v.end()) << endl; // 正常输出
  advance (it,3);
  cout << distance(v.end(),it) << endl; // 可以输出负值：-7

  return 0;
}

   21.1 逐个容器元素for_each 
     for_each  Apply function to range (template function)

//   21.1 逐个容器元素for_each -------------------------------------------------------


/*
Apply function to range
Applies function f to each of the elements in the range [first,last).
The behavior of this template function is equivalent to:
*/
template<class InputIterator, class Function>
  Function for_each(InputIterator first, InputIterator last, Function f)
  {
    while ( first!=last ) f(*first++);
    return f;
  }


// for_each example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void myfunction (int i) {
  cout << " " << i;
}

struct myclass {
  void operator() (int i) {cout << " " << i;}
} myobject;

int main () {
  vector<int> myvector;
  myvector.push_back(10);
  myvector.push_back(20);
  myvector.push_back(30);

  cout << "myvector contains:";
  for_each (myvector.begin(), myvector.end(), myfunction);

  // or:
  cout << "
myvector contains:";
  for_each (myvector.begin(), myvector.end(), myobject);

  cout << endl;

  return 0;
}


// for_each example ，稍改
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//容器中的元素，均转化为参数i。这个函数会被默认转化为函数对象
void myfunction (int i) //这仅是个函数。用这个函数，不断调用容器中的指定元素
{
  cout << " " << i+2;
}

struct myclass  //重载操作符：()，只能用函数对象方式
{
  void operator() (int i) {cout << " " << i+8;}
} myobject;

int main () 
{
  vector<int> myvector;
  myvector.push_back(10);
  myvector.push_back(20);
  myvector.push_back(30);
  cout << "myvector contains:
";
  for_each (myvector.begin(), myvector.end()-1, myfunction); //用函数调用
  // or: 注意：均可以取不同范围。范围大小还得程序员把握
  cout << "
myvector contains:";
  for_each (myvector.begin()+1, myvector.end(), myobject); //重载()，函数对象
  cout << endl;
}


//285
#include <algorithm>
#include <list>
#include <iostream>
using namespace std;
struct print
{
  int count; //打印的元素计数
  print(){ count = 0; }
  void operator()(int x)
  {
    cout << 3*x << endl;
    count++;
  }
};

int main(void)
{
  //双向链表初始化
  list < int > l;
  l.push_back(29);
  l.push_back(32);
  l.push_back(16);
  l.push_back(22);
  l.push_back(27);
  //打印链表的元素
  print p = for_each(l.begin(), l.end(), print());
  //打印的元素个数
  cout << p.count << endl;
  return 0;
}

   21.2 查找容器元素find 
     find  Find value in range (function template)

//   21.2 查找容器元素find ---------------

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


// find example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int myints[] = { 10, 20, 30 ,40 };
  int * p;

  // pointer to array element:
  p = find(myints,myints+4,30);
  ++p;
  cout << "The element following 30 is " << *p << endl;

  vector<int> myvector(myints,myints+4); //相当于：begin(),end()
  //vector<int myvector( myints ); //这样写就不行。这里演示了如何把数组放到容器中去。 
  cout << myvector.size() << endl;

  vector<int>::iterator it;

  // iterator to vector element:
  it = find (myvector.begin(), myvector.end(), 30);
  ++it;
  cout << "The element following 30 is " << *it << endl;

  it = find (myvector.begin(), myvector.end(), 35);
  if( it == myvector.end() )
    cout << "not found" << endl;
  else
    cout << "find element is " << *it << endl;
}


//286
#include <algorithm>
#include <list>
#include <iostream>
int main(void)
{
  using namespace std;
  //双向链表初始化
  list < int > l;
  l.push_back(10);
  l.push_back(18);
  l.push_back(26);
  l.push_back(26);
  l.push_back(30);
  //查找元素26
  list < int > ::iterator iLocation = find(l.begin(), l.end(), 26);
  if(iLocation != l.end())
    cout << "找到元素26" << endl;
  //打印元素18
  cout << "前一个元素为" << *(--iLocation) << endl;
  return 0;
}

   21.3 条件查找容器元素find_if
     find_if Find  element in range (function template)

//   21.3 条件查找容器元素find_if ---------------------------------

template<class InputIterator, class Predicate>
  InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred )
  {
    for ( ; first!=last ; first++ ) if ( pred(*first) ) break;
    return first;
  }
// predicate 谓词判断


// find_if example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool IsOdd (int i) {
  return ((i%2)==1);
}

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

  myvector.push_back(10);
  myvector.push_back(20);
  myvector.push_back(40);
  myvector.push_back(51); //50

  it = find_if (myvector.begin(), myvector.end(), IsOdd);
  if( it == myvector.end() )
    cout << "No found" << endl;
  else cout << "The first odd value is " << *it << endl;
}


//287，书中代码有错误，已经修正
#include <algorithm>
#include <vector>
#include <iostream>

bool divby5(int x)
{
  return 0==x % 5;
}

int main(void)
{
  using namespace std;
  //初始化vector
  vector < int > v(20);
  for(unsigned int i = 0; i < v.size(); i++)
    v[i] = (i + 1)*(i + 3); // 3 8 15 ..
  vector < int > ::iterator iLocation;
  iLocation = find_if(v.begin(), v.end(), divby5);
  if(iLocation != v.end())
  cout << "找到第一个能被5整除的元素" <<  *iLocation << endl  //打印15
     << "元素的索引位置为" << iLocation - v.begin() << endl;
  //打印2
  return 0;
}

   21.4 邻近查找容器元素adjacent_find
     adjacent_find  Find equal adjacent elements in range (function template)

//   21.4 邻近查找容器元素adjacent_find ----------------------------------------


template <class ForwardIterator>
   ForwardIterator adjacent_find ( ForwardIterator first, ForwardIterator last )
{
  ForwardIterator next=first; ++next;
  if (first != last)
    while (next != last)
      if (*first++ == *next++)  // or: if (pred(*first++,*next++)), for the pred version
        return first;
  return last;
}

// adjacent_百度词典  adj.邻近的，毗邻的；（时间上）紧接着的；相邻


// adjacent_find example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i, int j) {
  return (i*2==j); // i,first; j,next. first*2==next
}

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> myvector (myints,myints+8);
  vector<int>::iterator it;

  // using default comparison:
  it = adjacent_find (myvector.begin(), myvector.end());

  if (it!=myvector.end())
    cout << "the first...: " << *it << "  " << distance(myvector.begin(), it ) << endl;

  //using predicate comparison:
  it = adjacent_find (++it, myvector.end(), myfunction); //注意++it，从后一个30开始

  if (it!=myvector.end())
    cout << "the second...: " << *it << "  " << distance( myvector.begin(), it ) << endl;
}


//289
#include <algorithm>
#include <list>
#include <iostream>

bool parity_equal(int x, int y)
{
  return (x - y) % 2 == 0;
}

int main(void)
{
  using namespace std;
  //链表初始化
  list < int > l;
  l.push_back(3);
  l.push_back(6);
  l.push_back(9);
  l.push_back(11);
  l.push_back(11);
  l.push_back(18);
  l.push_back(20);
  l.push_back(20);
  //查找邻接相等的元素
  list < int > ::iterator iResult = adjacent_find(l.begin(), l.end());
  if(iResult != l.end())
  {
    cout << "发现链表有两个邻接的元素相等：" << endl;
    cout <<  *iResult << endl;
    iResult++;
    cout <<  *iResult << endl;
  }
  //查找奇偶性相同的邻接元素
  iResult = adjacent_find(l.begin(), l.end(), parity_equal);
  if(iResult != l.end())
  {
    cout << "发现有两个邻接元素的奇偶性相同: " << endl;
    cout <<  *iResult << endl;
    iResult++;
    cout <<  *iResult << endl;
  }
  return 0;
}

   21.5 范围查找容器元素find_first_of
     find_first_of  Find element from set in range (function template)

//   21.5 范围查找容器元素find_first_of -------------------------------------


template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_first_of ( ForwardIterator1 first1, ForwardIterator1 last1,
                                   ForwardIterator2 first2, ForwardIterator2 last2)
{
  for ( ; first1 != last1; ++first1 )
    for (ForwardIterator2 it=first2; it!=last2; ++it) // 第二组范围，作为参考、寻找对象
      if (*it==*first1)          // or: if (comp(*it,*first)) for the pred version
        return first1;  // 返回的是第一组范围中的某值的 iterator
  return last1;
}



// find_first_of example
#include <iostream>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;

bool comp_case_insensitive (char c1, char c2) {
  return (tolower(c1)==tolower(c2));
}

int main () {
  int mychars[] = {'a','b','c','A','B','C'};
  vector<char> myvector (mychars,mychars+6);
  vector<char>::iterator it;

  int match[] = {'A','B','C'};

  // using default comparison:
  it = find_first_of (myvector.begin(), myvector.end(), match, match+3);

  if (it!=myvector.end())
    cout << "first match is: " << *it << endl; // 因为大小写敏感，找到的是'A'

  // using predicate comparison:
  it = find_first_of (myvector.begin(), myvector.end(),
                      match, match+3, comp_case_insensitive);

  if (it!=myvector.end())
    cout << "first match is: " << *it << endl; // 因为大小写不敏感了，所以找到的是第一个：'a'
  
  return 0;
}


//290
#include <algorithm>
#include <iostream>
int main(void)
{
  using namespace std;
  //定义两个字符串
  char *string1 = "abcdef7ghijklmn";
  char *string2 = "zyx3pr7ys";
  //范围查找string1于string2中
  char *result = find_first_of(string1, string1 + strlen(string1), 
    string2, string2 + strlen(string2));

  // 应该加上判断，要是找不到呢？
  if(result!=string1 + strlen(string1))
    cout << "字符串string1的第一个出现在string2的字符为：" <<  *result << endl;
    //打印7

  // my test
  size_t i=distance(string1, result);
  cout << i << "  " << string1[i] << endl;

  return 0;
}



//290 思考：假设s2中的元素非常多，那么在集合中寻找，是否能提高速度？
#include <algorithm>
#include <iostream>
#include <set>
#include <string>
using namespace std;

int main(void)
{
  string s1 = "abcdef7ghijklmn";
  string s2 = "zyx3pr7ys";
  set<char> s(s2.begin(),s2.end()); // 放到集合中
  
  string::iterator it=find_first_of(
    s1.begin(),s1.end(),
    s.begin(),s.end());
  
  if(it!=s1.end()) cout << *it << endl;
    
  return 0;
}

   21.6 统计等于某值的容器元素个数count
     count  Count appearances of value in range (function template)

//   21.6 统计等于某值的容器元素个数count ---------------------------------------


template <class InputIterator, class T>
  ptrdiff_t count ( InputIterator first, InputIterator last, const T& value )
{
  ptrdiff_t ret=0;
  while (first != last) if (*first++ == value) ++ret;
  return ret;
}



// count algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int mycount;

  // counting elements in array:
  int myints[] = {10,20,30,30,20,10,10,20};   // 8 elements
  mycount = (int) count (myints, myints+8, 10); //可以直接操作数组
  cout << "10 appears " << mycount << " times.
";

  // counting elements in container:
  vector<int> myvector (myints, myints+8);
  mycount = (int) count (myvector.begin(), myvector.end(), 20);
  cout << "20 appears " << mycount  << " times.
";

  return 0;
}


//291
#include <algorithm>
#include <list>
#include <iostream>
int main(void)
{
  using namespace std;
  //
  list < int > l;
  for(int i = 0; i < 100; i++)
    l.push_back(i % 20);
  //
  int num = 0;
  int value = 9;
  num = count(l.begin(), l.end(), value);
  cout << "链表中元素等于value的元素个数为: " << num << endl; //打印5
  return 0;
}

   21.7 条件统计容器元素个数count_if
     count_if  Return number of elements in range satisfying condition (function template)

//   21.7 条件统计容器元素个数count_if --------------------------------------------


template <class InputIterator, class Predicate>
  ptrdiff_t count_if ( InputIterator first, InputIterator last, Predicate pred )
{
  ptrdiff_t ret=0;
  while (first != last) if (pred(*first++)) ++ret;
  return ret;
}


// count_if example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool IsOdd (int i) { return ((i%2)==1); }

int main () {
  int mycount;

  vector<int> myvector;
  for (int i=1; i<10; i++) myvector.push_back(i); // myvector: 1 2 3 4 5 6 7 8 9
  //谓词：找出奇数个数
  mycount = (int) count_if (myvector.begin(), myvector.end(), IsOdd);
  cout << "myvector contains " << mycount  << " odd values.
";

  return 0;
}



// 292
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;

struct StudentRecord
{
  struct StudentInfo
  {
    char *name;
    int year;
    char *addr;
  };
  int id; //学号
  StudentInfo sf; //学生信息
  StudentRecord(int id_, char *name_, int year_, char *addr_)
  {
    id = id_;
    sf.name = name_;
    sf.year = year_;
    sf.addr = addr_;
  }
};

bool setRange20_30(pair < int, StudentRecord::StudentInfo > s)
{
  // 20< x <30
  if(s.second.year > 20 && s.second.year < 30)
    return 1;
  return 0;
}

int main(void)
{
  //学生数据
  StudentRecord st1 = StudentRecord(1, "李强", 21, "北京");
  StudentRecord st2 = StudentRecord(2, "李文", 29, "上海");
  StudentRecord st3 = StudentRecord(3, "敦介", 12, "浙江");
  StudentRecord st4 = StudentRecord(4, "王强", 23, "山东");
  StudentRecord st5 = StudentRecord(5, "王文", 31, "江苏");
  //映照容器
  map < int, StudentRecord::StudentInfo > m;
  //插入5条学生记录
  pair < int, StudentRecord::StudentInfo > pairSt1(st1.id, st1.sf);
  m.insert(pairSt1);
  pair < int, StudentRecord::StudentInfo > pairSt2(st2.id, st2.sf);
  m.insert(pairSt2);
  pair < int, StudentRecord::StudentInfo > pairSt3(st3.id, st3.sf);
  m.insert(pairSt3);
  pair < int, StudentRecord::StudentInfo > pairSt4(st4.id, st4.sf);
  m.insert(pairSt4);
  pair < int, StudentRecord::StudentInfo > pairSt5(st5.id, st5.sf);
  m.insert(pairSt5);
  //条件统计
  int num = 0;
  num = count_if(m.begin(), m.end(), setRange20_30);
  cout << "年龄介于20至30岁之间的学生人数为: " << num << endl; //打印3
  return 0;
}

   21.8 元素不匹配查找mismatch
     mismatch  Return first position where two ranges differ (function template)

//   21.8 元素不匹配查找mismatch ----------------------------------------


template <class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2>
    mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
  while ( first1!=last1 )
  {
    if (*first1 != *first2)   // or: if (!pred(*first1,*first2)), for pred version
      break; // 不匹配，就跳出循环，返回
    ++first1; ++first2; // 奇怪，木有last2
  }
  return make_pair(first1,first2); // 返回的是pair，里面是两个迭代器
}
// 第二组必须较长，至少相等
// 要注意一点：因为木有last2，所以要求程序员自己把握，不能让第二个范围，长度短于第一个范围的，否则完全可能运行时错误


// mismatch algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {

  vector<int> myvector;
  for (int i=1; i<6; i++) myvector.push_back (i*10); // myvector: 10 20 30 40 50

  int myints[] = {10,20,80,320,1024};                //   myints: 10 20 80 320 1024

  pair<vector<int>::iterator,int*> mypair;

  // using default comparison:
  mypair = mismatch (myvector.begin(), myvector.end(), myints);
  cout << "First mismatching elements: " << *mypair.first;
  cout << " and " << *mypair.second << endl; // 30 80

  mypair.first++; mypair.second++;

  // using predicate comparison:
  mypair = mismatch (mypair.first, myvector.end(), mypair.second, mypredicate);
  cout << "Second mismatching elements: " << *mypair.first;
  cout << " and " << *mypair.second << endl;; // 40 320
  
  return 0;
}



// mismatch algorithm example。my test:因为有谓词判断，可以用不相等，来判断相等。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i!=j); // 不相等
}

int main () {

  vector<int> myvector;
  for (int i=1; i<6; i++) myvector.push_back (i*10); // myvector: 10 20 30 40 50

  int myints[] = {10,20,80,320,50};                  //   myints: 10 20 80 320 50

  pair<vector<int>::iterator,int*> mypair;

  // using default comparison:
  mypair = mismatch (myvector.begin(), myvector.end(), myints);
  cout << "First mismatching elements: " << *mypair.first;
  cout << " and " << *mypair.second << endl; // 30 80

  mypair.first++; mypair.second++;

  // using predicate comparison:
  mypair = mismatch (mypair.first, myvector.end(), mypair.second, mypredicate);
  cout << "Second mismatching elements: " << *mypair.first; // 当不不相等时。。^_^ 
  cout << " and " << *mypair.second << endl;; // 50 50
  
  return 0;
}


// 294。不鼓励使用C形式字符串。都使用STL了，Cpp中的string，就是STL中的一种容器。
#include <algorithm>
#include <vector>
#include <iostream>
bool strEqual(const char *s1, const char *s2)
{
  return strcmp(s1, s2) == 0 ? 1 : 0;
}
int main(void)
{
  using namespace std;
  //初始化向量v1、v2
  vector < int > v1, v2;
  v1.push_back(2);
  v1.push_back(0);
  v1.push_back(0);
  v1.push_back(6);
  v2.push_back(2);
  v2.push_back(0);
  v2.push_back(0);
  v2.push_back(7);
  //v1和v2不匹配检查
  pair < vector < int > ::iterator, vector < int > ::iterator > result1 =
    mismatch(v1.begin(), v1.end(), v2.begin());
  if(result1.first == v1.end() && result1.second == v1.end())
    cout << "v1和v2完全相同" << endl;
  else
    cout << "v1和v2不相同,不匹配的数是:
" <<  *result1.first << endl <<
      *result1.second << endl << endl;
  //初始化字符串s1、s2
  char *s1[] = { "apple", "pear", "watermelon", "banana", "grape" };
  char *s2[] = { "apple", "pears", "watermelons", "banana", "grape" };
  //s1和s2不匹配检查
  pair < char **, char ** > result2 = mismatch(s1, s1 + 5, s2, strEqual);
  if(result2.first == s1 + 5 && result2.second == s2 + 5)
    cout << "s1和s2完全相同" << endl;
  else
    cout << "s1与s2不相同,不匹配的字符串为:
" << s1[result2.first - s1] <<
      endl << s2[result2.second - s2] << endl << endl;
  return 0;
}

   21.9 元素相等判断equal
     equal  Test whether the elements in two ranges are equal (function template)

//   21.9 元素相等判断equal -----------------------------------------------

template <class InputIterator1, class InputIterator2>
  bool equal ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
  while ( first1!=last1 )
  {
    if (*first1 != *first2)   // or: if (!pred(*first1,*first2)), for pred version
      return false;
    ++first1; ++first2; // 坑爹啊，又木有 last2
  }
  return true;
}
// 注意范围。第二组必须较长，至少相等


// equal algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {

  int myints[] = {20,40,60,80,100};          //   myints: 20 40 60 80 100
  vector<int>myvector (myints,myints+5);     // myvector: 20 40 60 80 100

  // using default comparison:
  if (equal (myvector.begin(), myvector.end(), myints))
    cout << "The contents of both sequences are equal." << endl;
  else
    cout << "The contents of both sequences differ." << endl;

  myvector[3]=81;                            // myvector: 20 40 60 81 100

  // using predicate comparison:
  if (equal (myvector.begin(), myvector.end(), myints, mypredicate))
    cout << "The contents of both sequences are equal." << endl;
  else
    cout << "The contents of both sequences differ." << endl;
  
  return 0;
}



// equal algorithm example. my test，关于范围长短。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {

  int myints[] = {20,40,60,80,100};          //   myints: 20 40 60 80 100
  vector<int>myvector (myints,myints+5);     // myvector: 20 40 60 80 100

  // 如第二组较长，前面部分一样，则认为 equal
  myvector.erase(--myvector.end());
  cout << myvector.size() << endl;
  if (equal (myvector.begin(), myvector.end(), myints))
    cout << "The contents of both sequences are equal." << endl;
  else
    cout << "The contents of both sequences differ." << endl;

  // 如第二组较短，就算前面部分一样，也认为是 differ
  myvector.push_back(100);
  myvector.push_back(3);
  cout << myvector.size() << endl;
  if (equal (myvector.begin(), myvector.end(), myints))
    cout << "The contents of both sequences are equal." << endl;
  else
    cout << "The contents of both sequences differ." << endl;
  
  return 0;
}




//296
#include <algorithm>
#include <vector>
#include <iostream>
bool absEqual(int a, int b)
{
  return abs(a)==abs(b);
}
int main(void)
{
  using namespace std;
  //初始化向量v1、v2
  vector < int > v1(5);
  vector < int > v2(5);
  for(unsigned int i = 0; i < v1.size(); i++)
  {
    v1[i] = i;
    v2[i] =  -i;
  }
  //v1、v2相等检查
  if(equal(v1.begin(), v1.end(), v2.begin(), absEqual))
    cout << "v1和v2元素的绝对值完全相等" << endl;
  else
    cout << "v1和v2元素的绝对值不完全相等" << endl;
  return 0;
}

   21.10 子序列搜索search
     search  Find subsequence in range (function template)

//   21.10 子序列搜索search ------------------------------------------------------

/*
advance:
http://www.cplusplus.com/reference/iterator/
http://www.cplusplus.com/reference/iterator/advance/
*/


template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
                            ForwardIterator2 first2, ForwardIterator2 last2)
{
  ForwardIterator1 it1, limit;
  ForwardIterator2 it2;

  limit=first1;  // 要求第一个范围比较大。如果第二个范围比较大，肿么办？
  advance(limit,1+distance(first1,last1)-distance(first2,last2));

  while (first1!=limit) // first1到limit位置，无法比较了，长度不够了
  {
    it1 = first1; it2 = first2;
    while (*it1==*it2)        // or: while (pred(*it1,*it2)) for the pred version
      { ++it1; ++it2; if (it2==last2) return first1; }
    ++first1;
  }
  return last1;
}
// 第一组必须较长，至少相等。能够正常运行。以上模板是原理性的，不是真正程序



// search algorithm example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

  // set some values:        myvector: 10 20 30 40 50 60 70 80 90
  for (int i=1; i<10; i++) myvector.push_back(i*10);


  // using default comparison:
  int match1[] = {40,50,60,70};
  it = search (myvector.begin(), myvector.end(), match1, match1+4);

  if (it!=myvector.end())
    cout << "match1 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match1 not found" << endl;

  // using predicate comparison:
  int match2[] = {20,30,50};
  it = search (myvector.begin(), myvector.end(), match2, match2+3, mypredicate);

  if (it!=myvector.end())
    cout << "match2 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match2 not found" << endl;
  
  return 0;
}



// search algorithm example. my test，破坏性实验，如果第二组较长会如何？能够正常运行
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

  // set some values:        myvector: 10 20 30 40 50 60 70 80 90
  for (int i=1; i<10; i++) myvector.push_back(i*10);


  // using default comparison:
  int match1[] = {40,50,60,70};
  it = search (myvector.begin(), myvector.end(), match1, match1+4);

  if (it!=myvector.end())
    cout << "match1 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match1 not found" << endl;

  // using predicate comparison:
  int match2[] = {20,30,50,3,3,3,3,3,3,3,3,3,3,3,3}; // 破坏性实验
  it = search (myvector.begin(), myvector.end(), match2, match2+15, mypredicate);

  if (it!=myvector.end())
    cout << "match2 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match2 not found" << endl;
  
  return 0;
}



// search algorithm example。my test:谓词可以修改，以比较连续不相等
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i!=j); // 如果修改这里，就是比较连续不相等
}

int main () {
  vector<int> myvector;
  vector<int>::iterator it;

  // set some values:        myvector: 10 20 30 40 50 60 70 80 90
  for (int i=1; i<10; i++) myvector.push_back(i*10);


  // using default comparison:
  int match1[] = {40,50,60,70};
  it = search (myvector.begin(), myvector.end(), match1, match1+4);

  if (it!=myvector.end())
    cout << "match1 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match1 not found" << endl;

  // using predicate comparison:
  int match2[] = {20,30,50};
  it = search (myvector.begin(), myvector.end(), match2, match2+3, mypredicate);

  if (it!=myvector.end())
    cout << "match2 found at position " << int(it-myvector.begin()) << endl;
  else
    cout << "match2 not found" << endl;
  
  return 0;
}


//298
#include <algorithm>
#include <vector>
#include <iostream>
int main(void)
{
  using namespace std;
  //初始化向量v1={5, 6, 7, 8, 9 }
  vector < int > v1;
  v1.push_back(5);
  v1.push_back(6);
  v1.push_back(7);
  v1.push_back(8);
  v1.push_back(9);
  //初始化向量v2={7, 8}
  vector < int > v2;
  v2.push_back(7);
  v2.push_back(8);
  //检查v2是否构成v1的子序列
  vector < int > ::iterator iterLocation;
  iterLocation = search(v1.begin(), v1.end(), v2.begin(), v2.end());
  //打印从v1[2]开始匹配
  if(iterLocation != v1.end())
    cout << "v2的元素包含在v1中,起始元素为" << "v1[" << iterLocation - v1.begin
      () << "]
";
  else
    cout << "v2的元素不包含在v1中" << endl;
  return 0;
}

   21.11 重复元素子序列搜索search_n
     search_n  Find succession of equal values in range (function template)

//   21.11 重复元素子序列搜索search_n ------------------------------------------


template<class ForwardIterator, class Size, class T>
  ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
                             Size count, const T& value )
{
  ForwardIterator it, limit;
  Size i;

  limit=first; 
  advance(limit,distance(first,last)-count); // count过大，limit可能异常。但真正的实现程序，应该有保护措施

  while (first!=limit)
  {
    it = first; i=0;
    while (*it==value)       // or: while (pred(*it,value)) for the pred version
      { ++it; if (++i==count) return first; } // 找到连续count个value，返回first迭代器
    ++first;
  }
  return last;
}
// count 不可过大。过大时，也正常运行


// search_n example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i==j);
}

int main () {
  int myints[]={10,20,30,30,20,10,10,20};
  vector<int> myvector (myints,myints+8);

  vector<int>::iterator it;

  // using default comparison:
  it = search_n (myvector.begin(), myvector.end(), 2, 30); // 连续2个30

  if (it!=myvector.end())
    cout << "two 30s found at position " << int(it-myvector.begin()) << endl; // 2
  else
    cout << "match not found" << endl;

  // using predicate comparison:
  it = search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate);

  if (it!=myvector.end())
    cout << "two 10s found at position " << int(it-myvector.begin()) << endl; // 5
  else
    cout << "match not found" << endl;
  
  return 0;
}



// search_n example。my test: 修改谓词，也可以判断连续不相等。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool mypredicate (int i, int j) {
  return (i!=j); // 修改这里
}

int main () {
  int myints[]={10,20,30,30,20,10,10,20};
  vector<int> myvector (myints,myints+8);

  vector<int>::iterator it;

  // using default comparison:
  it = search_n (myvector.begin(), myvector.end(), 2, 30); // 连续2个，与30相等

  if (it!=myvector.end())
    cout << "two 30s found at position " << int(it-myvector.begin()) << endl; // 2
  else
    cout << "match not found" << endl;

  // using predicate comparison:
  it = search_n (myvector.begin(), myvector.end(), 2, 10, mypredicate); // 连续2个，与10不相等

  if (it!=myvector.end())
    cout << "two 10s found at position " << int(it-myvector.begin()) << endl; // 1
  else
    cout << "match not found" << endl;
  
  return 0;
}


//301。这个程序也说明了count过大的问题。
#include <algorithm>
#include <vector>
#include <iostream>
int main(void)
{
  using namespace std;
  //初始化向量v={1, 8, 8, 8, 6, 6, 8}
  vector < int > v;
  v.push_back(1);
  v.push_back(8);
  v.push_back(8);
  v.push_back(8);
  v.push_back(6);
  v.push_back(6);
  v.push_back(8);
  //查找子序列{8, 8, 8}
  vector < int > ::iterator iLocation;
  iLocation = search_n(v.begin(), v.end(), 3, 8);
  if(iLocation != v.end())
    cout << "在v中找到3个连续的元素8" << endl;
  else
    cout << "v中没有3个连续的元素8" << endl;
  //查找子序列{8, 8, 8, 8}
  iLocation = search_n(v.begin(), v.end(), 4, 8);
  if(iLocation != v.end())
    cout << "在v中找到4个连续的元素8" << endl;
  else
    cout << "v中没有4个连续的元素8" << endl;
  //查找子序列{6, 6}
  iLocation = search_n(v.begin(), v.end(), 2, 6);
  if(iLocation != v.end())
    cout << "在v中找到2个连续的元素6" << endl;
  else
    cout << "v中没有2个连续的元素6" << endl;
  return 0;
}

   21.12 最后一个子序列搜索find_end
     find_end  Find last subsequence in range (function template)

//   21.12 最后一个子序列搜索find_end -------------------------------------------



template<class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
                              ForwardIterator2 first2, ForwardIterator2 last2)
{
  ForwardIterator1 it1, limit, ret;
  ForwardIterator2 it2;

  limit=first1; 
  advance(limit,1+distance(first1,last1)-distance(first2,last2));
  ret=last1;

  while (first1!=limit)
  {
    it1 = first1; it2 = first2;
    while (*it1==*it2)          // or: while (pred(*it1,*it2)) for the pred version
      { ++it1; ++it2; if (it2==last2) {ret=first1;break;} } // break跳出的是内循环，会继续外循环。
    ++first1;  // 所以找到的是最后一个符合条件的
  }
  return ret;
}
// A similar algorithm function, but returning the first occurrence instead of the last, is search.
// 与search基本一样，无非是search一找到，就返回了。


// find_end example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i, int j) {
  return (i==j);
}

int main () {
  int myints[] = {1,2,3,4,5,1,2,3,4,5};
  vector<int> myvector (myints,myints+10);
  vector<int>::iterator it;

  int match1[] = {1,2,3};

  // using default comparison:
  it = find_end (myvector.begin(), myvector.end(), match1, match1+3);

  if (it!=myvector.end())
    cout << "match1 last found at position " << int(it-myvector.begin()) << endl; // 5

  int match2[] = {4,5,1};

  // using predicate comparison:
  it = find_end (myvector.begin(), myvector.end(), match2, match2+3, myfunction);

  if (it!=myvector.end())
    cout << "match2 last found at position " << int(it-myvector.begin()) << endl; // 3
  
  return 0;
}



// find_end example. my test:当第二组过长时，能够正常运行
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfunction (int i, int j) {
  return (i==j);
}

int main () {
  int myints[] = {1,2,3,4,5,1,2,3,4,5};
  vector<int> myvector (myints,myints+10);
  vector<int>::iterator it;

  int match1[] = {1,2,3};

  // using default comparison:
  it = find_end (myvector.begin(), myvector.end(), match1, match1+3);

  if (it!=myvector.end())
    cout << "match1 last found at position " << int(it-myvector.begin()) << endl; // 5

  int match2[] = {4,5,1,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3}; // 做个破坏性实验

  // using predicate comparison:
  it = find_end (myvector.begin(), myvector.end(), match2, match2+20, myfunction);

  if (it!=myvector.end())
    cout << "match2 last found at position " << int(it-myvector.begin()) << endl; // 3
  else cout << "it==myvector.end()" << endl; // 能够返回 end()
  
  return 0;
}



// p303

#include <algorithm>
#include <vector>
#include <iostream>
int main(void)
{
  using namespace std;
  //初始化向量v1={-5, 1, 2, -6, -8, 1, 2, -11}
  vector < int > v1;
  v1.push_back( - 5);
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back( - 6);
  v1.push_back( - 8);
  v1.push_back(1);
  v1.push_back(2);
  v1.push_back( - 11);
  //初始化向量v2={1, 2}
  vector < int > v2;
  v2.push_back(1);
  v2.push_back(2);
  //v1中查找最后一个子序列v2
  vector < int > ::iterator iLocation;
  iLocation = find_end(v1.begin(), v1.end(), v2.begin(), v2.end());
  //打印子序列在v1的起始位置v[5]
  if(iLocation != v1.end())
    cout << "v1中找到最后一个匹配v2的子序列,位置在" << "v1[" << iLocation -
      v1.begin() << "]" << endl;
  return 0;
}

   21.13 本章小结

/*

//   21.13 本章小结 -------------------------------------------------------------

最后总结一下：


   21.1 逐个容器元素for_each
对容器一定范围内的元素，进行循环操作。前两个参数表示范围，第三个参数是函数（对象）

   21.2 查找容器元素find
在容器一定范围内，查找记录等于某值的元素。前两个参数表示范围，第三个参数为某值。

   21.3 条件查找容器元素find_if
是find的谓词判断版本，第三个参数为谓词判断函数（对象）。

   21.4 邻近查找容器元素adjacent_find
查找相等或满足条件的邻近元素对。前两个参数表示范围，第三个参数可无，有时是谓词判断的函数（对象）。

   21.5 范围查找容器元素find_first_of
查找第一范围内的元素，在第二范围内第一次出现的位置。前两个参数表示第一范围，接着两个参数表示第二范围。
第五个参数可无，有时是谓词判断的函数（对象）。

   21.6 统计等于某值的容器元素个数count
计算容器某一范围内，给定值的出现次数。前两个参数表示范围，第三个参数为给定值。

   21.7 条件统计容器元素个数count_if
是count是谓词判断版本，计算容器某范围内的符合条件的元素个数。前两个参数表示范围，第三个参数为函数（对象）。

   21.8 元素不匹配查找mismatch
比较两个序列，找出首个不匹配元素的位置。前两个参数表示第一序列范围，第三个参数为第二序列开始位置。
注意：木有第二序列结束位置的参数。所以第二序列最好较长。
第四个参数可无，如有是谓词判断函数（对象）。
返回的是pair，pair中分别记录首个不匹配的第一、二序列的位置。

   21.9 元素相等判断equal
逐一比较两个序列的元素是否相等。参数同mismatch。
注意：如果第一序列较长，一定返回false。如果第二序列较长，比较前面的元素。
返回bool。

   21.10 子序列搜索search
在第一序列中，搜索与第二序列匹配的子序列，即把第二序列当子序列看。
前两个参数表示第一序列范围，接着两个参数表示第二序列范围。第五个参数可无，如有是谓词性质的函数（对象）。
如第二序列较长，返回第一序列的end()位置，即第二个参数。

   21.11 重复元素子序列搜索search_n
搜索序列中，是否有一系列元素值均为某一给定值的子序列。
前两个参数表示范围，第三个参数是count，第四个参数为value。第五个参数可无，如有是谓词性质的函数（对象）。
如count过大，返回第二个参数。

   21.12 最后一个子序列搜索find_end
在一个序列中搜索出最后一个与另一序列匹配的子序列。
参数与search一样。


*/

  

000TOP000