// copy()を使用する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v(10);
  vector< char> v2(10);
  int i;

  for(i=0; i<10; i++) v[i] = 'A'+i;
  for(i=0; i<10; i++) v2[i] = 'z';

  // vのすべての要素をv2にコピーする
  copy(v.begin(), v.end(), v2.begin());

  cout << "Contents of v2 after complete copy:\n";
  for(i=0; i<10; i++)
    cout << v2[i] << " ";
  cout << "\n\n";

  // v2を再び初期化する
  for(i=0; i<10; i++) v2[i] = 'z';

  // vの一部をv2にコピーする
  copy(v.begin()+2, v.end()-2, v2.begin());

  cout << "Contents of v2 after subsequence copy:\n";
  for(i=0; i<10; i++)
    cout << v2[i] << " ";
  cout << "\n\n";

  // v2を再び初期化する
  for(i=0; i<10; i++) v2[i] = 'z';

  // vの一部をv2の中間にコピーする
  copy(v.begin()+2, v.end()-2, v2.begin()+3);

  cout << "Contents of v2 after copy into middle:\n";
  for(i=0; i<10; i++)
    cout << v2[i] << " ";
  cout << "\n\n";

  return 0;
}

// swap_ranges()を使用する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v(10);
  vector< char> v2(10);
  int i;

  for(i=0; i<10; i++) v[i] = 'A'+i;
  for(i=0; i<10; i++) v2[i] = '0' + i;

  cout << "Original contents of v:\n";
  for(i=0; i<10; i++)
    cout << v[i] << " ";
  cout << "\n";
  cout << "Original contents of v2:\n";
  for(i=0; i<10; i++)
    cout << v2[i] << " ";
  cout << "\n\n";

  // vとv2の範囲を交換する
  swap_ranges(v.begin()+2, v.end()-3, v2.begin()+4);

  cout << "Contents of v after swap:\n";
  for(i=0; i<10; i++)
    cout << v[i] << " ";
  cout << "\n";
  cout << "Contents of v2 after swap:\n";
  for(i=0; i<10; i++)
    cout << v2[i] << " ";
  cout << "\n";

  return 0;
}

// find()とfind_if()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
#include < cstring>
using namespace std;

// chがカンマならtrueを返す
bool iscomma(char ch)
{
  if(ch==',') return true;
  return false;
}

int main()
{
  vector< char> v;
  vector< char>::iterator p;
  char str[] = "One, Two, Three";
  int i;

  for(i=0; i< strlen(str); i++)
    v.push_back(str[i]);

  cout << "Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout << v[i];
  cout << endl;

  // find the first T
  p = find(v.begin(), v.end(), 'T');
  cout << "Sequence beginning with T: ";
  while(p != v.end())
    cout << *p++;
  cout << endl;

  // 最初のカンマを探す
  p = find_if(v.begin(), v.end(), iscomma);
  cout << "After find first comma: ";
  while(p != v.end())
    cout << *p++;
  cout << endl;

  return 0;
}

// search()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
#include < cstring>
using namespace std;

int main()
{
  vector< char> v, v2;
  vector< char>::iterator p;
  char str1[] = "One, Two, Three, Two again";
  char str2[] = "Two";
  int i;

  for(i=0; i< strlen(str1); i++)
    v.push_back(str1[i]);

  for(i=0; i< strlen(str2); i++)
    v2.push_back(str2[i]);

  cout << "Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout << v[i];
  cout << endl;

  // 最初の"Two"を探す
  p = search(v.begin(), v.end(), v2.begin(), v2.end());
  cout << "Sequence beginning with Two: ";
  while(p != v.end())
    cout << *p++;
  cout << endl;

  return 0;
}

// mismatch()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
#include < cstring>
#include < utility>
using namespace std;

