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と同じだと思う。