Boostライブラリを解読する 1. boost/algorithm

# Boostの紹介
こんにちは。AtCoder現在茶色です。普段コンテストではPythonとC++を使い分けているのですが、AtCoderで使えるBoostというC++ライブラリの存在を知り、できる限り活用したいなと思い、その前に機能を調べようと思いました。
Boostのダウンロード→https://www.boost.org/users/download/
（解凍するのに44分かかりました）
Boostの最新バージョンは1.82.0で、AtCoderの今年の言語アップデートではこのバージョンが使用されます。

僕もまだC++がいろいろわかるわけではないので、もし悪いところがあったら細かいところでもコメントでぜひ教えてください。

# boost/algorithm

## boost/algorithm/cxx11

### boost/algorithm/cxx11/all_of.hpp

``` ex1.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/all_of.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n == 1;
}

bool p2(int n) {
  return n % 2 == 1;
}

int main() {
  vector<int> v1 = {1, 1, 1, 1, 1};
  bool b1 = all_of(v1, p1); // v1の要素は条件p1をすべて満たすか
  cout << (b1 ? "Yes" : "No") << '\n';

  bool b1_same = all_of_equal(v1, 1); // v1の要素はすべて1か
  cout << (b1_same ? "Yes" : "No") << '\n';

  vector<int> v2 = {1, 1, 1, 1, 2};
  bool b2 = all_of(v2, p1);
  cout << (b2 ? "Yes" : "No") << '\n';

  bool b2_same = all_of_equal(v2, 1);
  cout << (b2_same ? "Yes" : "No") << '\n';

  vector<int> v3 = {1, 3, 5, 7, 9};
  bool b3 = all_of(v3, p2);
  cout << (b3 ? "Yes" : "No") << '\n';
  return 0;
}
```
```
Yes
Yes
No
No
Yes
```
all_ofという関数は、全ての要素が条件を満たすか調べられます。
all_of_equalという関数は、all_ofの特殊化で、配列の中の数がすべて関数の最後の引数に等しいかどうかを調べることができます。



### boost/algorithm/cxx11/any_of.hpp

``` ex2.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/any_of.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n == 1;
}

bool p2(int n) {
  return n % 2 == 1;
}

int main() {
  vector<int> v1 = {1, 2, 3, 4, 5};
  bool b1 = any_of(v1, p1); // 条件p1を満たすv1の要素はあるか
  cout << (b1 ? "Yes" : "No") << '\n';

  bool b1_same = any_of_equal(v1, 1); // v1に1は含まれているか
  cout << (b1_same ? "Yes" : "No") << '\n';

  vector<int> v2 = {2, 2, 3, 4, 5};
  bool b2 = any_of(v2, p1);
  cout << (b2 ? "Yes" : "No") << '\n';

  bool b2_same = any_of_equal(v2, 1);
  cout << (b2_same ? "Yes" : "No") << '\n';

  vector<int> v3 = {2, 3, 4, 4, 6};
  bool b3 = any_of(v3, p2);
  cout << (b3 ? "Yes" : "No") << '\n';
  return 0;
}
```
```
Yes
Yes
No
No
Yes
```
any_ofという関数は、要素のうち条件を満たすものがあるかを調べられます。
any_of_equalという関数は、any_ofの特殊化で、配列の中の数のうち関数の最後の引数に等しいものがあるかどうかを調べることができます。



### boost/algorithm/cxx11/copy_if.hpp

``` ex3.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/copy_if.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n % 2 == 1;
}

bool p2(int n) {
  return n <= 5;
}

bool p3(int n) {
  return n >= 6;
}

int main() {
  vector<int> v1 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
  vector<int> v1_odd(9);
  auto i1 = v1_odd.begin();
  i1 = copy_if(v1.begin(), v1.end(), i1, p1); // v1の中から奇数を取り出す
  for (auto i = v1_odd.begin(); i < i1; i++)
    cout << *i << ' ';
  cout << '\n';

  vector<int> v1_u5(9);
  auto i2 = v1_u5.begin();
  i2 = copy_while(v1.begin(), v1.end(), i2, p2).second; // v1の中から5以下の間取り出す
  for (auto i = v1_u5.begin(); i < i2; i++)
    cout << *i << ' ';
  cout << '\n';

  vector<int> v1_u5_2(9);
  auto i3 = v1_u5_2.begin();
  i3 = copy_until(v1.begin(), v1.end(), i3, p3).second; // v1の中から6以上を満たさない間取り出す
  for (auto i = v1_u5_2.begin(); i < i3; i++)
    cout << *i << ' ';
  cout << '\n';
  return 0;
}
```
```
3 1 1 5 9 5 3 
3 1 4 1 5 
3 1 4 1 5 
```
copy_ifという関数は、要素のうち条件を満たすものを取り出せます。
copy_whileという関数は、要素のうち条件を満たす間取り出せます。
copy_untilという関数は、要素のうち条件を満たさない間取り出せます。