int main()
{
  vector< char> v, v2;
  pair< vector< char>::iterator, vector< char>::iterator> p;
  char str1[] = "One, Two, Three, Two again";
  char str2[] = "One, Two, Four, Five, Nine";
  int i;

  for(i=0; i< strlen(str1); i++)
    v.push_back(str1[i]);

  for(i=0; i< strlen(str2); i++)
    v2.push_back(str2[i]);

  cout << "Contents of v:  ";
  for(i=0; i< v.size(); i++)
    cout << v[i];
  cout << endl;

  cout << "Contents of v2: ";
  for(i=0; i< v2.size(); i++)
    cout << v2[i];
  cout << endl;

  // 最初の相違を探す
  p = mismatch(v.begin(), v.end(), v2.begin());

  if(p.first != v.end()) { // mismatch found
    cout << "The character " << *p.first;
    cout << " in v mismatches the character ";
    cout << *p.second << " in v2.\n";
  }

  return 0;
}

// sort()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

void init_v(vector< int> &v)
{
  v[0] = 99;
  v[1] = 5;
  v[2] = 109;
  v[3] = -3;
  v[4] = 44;
  v[5] = 10;
  v[6] = 108;
  v[7] = 7;
  v[8] = 11;
  v[9] = 76;
}

int main()
{
  vector< int> v(10);
  int i;

  // コンテナのすべての要素をソートする
  init_v(v); // vを初期化する

  cout << "Sort an entire container.\n";
  cout << "Original order:\n";
  for(i=0; i<10; i++) 
    cout << v[i] << " ";
  cout << "\n";

  sort(v.begin(), v.end());

  cout << "Order after sorting container:\n";
  for(i=0; i<10; i++) 
    cout << v[i] << " ";
  cout << "\n\n";

  // コンテナの一部をソートする
  init_v(v); // vを再初期化する

  cout << "Sort a subset of a container.\n";
  cout << "Original order:\n";
  for(i=0; i<10; i++) 
    cout << v[i] << " ";
  cout << "\n";

  sort(v.begin()+2, v.end()-2);

  cout << "Order after sorting v[2] through v[7]:\n";
  for(i=0; i<10; i++) 
    cout << v[i] << " ";
  cout << "\n\n";

  return 0;
}

// partial_sort()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

void init_v(vector< int> &v)
{
  v[0] = 99;
  v[1] = 5;
  v[2] = 109;
  v[3] = -3;
  v[4] = 44;
  v[5] = 10;
  v[6] = 108;
  v[7] = 7;
  v[8] = 11;
  v[9] = 76;
}

int main()
{
  vector< int> v(10);
  int i;

  init_v(v); // vを初期化する

  cout << "Original order:\n";
  for(i=0; i<10; i++) 
    cout << v[i] << " ";
  cout << "\n";

  partial_sort(v.begin(), v.begin()+5, v.end());

  cout << "Order after partial sorting:\n";
  for(i=0; i<10; i++) 
    cout << v[i] << " ";
  cout << "\n";

  return 0;
}

// binary_search()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;
int main()
{
  vector< char> v;
  bool result;
  int i;

  for(i=0; i<10; i++)
    v.push_back('A' + i);

  cout << "Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout << v[i];
  cout << endl;

  // Fを検索する
  cout << "Looking for F.\n";
  result = binary_search(v.begin(), v.end(), 'F');
  if(result)
    cout << "F Found\n";
  else
    cout << "F Not Found\n";

  // Xを検索する
  cout << "Looking for X.\n";
  result = binary_search(v.begin(), v.end(), 'X');
  if(result)
    cout << "X Found\n";
  else
    cout << "X Not Found\n";

  return 0;
} 

// lower_bound()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;
int main()
{
  vector< char> v;
  vector< char>::iterator p;
  int i;

  for(i=0; i<10; i++)
    v.push_back('A' + i);

  cout << "Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout << v[i];
  cout << endl;

  // Fを検索する
  cout << "Looking for F.\n";
  p = lower_bound(v.begin(), v.end(), 'F');
  if(p != v.end())
    cout << *p << " Found\n";
  else
    cout << "F Not Found\n";

  // Xを検索する
  cout << "Looking for X.\n";
  p = lower_bound(v.begin(), v.end(), 'X');
  if(p != v.end())
    cout << *p << " Found\n";
  else
    cout << "X Not Found\n";

  return 0;
}

