AtCoder の言語アップデート で、C++17 対応コンパイラが使えるようになりました。やったー！
この記事では、競技プログラミングに役立つ C++17 の新しい標準ライブラリ・言語機能を 16 個紹介します。
サンプルコードは、AtCoder の GCC 9.2.1 システムで動作を確認しています。
C++17 標準ライブラリ機能
1. 値を範囲内に収める std::clamp(x, min, max)
値 x を、min 以上、max 以下に収めてくれる関数です。
これまで std::max(std::min(x, max), min) と書いてたのが 1 つの関数で済みます。
#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) です。
#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 型と比較可能な型の値との比較演算も定義されています。
#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
#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 を返すときに {} を使えるようになりました。
#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() が、追加された要素への参照を返すよう仕様が変更されました。
#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 になっているので、代入だった（すでに同じキーを持つ要素が存在した）のか挿入だったのかがわかります。
操作としては operator[] による追加・挿入と同じですが、より多くの情報を返すのが特長です。
#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() 関数が追加されました。
#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 でも大丈夫です。
#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()
関数オブジェクトの結果の否定を返す関数オブジェクトを作る関数です。
サンプルコードを見ればすぐわかります。
#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: ボイヤー-ムーア文字列検索アルゴリズム
#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) が追加されました。
\sqrt{x^2+y^2+z^2}
です。
#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
12. 別の連想コンテナから要素を抽出・マージする merge() メンバ関数
std::set, std::map, std::unorderd_map, std::unordered_set などの連想コンテナクラスに、別の連想コンテナクラスから要素の抽出とマージを行う merge(source) メンバ関数が追加されました。連想コンテナ source から、自身に存在しないキーを持つ要素を抜き出し、自身にマージします。
#include <bits/stdc++.h>
int main()
{
std::unordered_set<int> s1 = { 10, 8, 5, 4 };
std::unordered_set<int> s2 = { 10, 6, 4, 2 };
// s2 から s1 への抽出とマージ
s1.merge(s2);
std::cout << "s1: ";
for (const auto& e : s1)
{
std::cout << e << ' ';
}
std::cout << "\ns2: ";
for (const auto& e : s2)
{
std::cout << e << ' '; // 4 と 10 は s1 に存在したので抽出されない
}
}
出力例
s1: 6 2 10 5 8 4
s2: 4 10
#include <bits/stdc++.h>
int main()
{
std::unordered_map<std::string, int> m1 =
{
{ "one", 1 },
{ "five", 5 },
{ "ten", 10 }
};
std::unordered_map<std::string, int> m2 =
{
{ "one", 1 },
{ "two", 2 },
{ "three", 3 }
};
// m2 から m1 への抽出とマージ
m1.merge(m2);
std::cout << "m1: ";
for (auto[key, value] : m1) // [] は構造化束縛（本記事の「言語機能 1」を参照）
{
std::cout << key << '=' << value << ' ';
}
std::cout << "\nm2: ";
for (auto [key, value] : m2)
{
std::cout << key << '=' << value << ' ';
}
}
出力例
m1: two=2 three=3 one=1 five=5 ten=10
m2: one=1
C++17 言語機能
1. std::pair や std::tuple, 構造体などの要素を個々に取り出す構造化束縛
std::pair や std::tuple, 構造体などの要素を個々に取り出すことができる言語機能です。
#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 (初期化式; 条件式) という文法が追加されました。
条件式に使う変数のスコープを狭めたいときに便利です。
#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 (初期化式; 条件式) という文法が追加されました。
条件式に使う変数のスコープを狭めたいときに便利です。
#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 システムでは、提出ページの「コンパイルエラー」欄にメッセージが表示されます。
#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
書籍リスト
C++20
競プロに役立つ C++20 機能を知りたい場合は下記の記事が参考になります。
まとめ
便利な機能が増えましたが、競技プログラミングの C++ コードが抜本的に変わるほどではない感じです。
それでも、来たる C++20 や C++23 に備えるためにも、アップデートは随時追っていたほうが良いでしょう。
記事で紹介したほかに、こういう C++17 機能が便利かも / 競プロらしい良いサンプルコードを思いついたよ、という方はコメントでお知らせください。