### boost/algorithm/cxx11/copy_n.hpp

``` ex4.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/copy_n.hpp>
using namespace std;
using namespace boost::algorithm;

int main() {
  vector<int> v1 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
  vector<int> v1_copy6(6);
  auto i1 = v1_copy6.begin();
  i1 = copy_n(v1.begin(), 6, i1);
  for (auto i: v1_copy6)
    cout << i << ' ';
  cout << '\n';
  return 0;
}
```
```
3 1 4 1 5 9 
```
copy_nという関数は、配列の最初のn要素を取り出せます。



### boost/algorithm/cxx11/find_if_not.hpp

``` ex5.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/find_if_not.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n <= 5;
}

int main() {
  vector<int> v1 = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
  auto it = find_if_not(v1.begin(), v1.end(), p1);
  cout << *it << '\n';
  return 0;
}
```
```
9
```
find_if_notは、配列のうち、条件を満たさない最初の要素を探します。

### boost/algorithm/cxx11/iota.hpp

``` ex6.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/iota.hpp>
using namespace std;
using namespace boost::algorithm;

int main() {
  vector<int> v1(10);
  iota(v1, 2);
  for (int i: v1)
    cout << i << ' ';
  cout << '\n';

  vector<int> v2(10);
  iota_n(v2.begin(), 2, (size_t)6);
  for (int i: v2)
    cout << i << ' ';
  cout << '\n';
  return 0;
}
```
```
2 3 4 5 6 7 8 9 10 11 
2 3 4 5 6 7 0 0 0 0 
```
iotaは、最後の引数の数から1ずつ増やしていって配列に入れます。
iota_nは、iotaを配列の最初のn要素だけでやるという感じです。


### boost/algorithm/cxx11/is_partitioned.hpp
``` ex7.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/is_partitioned.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n % 2 == 1;
}

int main() {
  vector<int> v1 = {7, 3, 5, 1, 6, 4, 8, 2};
  bool b1 = is_partitioned(v1, p1);
  cout << (b1 ? "Yes" : "No") << '\n';
  return 0;
}
```
```
Yes
```
配列のある場所までは条件を満たし、それ以降はすべてその条件を満たさないかどうかを判定しています。



### boost/algorithm/cxx11/is_permutation.hpp

``` ex8.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/is_permutation.hpp>
using namespace std;
using namespace boost::algorithm;

int main() {
  vector<int> v1 = {3, 5, 2, 6, 4, 1};
  vector<int> v2 = {1, 4, 5, 3, 6, 2};
  vector<int> v3 = {4, 3, 5, 6, 1, 3};
  bool b1 = is_permutation(v1, v2.begin());
  cout << (b1 ? "Yes" : "No") << '\n';
  bool b2 = is_permutation(v1, v3.begin());
  cout << (b2 ? "Yes" : "No") << '\n';
  return 0;
}
```
```
Yes
No
```
配列が一方の並び替えでできるかどうかを判定しています。

### boost/algorithm/cxx11/is_sorted.hpp

``` ex9.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/is_sorted.hpp>
using namespace std;
using namespace boost::algorithm;

int main() {
  vector<int> v1 = {1, 3, 6, 7, 4, 9};
  cout << is_sorted_until(v1) - v1.begin() << '\n';

  vector<int> v2 = {1, 4, 7, 8, 9};
  cout << (is_sorted(v2) ? "Yes" : "No") << '\n';
  cout << (is_increasing(v2) ? "Yes" : "No") << '\n';
  cout << (is_strictly_increasing(v2) ? "Yes" : "No") << '\n';

  cout << '\n';

  vector<int> v3 = {1, 4, 7, 8, 8};
  cout << (is_sorted(v3) ? "Yes" : "No") << '\n';
  cout << (is_increasing(v3) ? "Yes" : "No") << '\n';
  cout << (is_strictly_increasing(v3) ? "Yes" : "No") << '\n';

  cout << '\n';

  vector<int> v4 = {1, 4, 7, 6, 9};
  cout << (is_sorted(v4) ? "Yes" : "No") << '\n';
  return 0;
}
```
```
4
Yes
Yes
Yes

Yes
Yes
No

No
```
is_sorted_untilは、ソートされている部分の最後を返すので、最初の何要素がソートされているかがわかります。
is_sortedは、配列全体のソート判定、is_increasingはis_sortedと同じ、is_strictly_increasingは同じ要素が並んでいる場合はだめです。