// remove()とreplace()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v;
  vector< char>::iterator p, p_end;
  int i;

  for(i=0; i<5; i++) {
    v.push_back('A'+i);
    v.push_back('A'+i);
    v.push_back('A'+i);
  }

  cout << "Original contents of v:\n";
  for(p=v.begin(); p< v.end(); p++)
    cout << *p << " ";
  cout << endl;

  // すべての"C"を削除する
  p_end = remove(v.begin(), v.end(), 'C');

  cout << "Sequence after removing all C's:\n";
  for(p=v.begin(); p< p_end; p++)
    cout << *p << " ";
  cout << endl;

  // "D"を"X"に置換する
  replace(v.begin(), v.end(), 'D', 'X');

  cout << "Sequence after replacement:\n";
  for(p=v.begin(); p< p_end; p++)
    cout << *p << " ";
  cout << endl;

  return 0;
}

// unique()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v;
  vector< char>::iterator p, p_end;
  int i;

  for(i=0; i<5; i++) {
    v.push_back('A'+i);
    v.push_back('A'+i);
    v.push_back('A'+i);
  }

  cout << "Original contents of v:\n";
  for(p=v.begin(); p< v.end(); p++)
    cout << *p << " ";
  cout << endl;

  // 重複要素を削除する
  p_end = unique(v.begin(), v.end());

  cout << "Sequence after removing duplicates:\n";
  for(p=v.begin(); p< p_end; p++)
    cout << *p << " ";
  cout << endl;

  return 0;
}

// シーケンスの変換
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

double midpoint(double a, double b)
{
  return ((a-b) / 2) + b;
}

int main()
{
  vector< double> v1(5), v2(5), v3(5);
  int i;

  v1[0] = 10.0;
  v1[1] = 98.6;
  v1[2] = 12.23;
  v1[3] = 88.8;
  v1[4] = -212.01;

  v2[0] = 2.0;
  v2[1] = 3.3;
  v2[2] = 4.19;
  v2[3] = 155.0;
  v2[4] = -2.0;

  cout << "Values in v1: ";
  for(i=0; i< v1.size(); i++)
    cout << v1[i] << " ";
  cout << endl;

  cout << "Values in v2: ";
  for(i=0; i< v2.size(); i++)
    cout << v2[i] << " ";
  cout << endl;

  // v1の要素とv2の要素の中点を見つける
  transform(v1.begin(), v1.end(), v2.begin(),
            v3.begin(), midpoint);

  // 中点
  cout << "Midpoints: ";
  for(i=0; i< v3.size(); i++)
    cout << v3[i] << " ";

  return 0;
}

// シーケンスの生成
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

// 簡単な生成関数
double f()
{
  static double val = 1.0;
  double t;

  t = 1.0 / val;
  val += val;

  return t;
}

int main()
{
  vector< double> v(5);
  int i;

  // 数列を生成する
  generate(v.begin(), v.end(), f);

  cout << "Series: ";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";

  return 0;
}

// シーケンスを回転する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< int> v;
  vector< int>::iterator p;
  int i;
  
  for(i=0; i<10; i++) v.push_back(i);

  cout << "Original ordering: ";
  for(p=v.begin(); p< v.end(); p++)
    cout << *p << " ";
  cout << endl;

  // 左方向に1つ回転する
  rotate(v.begin(), v.begin()+1, v.end());

  cout << "Order after left rotate: ";
  for(p=v.begin(); p< v.end(); p++)
    cout << *p << " ";
  cout << endl;

  return 0;
}

