1. Reputeless

    Posted

    Reputeless
Changes in title
+競プロに便利な C++17 新機能まとめ
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,585 @@
+[AtCoder 言語アップデート](https://twitter.com/atcoder/status/1223141026707017728) で、C++17 対応コンパイラが使えるようになりました。やったー!
+この記事では、競技プログラミングに役立つ C++17 の新しい標準ライブラリ・言語機能を 15 個紹介します。
+サンプルコードは、AtCoder の GCC 9.2.1 システムで動作を確認しています。
+
+## C++17 標準ライブラリ機能
+
+### 1. 値を範囲内に収める `std::clamp(x, min, max)`
+
+値 `x` を、`min` 以上、`max` 以下に収めてくれる関数です。
+これまで `std::max(std::min(x, max), min)` と書いてたのが 1 つの関数で済みます。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ // 値を 0 以上 100 以下に収める
+ std::cout << std::clamp(50, 0, 100) << '\n';
+ std::cout << std::clamp(-50, 0, 100) << '\n';
+ std::cout << std::clamp(150, 0, 100) << '\n';
+}
+```
+
+出力
+
+```
+50
+0
+100
+```
+
+
+### 2. 要素の集合からランダムに N 個を取り出す `std::sample(first, last, out, n, g)`
+
+乱数ジェネレータ `g` を用いて、`[first, last)` の一連の要素から `n` 個を選択し、その結果を出力イテレータ `out` に書き込みます。配列や `std::vector`, `std::array`, `std::string` などで使用した場合、要素の順序は保持されます。計算量は `O(n)` です。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ const std::string in = "ABCDEFG";
+ const int N = 4;
+ std::string out;
+
+ // N 個ランダムに選択する
+ std::sample(in.begin(), in.end(), std::back_inserter(out), N, std::mt19937{std::random_device{}()});
+
+ std::cout << out << '\n';
+}
+```
+
+出力例
+
+```
+ACDG
+```
+
+
+### 3. 「無効値」を保持できる `std::optional<Type>`
+
+型 `Type` が「無効値」も保持できるようになります。
+サイズが 0 か 1 のいずれかである `std::vector<Type>` と考えるとわかりやすいです。
+
+有効値を保持しているかどうかは `operator bool` (`if` や `?:`) または `std::optional::has_value()` でチェックできます。`Type` 型の有効値を取り出すには `operator*` または `std::optional::value()` を使います。`Type` 型のメンバにアクセスするには `operator->` を使います。無効値を表す `std::nullopt` という定数があります。
+
+無効値を保持する状態で有効値を取り出そうとすると例外が発生するので、基本的にチェックは必要です。`std::optional::value_or(x)` は、有効値を保持している場合はその値を、保持していない場合は代わりに `x` を返します。
+
+`Type` 型または `Type` 型と比較可能な型の値との比較演算も定義されています。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::cout << std::boolalpha;
+
+ // デフォルトでは無効値
+ std::optional<int> oi;
+
+ // 有効値を与えることもできる
+ //std::optional<int> oi = 100;
+
+ if (oi)
+ { // 実行されない
+ std::cout << oi.value() << '\n';
+ }
+
+ std::cout << (oi == 200) << '\n'; // false
+
+ oi = 200; // 有効値を代入
+
+ if (oi)
+ { // 実行される
+ std::cout << oi.value() << '\n'; // 200
+ }
+
+ std::cout << (oi == 200) << '\n'; // true
+
+ // oi が無効値の場合引数の値を返す
+ std::cout << oi.value_or(999) << '\n'; // 200
+
+ oi = std::nullopt; // 無効値を表す値を代入
+
+ if (oi)
+ { // 実行されない
+ std::cout << oi.value() << '\n';
+ }
+
+ // oi が無効値の場合引数の値を返す
+ std::cout << oi.value_or(999) << '\n'; // 999
+}
+```
+
+出力
+
+```
+false
+200
+true
+200
+999
+```
+
+```C++
+#include <bits/stdc++.h>
+
+struct Point
+{
+ int x, y;
+};
+
+int main()
+{
+ std::optional<Point> op;
+
+ if (op)
+ { // 実行されない
+ std::cout << op->x << ',' << op->y << '\n';
+ }
+
+ op = Point{11, 22}; // 有効値を代入
+
+ if (op)
+ { // 実行される
+ std::cout << op->x << ',' << op->y << '\n'; // 11,22
+ }
+
+ op = std::nullopt; // 無効値を表す値を代入
+
+ if (op)
+ { // 実行されない
+ std::cout << op->x << ',' << op->y << '\n';
+ }
+}
+```
+
+出力
+
+```
+11,22
+```
+
+
+### 4. `tuple` を構築しやすくなった
+
+関数の戻り値で `std::tuple` を返すときに `{}` を使えるようになりました。
+
+```C++
+#include <bits/stdc++.h>
+
+std::tuple<int, int, std::string> GetTuple()
+{
+ // return std::make_tuple(20, 40, "ABC");
+ return{ 20, 40, "ABC" }; // C++17 ではこれで OK
+}
+
+int main()
+{
+ // 構造化束縛(本記事の「言語機能 1」を参照)
+ auto [a, b, c] = GetTuple();
+ std::cout << a << ',' << b << ',' << c << '\n';
+}
+```
+
+出力
+
+```
+20,40,ABC
+```
+
+
+### 5. `emplace_back()`, `emplace_front()` が、追加された要素への参照を返すように
+
+`std::vector` や `std::deque`, `std::list`, `std::queue` の `emplace_back()`, `empalce_front()` が、追加された要素への参照を返すよう仕様が変更されました。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::vector<std::pair<int, int>> v;
+
+ // v.emplace_back(11, 33)
+ // const auto p = v.back();
+
+ const auto p = v.emplace_back(11, 33); // C++17 はこれができる
+
+ std::cout << p.first << '\n'; // 11
+}
+```
+
+出力
+
+```
+11
+```
+
+
+### 6. `insert_or_assign(key, value)`
+
+`std::map` と `std::unordered_map` に `insert_or_assign(key, value)` メンバ関数が追加されました。`key` と同じキーを持つ要素が存在する場合は要素を代入し、存在しない場合は要素を追加します。戻り値の `std::pair<iterator, bool>` を調べると、要素が追加された場合は `second` が `true` になっているので、代入だった(すでに同じキーを持つ要素が存在した)のか追加だったのかがわかります。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::cout << std::boolalpha;
+
+ std::unordered_map<std::string, int> m;
+
+ std::cout << m.insert_or_assign("aaa", 5).second << '\n'; // 追加なので true
+
+ std::cout << m.insert_or_assign("aaa", 10).second << '\n'; // 代入なので false
+
+ std::cout << m["aaa"] << '\n';
+}
+```
+
+出力
+
+```
+true
+false
+10
+```
+
+
+### 7. 非メンバ関数の `std::data()`, `std::size()`, `std::empty()`
+
+各種コンテナや配列で一貫して使える、非メンバの `std::data()`, `std::size()`, `std::empty()` 関数が追加されました。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::cout << std::boolalpha;
+
+ int ar[10];
+ std::vector<int> v;
+
+ std::cout << std::size(ar) << '\n'; // 10
+ std::cout << std::size(v) << '\n'; // 0
+
+ std::cout << std::empty(ar) << '\n'; // false
+ std::cout << std::empty(v) << '\n'; // true
+}
+```
+
+出力
+
+```
+10
+0
+false
+true
+```
+
+
+### 8. 最大公約数 `std::gcd()` と最小公倍数 `std::lcm()`
+
+GCC には以前から `std::__gcd()` という内部関数があり、最大公約数を求めるときにこれを使うテクニックがありましたが、C++17 からは最大公約数と最小公倍数を求める関数が標準で実装されました。戻り値の型は 2 つの引数の型 `M`, `N` に対して `std::common_type_t<M, N>` なので、片方が `long long`, 片方が `int` でも大丈夫です。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ // C++17 以前のテクニック
+ // std::cout << std::__gcd(554433221100LL, 12345) << '\n'; // エラー
+ // std::cout << std::__gcd(554433221100LL, 12345LL) << '\n';
+
+ std::cout << std::gcd(554433221100LL, 12345) << '\n'; // 15
+
+ std::cout << std::lcm(554433221100LL, 12345) << '\n'; // 456298540965300
+}
+```
+
+出力
+
+```
+15
+456298540965300
+```
+
+
+### 9. 関数オブジェクトの戻り値の否定ラッパー `std::not_fn()`
+
+関数オブジェクトの結果の否定を返す関数オブジェクトを作る関数です。
+サンプルコードを見ればすぐわかります。
+
+```C++
+#include <bits/stdc++.h>
+
+bool LessThan10(int n)
+{
+ return n < 10;
+}
+
+int main()
+{
+ std::vector<int> v = { 3, 5, 7, 9, 11 };
+
+ std::cout << std::count_if(v.begin(), v.end(), LessThan10) << '\n'; // 4
+
+ std::cout << std::count_if(v.begin(), v.end(), std::not_fn(LessThan10)) << '\n'; // 1
+}
+```
+
+
+### 10. 文字列検索アルゴリズムとして「Boyer-Moore 法」「Boyer-Moore-Horspool 法」を使用できるように
+
+効率的な文字列検索アルゴリズムの一種である「Boyer-Moore 法」と「Boyer-Moore-Horspool 法」を使って、文字列検索ができるようになります。
+
+アルゴリズムの詳細: [Wikipedia: ボイヤー-ムーア文字列検索アルゴリズム](https://ja.wikipedia.org/wiki/%E3%83%9C%E3%82%A4%E3%83%A4%E3%83%BC-%E3%83%A0%E3%83%BC%E3%82%A2%E6%96%87%E5%AD%97%E5%88%97%E6%A4%9C%E7%B4%A2%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ const std::string in = "ATGGTTGGTTCGCTAAACTGCATCGTCGCTGTGTCCCAGAA";
+ const std::string pattern = "TGTGTCCCAG";
+ const std::boyer_moore_searcher searcher(pattern.begin(), pattern.end());
+
+ const auto it = std::search(in.begin(), in.end(), searcher);
+
+ if (it != in.end()) // 見つかった
+ {
+ std::cout << std::distance(in.begin(), it) << '\n'; // 29
+ }
+ else
+ {
+ std::cout << "not found\n";
+ }
+}
+```
+
+出力
+
+```
+29
+```
+
+
+### 11. 3 次元の `std::hypot(x, y, z)`
+
+2 次元のベクトルの長さを求める `std::hypot(x, y)` の 3 次元版のオーバーロード関数 `std::hypot(x, y, z)` が追加されました。
+
+```math
+\sqrt{x^2+y^2+z^2}
+```
+です。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::cout << std::hypot(0.0, 5.0, 0.0) << '\n';
+ std::cout << std::hypot(1.0, 1.0, 1.0) << '\n';
+ std::cout << std::hypot(2.0, 3.0, 5.0) << '\n';
+}
+```
+
+出力
+
+```
+5
+1.73205
+6.16441
+```
+
+
+## C++17 言語機能
+
+### 1. `std::pair` や `std::tuple`, 構造体などの要素を個々に取り出す構造化束縛
+
+`std::pair` や `std::tuple`, 構造体などの要素を個々に取り出すことができる言語機能です。
+
+```C++
+#include <bits/stdc++.h>
+
+std::tuple<int, double, std::string> GetTuple()
+{
+ return{ 123, 3.14, "Hello" };
+}
+
+int main()
+{
+ auto [min, max] = std::minmax({ 10, 50, 30, 20 }); // 戻り値 std::pair<int, int> を 2 つの変数に分解
+ std::cout << min << ',' << max << '\n'; // 10,50
+
+ auto [a, b, c] = GetTuple(); // tuple を 3 つの変数に分解
+ std::cout << a << ',' << b << ',' << c << '\n';
+
+ std::vector<std::pair<int, int>> v =
+ {
+ { 11, 22 },
+ { 33, 44 }
+ };
+ for (auto[x, y] : v) // pair を 2 つの変数に分解
+ {
+ std::cout << x << ',' << y << '\n';
+ }
+}
+```
+
+出力
+
+```
+10,50
+123,3.14,Hello
+11,22
+33,44
+```
+
+
+### 2. `if` で初期化式と条件式を分けられるように
+
+`if (初期化式; 条件式)` という文法が追加されました。
+条件式に使う変数のスコープを狭めたいときに便利です。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::unordered_map<std::string, int> m =
+ {
+ { "one", 1 },
+ { "five", 5 },
+ { "ten", 10 }
+ };
+
+ if (auto it = m.find("ten"); it != m.end())
+ {
+ std::cout << it->second << '\n';
+ }
+
+ // ここでまた it を使える
+ if (auto it = m.find("five"); it != m.end())
+ {
+ std::cout << it->second << '\n';
+ }
+}
+```
+
+出力
+
+```
+10
+5
+```
+
+
+### 3. `switch` で初期化式と条件式を分けられるように
+
+`switch (初期化式; 条件式)` という文法が追加されました。
+条件式に使う変数のスコープを狭めたいときに便利です。
+
+```C++
+#include <bits/stdc++.h>
+
+int main()
+{
+ std::unordered_map<std::string, int> m =
+ {
+ { "one", 1 },
+ { "five", 5 },
+ { "ten", 10 }
+ };
+
+ switch (auto it = m.find("two"); (it != m.end()) ? it->second : -1)
+ {
+ case 0:
+ std::cout << "case 0\n";
+ break;
+ case 5:
+ std::cout << "case 5\n";
+ break;
+ case 10:
+ std::cout << "case 10\n";
+ break;
+ default:
+ std::cout << "default\n";
+ break;
+ }
+
+ // ここでまた it を使える
+ if (auto it = m.find("five"); it != m.end())
+ {
+ std::cout << it->second << '\n';
+ }
+}
+```
+
+出力
+
+```
+default
+5
+```
+
+
+### 4. 戻り値の使い忘れを警告する `[[nodiscard]]` 属性
+
+戻り値を捨ててはいけない関数に `[[nodiscard]]` 属性を付けると、誤ってその関数の戻り値を無視したコードをコンパイルした際、コンパイラが警告メッセージを出してくれます。自作関数の誤用防止ができます。AtCoder システムでは、提出ページの「コンパイルエラー」欄にメッセージが表示されます。
+
+```C++
+#include <bits/stdc++.h>
+
+[[nodiscard]] int Increment(int n) // 戻り値を無視したら意味が無い関数
+{
+ return n + 1;
+}
+
+int main()
+{
+ int x = 0;
+
+ // 戻り値を誤って無視!
+ Increment(x);
+
+ std::cout << x << '\n';
+}
+```
+
+出力
+
+```
+0
+```
+
+コンパイラメッセージの例
+
+```
+./Main.cpp: In function 'int main()':
+./Main.cpp:13:14: warning: ignoring return value of 'int Increment(int)', declared with attribute nodiscard [-Wunused-result]
+ 13 | Increment(x);
+ | ~~~~~~~~~^~~
+./Main.cpp:3:19: note: declared here
+ 3 | [[nodiscard]] int Increment(int n)
+ | ^~~~~~~~~
+```
+
+
+## C++17 を学ぶための参考資料
+
+### Web
+- https://cpprefjp.github.io/lang/cpp17.html
+- https://ja.cppreference.com/w/cpp
+
+### 書籍リスト
+- https://cppmap.github.io/learn/books/
+
+
+## まとめ
+便利な機能が増えましたが、競技プログラミングの C++ コードが抜本的に変わるほどではない感じです。
+それでも、来たる C++20 や C++23 に備えるためにも、アップデートは随時追っていたほうが良いでしょう。
+記事で紹介したほかに、こういう C++17 機能が便利かも / 競プロらしい良いサンプルコードを思いついたよ、という方はコメントでお知らせください。
+
+