### boost/algorithm/cxx11/none_of.hpp
``` ex10.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/none_of.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n == 2;
}

bool p2(int n) {
  return n % 2 == 0;
}

int main() {
  vector<int> v1 = {1, 1, 1, 1, 1};
  bool b1 = none_of(v1, p1);
  cout << (b1 ? "Yes" : "No") << '\n';

  bool b1_same = none_of_equal(v1, 2);
  cout << (b1_same ? "Yes" : "No") << '\n';

  vector<int> v2 = {1, 1, 1, 1, 2};
  bool b2 = none_of(v2, p1);
  cout << (b2 ? "Yes" : "No") << '\n';

  bool b2_same = none_of_equal(v2, 2);
  cout << (b2_same ? "Yes" : "No") << '\n';

  vector<int> v3 = {1, 3, 5, 7, 9};
  bool b3 = none_of(v3, p2);
  cout << (b3 ? "Yes" : "No") << '\n';
  return 0;
}
```
```
Yes
Yes
No
No
Yes
```
none_ofは、配列の要素が全て条件を満たさないかどうかを判定しています。
none_of_equalも配列の要素が全て特定の値に等しくないかどうかを判定しています。


### boost/algorithm/cxx11/one_of.hpp

``` ex11.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/one_of.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n == 2;
}

bool p2(int n) {
  return n % 2 == 0;
}

int main() {
  vector<int> v1 = {1, 1, 1, 2, 2};
  bool b1 = one_of(v1, p1);
  cout << (b1 ? "Yes" : "No") << '\n';

  bool b1_same = one_of_equal(v1, 2);
  cout << (b1_same ? "Yes" : "No") << '\n';

  vector<int> v2 = {1, 1, 1, 1, 2};
  bool b2 = one_of(v2, p1);
  cout << (b2 ? "Yes" : "No") << '\n';

  bool b2_same = one_of_equal(v2, 2);
  cout << (b2_same ? "Yes" : "No") << '\n';

  vector<int> v3 = {1, 3, 5, 6, 8};
  bool b3 = one_of(v3, p2);
  cout << (b3 ? "Yes" : "No") << '\n';
  return 0;
}
```
```
No
No
Yes
Yes
No
```
one_ofは、配列の中に条件を満たすものが一つだけ入っているかどうかを判定します。
one_of_equalも同様です。

### boost/algorithm/cxx11/partition_copy.hpp

``` ex12.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/partition_copy.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n % 2 == 1;
}

int main() {
  vector<int> v1 = {7, 2, 6, 3, 4, 1, 5, 8};
  vector<int> t(8), f(8);
  auto i1 = t.begin(), i2 = f.begin();
  auto r = partition_copy(v1.begin(), v1.end(), i1, i2, p1);
  for (auto i = t.begin(); i < r.first; i++)
    cout << *i << ' ';
  cout << '\n';
  for (auto i = f.begin(); i < r.second; i++)
    cout << *i << ' ';
  cout << '\n';
  return 0;
}
```
```
7 3 1 5 
2 6 4 8 
```
partition_copyは条件を満たす要素と満たさない要素に分けます。

### boost/algorithm/cxx11/partition_point.hpp

``` ex13.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx11/partition_point.hpp>
using namespace std;
using namespace boost::algorithm;

bool p1(int n) {
  return n % 2 == 1;
}

int main() {
  vector<int> v1 = {7, 3, 1, 5, 3, 8, 6, 2};
  auto i = partition_point(v1.begin(), v1.end(), p1);
  cout << i - v1.begin() << '\n';
  return 0;
}
```
```
4
```
partition_pointは、配列の何番目の要素より前が全て条件を満たして、それ以降はすべて満たさないのか調べて返します。二分探索にも応用できます。

## boost/algorithm/cxx14

### boost/algorithm/cxx14/equal.hpp
``` ex14.cpp
#include <iostream>
#include <vector>
#include <boost/algorithm/cxx14/equal.hpp>
using namespace std;

bool p1(int n, int m) {
  return n % 2 == m % 2;
}

int main() {
  vector<int> v1 = {1, 2, 4, 7};
  vector<int> v2 = {5, 0, 8, 3};
  vector<int> v3 = {3, 4, 5, 6};
  cout << (equal(v1.begin(), v1.end(), v2.begin(), v2.end(), p1) ? "Yes" : "No") << '\n';
  cout << (equal(v1.begin(), v1.end(), v3.begin(), v3.end(), p1) ? "Yes" : "No") << '\n';
}
```
```
Yes
No
```
equalは、配列と配列の長さが等しく、同じインデックスの要素がともに条件を満たすか満たさないかとなるときにtrueを返します。

### boost/algorithm/cxx14/is_permutation.hpp
boost/algorithm/cxx11/is_permutation.hppと同じだと思う。