// シーケンスを右方向に回転する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< int> v;
  vector< int>::iterator p;
  int i;
  
  for(i=0; i<10; i++) v.push_back(i);

  cout << "Original ordering: ";
  for(p=v.begin(); p< v.end(); p++)
    cout << *p << " ";
  cout << endl;

  // 逆方向反復子を使って右方向に2つ回転する
  rotate(v.rbegin(), v.rbegin()+2, v.rend());

  cout << "Order after two right rotates: ";
  for(p=v.begin(); p< v.end(); p++)
    cout << *p << " ";
  cout << endl;

  return 0;
}

// random_shuffle()の使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v;
  int i;

  for(i=0; i<26; i++) v.push_back('A'+i);

  cout << "Original contents of v:\n";
  for(i=0; i< v.size(); i++)
    cout << v[i];
  cout << "\n\n";

  random_shuffle(v.begin(), v.end());

  cout << "Shuffled contents of v:\n";
  for(i=0; i< v.size(); i++)
    cout << v[i];

  return 0;
}

// 2つのシーケンスをマージする
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v1, v2, v3(26);
  int i;

  for(i=0; i<26; i+=2) v1.push_back('A'+i);
  for(i=0; i<26; i+=2) v2.push_back('B'+i);

  cout << "Original contents of v1:\n";
  for(i=0; i< v1.size(); i++)
    cout << v1[i];
  cout << "\n\n";

  cout << "Original contents of v2:\n";
  for(i=0; i< v2.size(); i++)
    cout << v2[i];
  cout << "\n\n";

  // シーケンスをマージする
  merge(v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        v3.begin());

  cout << "Result of merge:\n";
  for(i=0; i< v3.size(); i++)
    cout << v3[i];

  return 0;
}

// 同一シーケンス内でマージを行う
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v1;
  int i;

  for(i=0; i<26; i+=2) v1.push_back('A'+i);
  for(i=0; i<26; i+=2) v1.push_back('B'+i);

  cout << "Original contents of v1:\n";
  for(i=0; i< v1.size(); i++)
    cout << v1[i];
  cout << "\n\n";

  // v1内の2つの範囲をマージする
  inplace_merge(v1.begin(), v1.begin()+13, v1.end());

  cout << "Result of merge:\n";
  for(i=0; i< v1.size(); i++)
    cout << v1[i];

  return 0;
}

// 集合アルゴリズムの使用例
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v1, v2, v_res(26), v3;
  vector< char>::iterator p, pres_end;
  int i;

  for(i=0; i<20; i++) v1.push_back('A'+i);
  for(i=10; i<26; i++) v2.push_back('A'+i);

  cout << "Contents of v1:\n";
  for(i=0; i< v1.size(); i++)
    cout << v1[i];
  cout << "\n";

  cout << "Contents of v2:\n";
  for(i=0; i< v2.size(); i++)
    cout << v2[i];
  cout << "\n\n";

  // 和
  pres_end = set_union(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),
                 v_res.begin());

  cout << "Set union: ";
  for(p=v_res.begin(); p!=pres_end; p++)
    cout << *p;
  cout << "\n\n";

  // 差
  pres_end = set_difference(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),
                 v_res.begin());

  cout << "Set difference: ";
  for(p=v_res.begin(); p!=pres_end; p++)
    cout << *p;
  cout << "\n\n";

  // 対称差
  pres_end = set_symmetric_difference(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),
                 v_res.begin());

  cout << "Set symmetric difference: ";
  for(p=v_res.begin(); p!=pres_end; p++)
    cout << *p;
  cout << "\n\n";

  // 交差
  pres_end = set_intersection(v1.begin(), v1.end(),
                 v2.begin(), v2.end(),
                 v_res.begin());

  cout << "Set intersection: ";
  for(p=v_res.begin(); p!=pres_end; p++)
    cout << *p;
  cout << "\n\n";

  // 包含
  v3.push_back('A');
  v3.push_back('C');
  v3.push_back('D');

  // 以下の4行は監修者による追加
  cout << "Contents of v3: \n";
  for(i=0; i< v3.size(); i++)
    cout << v3[i];
  cout << "\n\n";

  if(includes(v1.begin(), v1.end(),
              v3.begin(), v3.end()))
    cout << "v1 includes all of v3\n";
  else
    cout << "v3 contains elements not found in v1\n";

  return 0;
}

// 順列を作成する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v;
  int i;

  for(i=0; i<3; i++) v.push_back('A'+i);

  cout << "All permutations of 3 characters:\n";

  do {
    for(i=0; i< v.size(); i++)
      cout << v[i];
    cout << "\n";
  } while(next_permutation(v.begin(), v.end()));

  return 0;
}

// 順列を作成する
#include 
#include 
#include 
using namespace std;

int main()
{
  vector v;
  int i;

  for(i=0; i<3; i++) v.push_back('A'+i);

  cout << "3文字の順列をすべて挙げると:\n";

  do {
    for(i=0; i< v.size(); i++)
      cout >< v[i];
    cout << "\n";
  } while(next_permutation(v.begin(), v.end()));

  return 0;
}

// ヒープを使用する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< char> v;
  int i;

  for(i=0; i<20; i+=2) v.push_back('A'+i);

  cout << "Sequence before building heap:\n";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n\n";

  // ヒープを構築する
  make_heap(v.begin(), v.end());

  cout << "Sequence after building heap:\n";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n\n";

  // ヒープに"H"をプッシュする
  v.push_back('H'); // まず、ベクタにHを挿入する
  push_heap(v.begin(), v.end()); // 次に、Hをヒープにプッシュする

  cout << "Sequence after pushing onto heap:\n";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n\n";

  // ヒープから値をポップする
  pop_heap(v.begin(), v.end());

  cout << "Sequence after poping from heap:\n";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n\n";

  return 0;
}

// 最小値と最大値を探す
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

int main()
{
  vector< int> v(5);
  int i;

  v[0] = 100;
  v[1] = -4;
  v[2] = 55;
  v[3] = 19;
  v[4] = 122;

  cout << "Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n\n";

  cout << "Maximum element is: ";
  cout << *max_element(v.begin(), v.end());
  cout << "\n";

  cout << "Minimum element is: ";
  cout << *min_element(v.begin(), v.end());

  return 0;
}

#include 
#include 
using namespace std;

int main()
{
  vector v;
  int i;

  for(i=0; i<10; i++) v.push_back(i);

  cout << "Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout >< v[i] << " ";
  cout << "\n";

  return 0;
}

// for_each()を使用する
#include < iostream>
#include < vector>
#include < algorithm>
using namespace std;

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

int main()
{
  vector< int> v;
  int i;

  for(i=0; i<10; i++) v.push_back(i);

  cout << "Contents of v: ";
  for_each(v.begin(), v.end(), show);
  cout << "\n";

  return 0;
}

// 独自のアルゴリズムを作成する
#include < iostream>
#include < vector>
#include < list>
#include < algorithm>
using namespace std;

// 特定の範囲の値を2倍にするアルゴリズム
template< class ForIter>
  void times2(ForIter start, ForIter end)
{
  while(start != end) {
    *start *= 2;
    start++;
  }
}

int main()
{
  int i;

  //**************************************
  // intのベクタにtimes2を適用する
  vector< int> v;

  for(i=0; i<10; i++) v.push_back(i);

  cout << "Initial Contents of v: ";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n";

  times2(v.begin(), v.end());

  cout << "Contents of v doubled: ";
  for(i=0; i< v.size(); i++)
    cout << v[i] << " ";
  cout << "\n\n";

  //**************************************
  // floatのリストにtimes2を適用する
  list< float> lst;
  list< float>::iterator p;

  for(i=0; i<5; i++) lst.push_back((float)i*3.1416);

  cout << "Initial Contents of lst: ";
  for(p=lst.begin(); p!=lst.end(); p++)
    cout << *p << " ";
  cout << "\n";

  times2(lst.begin(), lst.end());

  cout << "Contents of lst doubled: ";
  for(p=lst.begin(); p!=lst.end(); p++)
    cout << *p << " ";
  cout << "\n\n";

  return 0;
}