はじめに
この記事は，C++初心者だけど競技プログラミングでC++を使っている，C++で競技プログラミングをやってみようと思っている人に向けた記事である．
「C++初心者」対象であって，プログラミングそのものが初心者である人向けではないかもしれない．
なるべくC++11で可能な範囲で記述している．
（最近の各種ジャッジサーバーではC++14も使えるからあんまりC++11にこだわる必要もないのだが一応）
なお，この記事は気が向いたきに不定期に更新される可能性が高い．
using namespace std;
競技プログラミングではタイプ量を少なくするために，using namespace std; というおまじないを書き，std:: を書かなくてもよいようにする．
#include <iostream>
using namespace std;
int
main()
{
cout << 42 << endl;
return 0;
}
しかし，一般的なC++では using namespace std; を使用してはならない．
というのも，std 名前空間には多数の関数が定義されているからである．
また， using namespace std; の有無で実行結果が異なるプログラムもある．
一番単純な例は以下のようなものだろう．
#include <cstdio>
using namespace std;
int
main()
{
cout << abs(-3.14) << endl;
return 0;
}
#include <cstdio>
using namespace std;
int
main()
{
std::cout << abs(-3.14) << "\n";
return 0;
}
また，C++17からは std::gcd(), std::lcm() が <numeric> に加わる．
なので，using namespace std; をした上で，自前で gcd(), lcm() を用意している場合，C++17ではコンパイルエラーになるので，将来的には気をつける必要がある．
もっとも，コンパイラはgcc派の人は，<algorithm> にある std::__gcd() と std::__lcm() という関数があるので，そちらを利用してきたかもしれないが．
std::cout, std::cin の高速化
以下の2行は std::cout, std::cin を高速化するおまじないとして知られている．
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
これらはそれぞれ以下の効果がある．
| 関数呼び出し |
効果 |
std::cin.tie(0); |
std::cout と std::cin の結びつきを解除する |
std::ios::sync_with_stdio(false); |
<cstdio> の std::printf() 等のC言語標準入出力関数との同期を切る |
これらをmain関数の一番初めに書くのもよいし，以下のようにグローバル変数のコンストラクタがmain関数より先に呼び出されることを利用するのもよい．
std::ios::sync_with_stdio(false); を用いた場合，std::printf() や std::scanf() 等の関数と std::cout, std::cin を併用してはならない．
仮に用いた場合，プログラムに記述した通りの出力順序とならなくなる．
（明示的にflushすれば回避可能ではあるが，事故を起こしやすいと思われる）
struct InitCppIo
{
InitCppIo() noexcept
{
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
}
} initCppIo;
std::endl
std::endl はよく「改行」であると勘違いされるが，正しくは「改行とフラッシュ」である．
「フラッシュ」が発生するということは，writeシステムコールが呼び出され，バッファから実際の出力が行われる．
そのため，頻繁に std::endl の呼び出しを行うと，実行速度に多少の影響が出る．
文字列のフラッシュはプログラム終了時にも行われるので，競技プログラミングにおいては，"\n" の出力で充分だと思われる．
ただし，プログラム自体がSEGVで落ちる場合はフラッシュが行われないことがあるので，std::endl あるいは std::flush 等でフラッシュした方がよいこともある．
#include <bits/stdc++.h>
どの関数がどのヘッダで宣言・定義されているかを考えるのは手間であるため，一行で全標準ライブラリをインクルードする競プロテンプレートを見ることがある．
#include <bits/stdc++.h>
確かにこれは楽でよい．
ただ，全ヘッダのインクルードを行う分，コンパイルに時間がかかるようになる（1秒以上の時間が必要になる）．
そこで，<bits/stdc++.h> を作っておくと，コンパイル時間が1/3程度になり，快適になる．
システムの <bits/stdc++.h> を探し出し，同じディレクトリにプリコンパイル済みヘッダを作ってもよいが，環境を汚すのはお行儀が悪い．
そこで，プリコンパイル済みヘッダ保存用のディレクトリを作成し，そこに環境変数を用いてインクルードパスを通すようにする．
まず，プリコンパイル済みヘッダ保存用のディレクトリを ~/.cache/cxxpch/ とする．
以下のシェルスクリプトを任意のディレクトリで実行すると，~/.cache/cxxpch/ 以下にプリコンパイル済みヘッダが作成される．
pch_dir='~/.cache/cxxpch/'
header_file='bits/stdc++.h'
header_dir=`dirname "$header_file"`
[ ! -d "$pch_dir" ] && mkdir -p "$pch_dir" || :
[ ! -d "$header_dir" ] && mkdir -p "$header_dir" || :
echo "#include <$header_file>" > "$header_file" \
&& g++ -x c++-header "$header_file" -o "$pch_dir/$header_file" \
&& rm "$header_file"
あとは，以下のような環境変数設定を ~/.bash_profile や ~/.zprofile などに書いておくとよい．
if [ "$CPLUS_INCLUDE_PATH" = '' ]; then
export CPLUS_INCLUDE_PATH=~/.cache/cxxpch/
else
export CPLUS_INCLUDE_PATH=$CPLUS_INCLUDE_PATH:~/.cache/cxxpch/
fi
これで，次回のシェル起動以降は ~/.cache/cxxpch/ のプリコンパイル済みヘッダが参照されるようになり，<bits/stdc++.h> のインクルード時間が劇的に短くなる．
なお， <bits/stdc++.h> はgcc独自のもので，clangでは使えない．なので，以下のように1つ1つインクルードする競プロテンプレートを用意しておいた方が便利なこともある．
以下は標準ライブラリヘッダの羅列である．
ただし，明らかに競プロに使わないであろうものはコメントアウトしてある．
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <cfenv>
#include <cinttypes>
#include <cstdint>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <forward_list>
#include <initializer_list>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
for (auto&& e : hoge) と for (const auto& e : hoge)
C++11からは，Range-based forという他の言語で言うところのforeachが使えるようになった．
基本的には，for (auto&& e : hoge) か for (const auto& e : hoge) のどちらかを利用する．
auto&& の方はループ内で要素を変更するときに，const auto& はループ内で要素を変更しないときに用いる．
ただし，ループ内で要素を変更しない場合に auto&& を使用したとしても，cons auto& の場合と生成されるコードは変わらないので，
- タイプ量少なめに，高速にコードを書きたい場合は
auto&& オンリー
- 事故を防止したい，丁寧なコードを書きたい場合は
const auto& も
とするとよいだろう．
なお，for (auto e : hoge) とした場合は，1つ1つの要素のコピーが発生するので，基本的に用いることはない．
また，for (auto& e : hoge) に触れていないのは，hoge の各要素が左辺値である必要があるからだ．
例えば，悪名高き std::vector<bool> の各要素は右辺値なので，for (auto& e : hoge) はコンパイルエラーとなる．
for (auto&& e : hoge) と for (const auto& e : hoge) であれば，どちらも左辺値と右辺値をとることができるので，このような問題は発生しない．
std::vector への読み込み
競技プログラミングでは，要素数 \( N \) が与えられて，次に \( N \) 個の要素を読み取るみたいなパターンがよくある．
このときの読み込み方として，
int n;
std::cin >> n;
std::vector<int> v(n);
for (auto&& e : v) {
std::cin >> e;
}
int n;
std::cin >> n;
std::vector<int> v(n);
for (int i = 0; i < n; i++) {
std::cin >> v[i];
}
int n;
std::cin >> n;
std::vector<int> v;
for (int i = 0; i < n; i++) {
int e;
std::cin >> e;
v.push_back(e);
}
という3つが考えられるが，タイプ量，実行効率から考えて1番目のものがベストだと思う．
push_back() を用いる3番目の手法は，あらかじめ reserve() 関数を呼び出しておかないと，メモリの再確保が何回か発生するので，方法として良いとはいえない．
STLコンテナをそのまま std::cout に渡したい
std::ostream と STLコンテナ間の operator<< のオーバーロードを用意すればよい．
ただし，全STLコンテナに対してオーバーロードを用意するのはしんどいので，テンプレートでまとめる．
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>
#include <type_traits>
struct is_container_impl
{
template<typename T>
static auto
check(T&& obj) -> decltype(obj.begin(), obj.end(), obj.empty(), std::true_type{});
template<typename T>
static auto
check(...) -> std::false_type;
};
template<typename T>
class is_container :
public decltype(is_container_impl::check<T>(std::declval<T>())){};
template<
typename T,
std::size_t N,
typename std::enable_if<!std::is_same<T, char>::value && !std::is_same<T, wchar_t>::value, std::nullptr_t>::type = nullptr
>
std::ostream&
operator<<(std::ostream& os, const T (&array)[N]) noexcept
{
os << "[";
std::copy(
std::begin(array),
std::prev(std::end(array)),
std::ostream_iterator<const T&>{os, ", "});
std::cout << *std::prev(std::end(array));
return os << "]";
}
template<
typename C,
typename std::enable_if<is_container<C>::value && !std::is_same<C, std::string>::value && !std::is_same<C, std::wstring>::value, std::nullptr_t>::type = nullptr
>
std::ostream&
operator<<(std::ostream& os, const C& container) noexcept
{
os << "[";
if (!container.empty()) {
std::copy(
std::begin(container),
std::prev(std::end(container)),
std::ostream_iterator<const typename std::remove_reference<C>::type::value_type&>{os, ", "});
std::cout << *std::prev(std::end(container));
}
return os << "]";
}
template<
typename T,
typename U
>
std::ostream&
operator<<(std::ostream& os, const std::pair<T, U>& p) noexcept
{
return os << "(" << p.first << ", " << p.second << ")";
}
組み込み配列用のオーバーロードは別途用意し，要素型が char のときはオーバーロード候補から外れるようにしておかないと， std::cout << "hoge" としたときに，候補が複数あることになりコンパイルエラーとなる．
同様の理由で，STLコンテナ版に対しても， std::string, std::wstring のときはオーバーロード候補にならないようにする必要がある．
なお，特定の区切り文字を入れて要素を出力する方法については，この記事に書いた．
repマクロ
競技プログラミングにおけるC++では簡単にループを書くためにrepマクロを定義することがある．
decltype() で型を持ってくるようにすると，符号付きと符号無しの比較のワーニングを解決できる．
#define REP(var, n) for (decltype(n) var = 0; var < (n); var++)
#define RREP(var, n) for (auto var = n - 1; var != static_cast<decltype(var)>(-1); var--)
#define FOR(var, a, b) for (auto var = (a); var < (b); var++)
#define RFOR(var, a, b) for (auto var = b - 1; var != a; var--)
repマクロの代替
repマクロはマクロというC++的にはあまり好まれないものが用いられているため，非競技プログラマには嫌われやすい．
そこで代替の実装を考えてみることにする．
個人的にはrepマクロは必要悪だとは思う．
Range-based forで
Python2の xrange(), Python3の range() 相当のものをRange-based forで用いることを考えてみる．
自前で実装するなら以下のようにするとよいだろう．
#include <type_traits>
#include <utility>
template<typename Iterator>
class Range
{
public:
Range(Iterator&& begin, Iterator&& end) noexcept
: m_begin(std::forward<Iterator>(begin))
, m_end(std::forward<Iterator>(end))
{}
Iterator
begin() const noexcept
{
return m_begin;
}
Iterator
end() const noexcept
{
return m_end;
}
private:
const Iterator m_begin;
const Iterator m_end;
};
template<typename Iterator>
static inline Range<Iterator>
makeRange(Iterator&& begin, Iterator&& end) noexcept
{
return Range<Iterator>{std::forward<Iterator>(begin), std::forward<Iterator>(end)};
}
template<typename T>
class IntegerIterator
{
static_assert(std::is_integral<T>::value, "[IntegerIterator] Element type must be integer");
public:
using difference_type = T;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = std::random_access_iterator_tag;
template<typename U>
IntegerIterator(U value) noexcept
: m_value(value)
{
static_assert(std::is_integral<U>::value, "[IntegerIterator::ctor] The argument must be an integer");
}
T&
operator*() const noexcept
{
return m_value;
}
bool
operator!=(const IntegerIterator& rhs) const noexcept
{
return m_value != rhs.m_value;
}
IntegerIterator&
operator++() noexcept
{
m_value++;
return *this;
}
private:
T m_value;
T m_step;
};
template<typename T>
static inline Range<IntegerIterator<T>>
makeIntegerRange(const T& n) noexcept
{
static_assert(std::is_integral<T>::value, "[makeIntegerRange] The argument must be an integer");
return makeRange(IntegerIterator<T>{0}, IntegerIterator<T>{n});
}
template<
typename T,
typename U,
typename C = typename std::common_type<T, U>::type
>
static inline Range<IntegerIterator<C>>
makeIntegerRange(const T& a, const U& b) noexcept
{
static_assert(std::is_integral<T>::value, "[makeIntegerRange] The 1st argument must be an integer");
static_assert(std::is_integral<T>::value, "[makeIntegerRange] The 2nd argument must be an integer");
return makeRange(IntegerIterator<C>{a}, IntegerIterator<C>{b});
}
template<typename T>
class ReversedIntegerIterator
{
static_assert(std::is_integral<T>::value, "[IntegerIterator] Element type must be integer");
public:
template<typename U>
explicit ReversedIntegerIterator(U value) noexcept
: m_value(value)
{
static_assert(std::is_integral<U>::value, "[IntegerIterator::ctor] The argument must be an integer");
}
T
operator*() const noexcept
{
return m_value;
}
bool
operator!=(const ReversedIntegerIterator& rhs) const noexcept
{
return m_value != rhs.m_value;
}
ReversedIntegerIterator&
operator++() noexcept
{
m_value--;
return *this;
}
private:
T m_value;
};
template<typename T>
static inline Range<ReversedIntegerIterator<T>>
makeReversedIntegerRange(const T& n) noexcept
{
static_assert(std::is_integral<T>::value, "[makeReversedIntegerRange] The argument must be an integer");
return makeRange(ReversedIntegerIterator<T>{n}, ReversedIntegerIterator<T>{0});
}
template<
typename T,
typename U,
typename C = typename std::common_type<T, U>::type
>
static inline Range<ReversedIntegerIterator<C>>
makeReversedIntegerRange(const T& a, const U& b) noexcept
{
static_assert(std::is_integral<T>::value, "[makeReversedIntegerRange] The 1st argument must be an integer");
static_assert(std::is_integral<T>::value, "[makeReversedIntegerRange] The 2nd argument must be an integer");
return makeRange(ReversedIntegerIterator<C>{a}, ReversedIntegerIterator<C>{b});
}
#include <iostream>
int
main()
{
for (const auto& e : makeIntegerRange(10)) {
std::cout << e << " ";
}
std::cout << "\n";
for (const auto& e : makeIntegerRange(10, 20)) {
std::cout << e << " ";
}
std::cout << "\n";
for (const auto& e : makeReversedIntegerRange(10)) {
std::cout << e << " ";
}
std::cout << "\n";
for (const auto& e : makeReversedIntegerRange(10u, 0u)) {
std::cout << e << " ";
}
std::cout << "\n";
return 0;
}
テンプレートに入れるにしても長すぎる...．
Boost.Range と Range-based forで
Boostライブラリという準標準ライブラリもいえる超強力なC++のライブラリにも同等のものが用意されている．
AtCoderではBoostライブラリが使用可能なので，以下のように書くことができる．
#include <iostream>
#include <boost/range/irange.hpp>
int
main()
{
for (const auto& e : boost::irange(10, 20)) {
std::cout << e << " ";
}
std::cout << "\n";
for (const auto& e : boost::irange(20, 10, -1)) {
std::cout << e << " ";
}
std::cout << "\n";
return 0;
}
数値型の最大値と最小値
int 等の数値型の最大値，最小値はC言語ライブラリヘッダの <climits> で， INT_MAX，INT_MIN 等のマクロで定義されている．
std::cout << "char min:" << CHAR_MIN << "\n";
std::cout << "char max:" << CHAR_MAX << "\n";
std::cout << "short min:" << SHRT_MIN << "\n";
std::cout << "short max:" << SHRT_MAX << "\n";
std::cout << "int min:" << INT_MIN << "\n";
std::cout << "int max:" << INT_MAX << "\n";
std::cout << "long min:" << LONG_MIN << "\n";
std::cout << "long max:" << LONG_MAX << "\n";
std::cout << "long long min:" << LLONG_MIN << "\n";
std::cout << "long long max:" << LLONG_MAX << "\n";
std::cout << "unsigned char min:" << 0 << "\n";
std::cout << "unsigned char max:" << UCHAR_MAX << "\n";
std::cout << "unsigned short min:" << 0 << "\n";
std::cout << "unsigned short max:" << USHRT_MAX << "\n";
std::cout << "unsigned int min:" << 0 << "\n";
std::cout << "unsigned int max:" << UINT_MAX << "\n";
std::cout << "unsigned long min:" << 0 << "\n";
std::cout << "unsigned long max:" << ULONG_MAX << "\n";
std::cout << "unsigned long long min:" << 0 << "\n";
std::cout << "unsigned long long max:" << ULLONG_MAX << "\n";
しかし，C++的には <limits> で定義されている std::numeric_limits クラスから取得するのがよい．
std::cout << "char min:" << std::numeric_limits<char>::min() << "\n";
std::cout << "char max:" << std::numeric_limits<char>::max() << "\n";
std::cout << "short min:" << std::numeric_limits<short>::min() << "\n";
std::cout << "short max:" << std::numeric_limits<short>::max() << "\n";
std::cout << "int min:" << std::numeric_limits<int>::min() << "\n";
std::cout << "int max:" << std::numeric_limits<int>::max() << "\n";
std::cout << "long min:" << std::numeric_limits<long>::min() << "\n";
std::cout << "long max:" << std::numeric_limits<long>::max() << "\n";
std::cout << "long long min:" << std::numeric_limits<long long>::min()<< "\n";
std::cout << "long long max:" << std::numeric_limits<long long>::max()<< "\n";
std::cout << "unsigned char min:" << std::numeric_limits<unsigned char>::min() << "\n";
std::cout << "unsigned char max:" << std::numeric_limits<unsigned char>::max() << "\n";
std::cout << "unsigned short min:" << std::numeric_limits<unsigned short>::min() << "\n";
std::cout << "unsigned short max:" << std::numeric_limits<unsigned short>::max() << "\n";
std::cout << "unsigned int min:" << std::numeric_limits<unsigned int>::min() << "\n";
std::cout << "unsigned int max:" << std::numeric_limits<unsigned int>::max() << "\n";
std::cout << "unsigned long min:" << std::numeric_limits<unsigned long>::min() << "\n";
std::cout << "unsigned long max:" << std::numeric_limits<unsigned long>::max() << "\n";
std::cout << "unsigned long long min:" << std::numeric_limits<unsigned long long>::min() << "\n";
std::cout << "unsigned long long max:" << std::numeric_limits<unsigned long long>::max() << "\n";
タイプ数が多いところが欠点ではあるが...．
<algorithm>
<algorithm> は配列やSTLコンテナ等の集合強力なアルゴリズムを提供してくれる標準ライブラリである．
使いこなせば，合計値を求めたり，条件を満たす要素の数を求めるといった処理を自分で書かなくて済む．
begin(), end()
<algorithm> は集合を指定する方法として，開始位置，終了位置の2組のイテレータを渡す．
これにより，集合の一部のみをソートするといった柔軟な処理が可能になるのだが，日常生活の中では集合全体を指定するパターンが多い．
集合の開始位置を得る関数として，begin() と end() がある．
STLコンテナは基本的に begin() と end() をメンバ関数に持つ．
なのに，std::begin() と std::end() というフリー関数版もある．
これらはどう使い分けるべきなのだろうか？
std::vector<int> v{1, 3, 5, 6, 4, 2};
std::sort(v.begin(), v.end());
std::sort(std::begin(v), std::end(v));
フリー関数の std::begin() と std::end() はC++11で追加されたものであり，C++11以降では基本的にフリー関数版を利用するとよい．
フリー関数版の意義は，組み込み配列からもイテレータを取得できる点であり，これにより組み込み配列，STLコンテナという差を吸収して統一的な記述ができる．
template<
typename T,
std::size_t N
>
static inline constexpr std::size_t
length(T (&)[N]) noexcept
{
return N;
}
int arr[] = {1, 3, 5, 6, 4, 2};
std::sort(arr.begin(), arr.end());
std::sort(arr, arr + length(arr));
std::sort(std::begin(arr), std::end(arr));
rbegin(), rend()
rbegin(), rend() メンバ関数，フリー関数は集合を逆順に走査するリバースイテレータの開始位置および終了位置を取得する．
begin() と end() と比較すると，利用頻度は少なめになるが，うまく使える場面もある．
例えば，降順ソートを行うとき，
std::array<int, 6> arr{{1, 3, 5, 6, 4, 2}}
std::sort(std::begin(arr), std::end(arr), std::greater<decltype(arr)::value_type>());
と書く例があるが，
std::array<int, 6> arr{{1, 3, 5, 6, 4, 2}}
std::sort(std::rbegin(arr), std::rend(arr));
のように，std::greater が不要になる．
残念なことに，フリー関数版の rbegin(), rend() はC++11では提供されておらず，C++14から標準ライブラリ入りしたので，C++11では以下のようにメンバ関数を呼び出すように書くしかないし，
std::array<int, 6> arr{{1, 3, 5, 6, 4, 2}}
std::sort(arr.rbegin(), arr.rend());
組み込み配列はやはり，std::greater が必要になる．
int arr[] = {1, 3, 5, 6, 4, 2};
std::sort(std::begin(arr), std::end(arr), std::greater<decltype(arr[0])>{});
第三引数に std::greater と同等のラムダを与える手もあるが， std::greater の方がタイプ数が少なく，お手軽である．
int arr[] = {1, 3, 5, 6, 4, 2};
std::sort(
std::begin(arr),
std::end(arr),
[](const decltype(arr[0])& x, const decltype(arr[0])& y){
return x > y;
});
cbegin(), cend(), crbegin(), crend()
cbegin(), cend(), crbegin(), crend() はそれぞれ，begin(), end(), rbegin(), rend() のconstイテレータを返却する版のメンバ関数，フリー関数である．
ただし，例によってフリー関数版の cbegin(), cend(), crbegin(), crend() はC++11では提供されていない．
ALL マクロ
begin() end() を書くのは面倒なので，競技プログラミングでは以下のマクロを見かけることがある．
#define ALL(c) std::begin(c), std::end(c)
このマクロを用いると，
int arr[] = {1, 3, 5, 6, 4, 2};
std::sort(ALL(arr));
のように記述が多少楽になる．
ただし，式を返すようなマクロではないので，通常のC++を書く人には嫌われがちである．
std::all_of(), std::none_of(), std::any_of()
それぞれ以下の表の通り．
| 関数 |
機能 |
std::all_of() |
要素全てが指定した条件を満たせば true，そうでなければ false |
std::none_of() |
要素全てが指定した条件を満たさなければ false そうでなければ true |
std::any_of() |
要素のどれか1つでも条件を満たせば true，そうでなければ false |
これらの関数は他の言語でも存在する関数なので，特に使い方に問題はないだろう．
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};
auto ret1 = std::all_of(
std::begin(v),
std::end(v),
[](const decltype(v)::value_type& e){
return e % 2 == 0;
});
auto ret2 = std::none_of(
std::begin(v),
std::end(v),
[](const decltype(v)::value_type& e){
return e < 0;
});
auto ret2 = std::any_of(
std::begin(v),
std::end(v),
[](const decltype(v)::value_type& e){
return e % 3 == 0;
});
std::min(), std::max(), std::minmax()
与えた2数のうちから，最小値，最大値を得る．
auto minValue = std::min(0, 10);
auto maxValue = std::max(0, 10);
auto mmPair = std::max(0, 10);
実は，3つ以上でもいける．これは std::initialize_list を取るオーバーロードがあるためである．
auto minValue = std::min({3, 1, 4, 1, 5, 9, 2, 6, 5});
auto maxValue = std::max({1, 1, 4, 5, 1, 4});
auto mmPair = std::minmax({2, 7, 1, 8, 2, 8, 1, 8});
最小値，最大値の更新で次のように書くことはよくある．
minValue = std::min(minValue, value);
maxValue = std::max(maxValue, value);
これは（最適化を無効化していない限り）以下のコードのコンパイル結果と同じになる（つまり速度面は気にしなくてよい）．
if (value < minValue) {
minValue = value;
}
if (value > maxValue) {
maxValue = value;
}
std::min_element, std::max_element(), std::minmax_element(): 最小値，最大値
STLコンテナから最小値，最大値を取るイテレータを取得する．
std::sort(), std::stable_sort(): ソートする
std::sort() は非安定ソートであるが， std::stable_sort() は安定ソートである．
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5};
std::sort(std::begin(v), std::end(v));
int a[] = {5, 3, 4, 2, 1};
std::sort(std::begin(v), std::end(v));
降順にするには以下の2つのうち，好きな方を利用するとよい．
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5};
std::sort(std::begin(v), std::end(v), std::greater<decltype(v)::value_type>{});
std::sort(std::rbegin(v), std::rend(v), std::greater<decltype(v)::value_type>{});
std::array<int, 5> a{{5, 3, 7, 8, 1}};
std::sort(arr, arr + (sizeof(a) / sizeof(a[0])), std::greater<decltype(a[0])>{});
int arr[] = {5, 3, 4, 2, 1};
std::sort(arr, arr + (sizeof(a) / sizeof(a[0])), std::greater<decltype(a[0])>{});
第三引数に比較関数を指定することができる．
以下は第三引数に比較関数を指定しているが，何も指定しない場合と同等の処理である．
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5};
std::sort(
std::begin(v),
std::end(v),
[](const decltype(v)::value_type& x, const decltype(v)::value_type& y){
return x < y;
});
第三引数の意義は，比較演算子が定義されていないインスタンスの大小比較や，std::pair や std::tuple 等，複数要素を持つものの大小関係をカスタマイズできる点にある．
std::fill(), std::fill_n(): 指定した値で埋める
STLコンテナや配列などを指定した値で埋める．
ローカル変数の std::array 等の初期化に用いることが多い．
（std::array は通常の配列同様，グローバル変数やstatic変数でない限り，不定値が入っている）
std::array<int, 100> arr;
std::fill(std::begin(arr), std::end(arr), 0);
std::fill_n は指定した個数だけ指定した値で埋める．
基本的にポインタ引数を与えて用いる．
static constexpr int INF = 0x3f3f3f3f;
std::fill_n(p, 10, INF);
std::count(), std::count_if(): 指定した要素，条件と等しい要素数を返す
std::count() は指定した要素と等しい要素の数を数える．
例えば，std::string の中に含まれる文字数 'z' の数を数えるには，
std::string s{"FizzBuzz"};
auto cnt = std::count(std::begin(s), std::end(s), 'z');
とすればよい．
また，std::vector<int> に含まれる2の倍数の数を数えるには，
std::vector v{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0}
auto cnt = std::count_if(
std::begin(v),
std::end(v),
[](const decltype(v)::value_type& e){
return e % 2 == 0;
});
とするとよい．
std::find(), std::find_if(): 指定した値を探す
std::reverse(): 要素の反転
std::reverse() は集合の要素の並びを反転させる．
std::vector v{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
std::reverse(std::begin(v), std::end(v));
std::sort() と組み合わせると，降順ソートもできるが，別の方法を採った方がよいだろう．
std::vector v{1, 3, 5, 7, 8, 6, 4, 2};
std::sort(std::begin(v), std::end(v));
std::reverse(std::begin(v), std::end(v));
std::rotate(): 要素の転回
std::reverse() は要素の左方向への転回を行う．
第1引数に左端とするイテレータ，第2引数に転回範囲，第3引数に右端の1つ右のイテレータを与える．
以下のコードで動作が掴めるだろう．
std::vector<int> v(10);
std::cout << "========== 01 ==========\n";
std::iota(std::begin(v), std::end(v), 0);
for (int i = 0; i < 5; i++) {
std::copy(std::begin(v), std::prev(std::end(v)), std::ostream_iterator<const decltype(v)::value_type&>{std::cout});
std::cout << *std::prev(std::end(v)) << "\n";
std::rotate(std::begin(v), std::begin(v) + 1, std::end(v));
}
std::cout << "========== 02 ==========\n";
std::iota(std::begin(v), std::end(v), 0);
for (int i = 0; i < 5; i++) {
std::copy(std::begin(v), std::prev(std::end(v)), std::ostream_iterator<const decltype(v)::value_type&>{std::cout});
std::cout << *std::prev(std::end(v)) << "\n";
std::rotate(std::begin(v), std::begin(v) + 2, std::end(v));
}
std::cout << "========== 03 ==========\n";
std::iota(std::begin(v), std::end(v), 0);
for (int i = 0; i < 5; i++) {
std::copy(std::begin(v), std::prev(std::end(v)), std::ostream_iterator<const decltype(v)::value_type&>{std::cout});
std::cout << *std::prev(std::end(v)) << "\n";
std::rotate(std::begin(v) + 4, std::begin(v) + 5, std::end(v));
}
逆方向への転回にはリバースイテレータを用いるとよい．
std::rotate(std::rbegin(v), std::rbegin(v) + 1, std::rend(v));
std::remove(): 指定した要素を削除する
第三引数にラムダ式を指定することができ，このラムダ式は2つの要素が等しいならtrue, そうでなければ false を返すように作る．
ただし，ラムダ式版を使うことは滅多にないと思われる．
（operator==()が無ければ使う機会あるかもしれない）
なお，removeという関数名に惑わされがちだが，実際には削除動作は行われず，削除したとする要素を末尾に持っていくだけである．
std::remove() は削除されなかった要素の次の位置，すなわち削除した要素が詰められている位置のイテレータを返却するので，メンバ関数の erase() を用いて，次のように要素を削除する．
std::vector v{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
v.erase(std::remove(std::begin(v), std::end(v), 1), std::end(v));
std::remove() が実際には削除を行わないのは，配列などの要素数変更不可のものに対して用いることを考えているためだと思われる．
int arr[] = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
auto endItr = std::remove(std::begin(arr), std::end(arr), 1);
for (auto itr = std::begin(arr); itr != endItr; ++itr) {
std::cout << *itr << "\n";
}
erase() は「対象要素のデストラクタの実行」と「コンテナのリサイズ」の2つを行っていると考えられる．
したがって， erase() しない場合は，要素のデストラクタが実行されないことに気を付けないといけない．
std::unique(): 重複要素を削除する
集合から重複した要素を取り除く．
ただし，事前に集合がソートされている必要がある．
std::remove() と同様，除外対象の要素を末尾に詰めるだけなので，実際の削除処理は erase() メンバ関数で行う必要がある．
std::vector v{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
std::sort(std::begin(v), std::end(v));
std::unique(std::begin(v), std::end(v));
for (const auto& e : v) {
std::cout << e << "\n";
}
std::vector v{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
std::sort(std::begin(v), std::end(v));
v.erase(std::unique(std::begin(v), std::end(v)), std::end(v));
for (const auto& e : v) {
std::cout << e << "\n";
}
std::copy, std::copy_if(): 集合の要素をコピーする
std::copy() は集合の要素のコピーを行う．
出力先は始点となるイテレータのみを渡す．
std::vector<int> srcVector{1, 2, 4, 8};
std::vector<int> dstVector(srcVector.size());
std::copy(std::begin(srcVector), std::end(srcVector), std::begin(dstVector));
std::copy() の出力先はイテレータであればよいので，色々なことができる．
例えば，std::back_inserter と組み合わせると，
std::vector<int> srcVector{1, 2, 4, 8};
std::vector<int> dstVector{1, 1, 2, 3, 5, 8};
std::copy(std::begin(srcVector), std::end(srcVector), std::back_inserter(dstVector))
のように，出力先STLコンテナの末尾に要素を追加していくようにもできるし，std::ostream_iterator を使って，
std::vector<int> srcVector{1, 2, 4, 8};
std::copy(std::begin(srcVector), std::end(srcVector), std::ostream_iterator<const decltype(v)>&){std::cout, " "};
のようにストリームへ出力することもできる．
std::copy_if() は条件を満す要素だけを対象にする．
例えば，偶数のみをコピーするという処理は，
std::vector<int> srcVector{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
std::vector<int> dstVector;
std::copy(
std::begin(srcVector),
std::end(srcVector),
std::back_inserter(dstVector),
[](const decltype(srcVector)::value_type& e) {
return e % 2 == 0;
});
と書ける．
std::generate(), std::generate_n(): 要素の生成
std::generate() は要素の初期化に用いることができる．
ただし，同じ値で埋めるというのは，std::fill() の仕事であるので，少し工夫して用いないとあまり意味のない関数である．
int cnt = 0;
auto generator = [&i]{
return i * 3;
};
std::vector<int> v(10);
std::generate(
std::begin(v),
std::end(v),
[&generator]{
return generator();
});
要素を乱数で埋めることにも利用できる．
std::vector<int> v(10);
std::generate(std::begin(v), std::end(v), std::mt19937{std::random_device{}()});
std::transform(): 要素の写像
std::transform() は他の言語で言うところのmap，C#であればLINQのSelect関数に相当する．
例えば，std::vector<int> の全要素を2乗した値を別の std::vector<int> にコピーするには，
std::vector<int> v1{1, 2, 3, 4, 5};
std::vector<int> v2(v1.size());
std::transform(
std::begin(v1),
std::end(v1),
std::begin(v2),
[](const decltype(v1)::value_type& e) {
return e * e;
});
std::copy(std::begin(v1), std::end(v1), std::ostream_iterator<const decltype(v1)::value_type&>{std::cout, "\n"});
と書く．既に v2 にいくつかの要素があり，末尾に追加したい場合は，
std::vector<int> v1{1, 2, 3, 4, 5};
std::vector<int> v2(v1.size());
std::transform(
std::begin(v1),
std::end(v1),
std::back_inserter(v2),
[](const decltype(v1)::value_type& e) {
return e * e;
});
std::copy(std::begin(v1), std::end(v1), std::ostream_iterator<const decltype(v1)::value_type&>{std::cout, "\n"});
とするとよい．
もちろん，自身に対して破壊的変更を加えることもできる．
std::vector<int> v{1, 2, 3, 4, 5};
std::transform(
std::begin(v),
std::end(v),
std::begin(v),
[](const decltype(v)::value_type& e) {
return e * e;
});
std::copy(std::begin(v), std::end(v), std::ostream_iterator<const decltype(v)::value_type&>{std::cout, "\n"});
std::next_permutation(), std::prev_permutation(): 組み合わせの生成
おそらく競技プログラミングでしか使われることのない関数として，集合の要素を並び替え，組み合わせを生成する std::next_permutation(), std::prev_permutation() がある．
基本的に以下のような do ~ while と併用する形で用いる．
全ての組み合わせに並び換えができたら do ~ while から抜けるようになっている．
std::vector v{ {1, 1, 3, 4, 1} };
do {
std::copy(
std::begin(v),
std::prev(std::end(v)),
std::ostream_iterator<const decltype(v)::value_type&>{std::cout, " "});
std::cout << *std::prev(std::end(v)) << "\n";
} while (std::next_permutation(std::begin(v), std::end(v)));
<numeric>
<numeric> の中にも <algorithm> と似た開始と終了位置のイテレータを引数に取る関数がいくつか存在する．
std::accumulate(): 合計値を求める
std::accumulate() は std::vector 等の合計値を求めるのに利用できる．
数値型の集合の場合，第三引数は基本的に 0 にすることが多いと思われる．
std::vector<int> v(1000);
std::iota(std::begin(v), std::end(v), 0);
auto sum = std::accumulate(std::begin(v), std::end(v), 0);
std::cout << sum << "\n";
上記は，以下の計算と同様である．
ただし，合計値は第三引数の型になるので，集合の各要素が取り得る値の範囲，要素数を考慮して long long や double などにして，オーバーフローが発生しないように気をつける必要がある．
（例えば， 0LL や 0.0 にするなど）
第4引数で各要素を足し合わせるときのアクションを指定できる．
まず，第4引数を指定しない場合と同等の処理は，
std::vector<int> v{1, 2, 3, 4, 5};
std::accumulate(
std::begin(s),
std::end(s),
0,
[](int acc, const decltype(v)::value_type& e){
return acc + e;
});
と書ける．
例えば，各要素を2乗した和を求めるには，
std::vector<int> v{1, 2, 3, 4, 5};
std::accumulate(
std::begin(s),
std::end(s),
0,
[](int acc, const decltype(v)::value_type& e){
return acc + (e * e);
});
とすればよい．
std::accumulate() にリバースイテレータを与えることで，foldrを実現することもできる．
std::vector v{"abc", "def", "ghi", "jkl", "mno"};
std::accumulate(
std::rbegin(s),
std::rend(s),
std::string{""},
[](const std::string& acc, const decltype(v)::value_type& e) {
return e + acc;
});
std::inner_product(): 内積を求める
std::inner_product() は2つの集合の内積，すなわち，
\begin{equation}
\boldsymbol{x} = \left( x_0, x_1, x_2, \cdots, x_{N - 1} \right)^{T}
\end{equation}
\begin{equation}
\boldsymbol{y} = \left( y_0, y_1, y_2, \cdots, y_{N - 1} \right)^{T}
\end{equation}
に対して，次の計算を行う関数である．
\begin{equation}
\boldsymbol{x}^{T} \boldsymbol{y} = \sum_{i = 0}^{N - 1} x_i y_i
\end{equation}
コードにすると，以下のようになる．
std::vector<int> xs{1, 2, 3, 4, 5};
std::vector<int> ys{5, 4, 3, 2, 1};
auto ip = std::inner_product(
std::begin(xs),
std::end(xs),
std::begin(ys),
0.0);
内積を求める関数であるが，第5，第6引数にラムダを指定すると，色々と便利になる．
例えば，共分散
\begin{equation}
S_{xy} = \dfrac{1}{n} \sum_{i = 0}^{N - 1} \left( x_i - \bar{x} \right) \left( y_i - \bar{y} \right)
\end{equation}
を求めるなら，
std::vector<int> xs{10, 20, 30, 40, 50, 60};
std::vector<int> ys{1, 1, 2, 3, 5, 8};
auto mx = std::accumulate(std::begin(xs), std::end(xs), 0) / static_cast<double>(xs.size());
auto my = std::accumulate(std::begin(ys), std::end(ys), 0) / static_cast<double>(ys.size());
auto sxy = std::inner_product(
std::begin(xs),
std::end(xs),
std::begin(ys),
0.0,
[](const double acc, const double e){
return acc + e;
},
[&mx, &my](const decltype(xs)::value_type x, const decltype(ys)::value_type y){
return (x - mx) * (y - my);
}) / xs.size();
のように書くことができる．
また，
\begin{equation}
\sum_{i = 0}^{N - 1} \left( -1 \right)^{i} \dfrac{y_i}{x_i}
\end{equation}
のようなものでも，
std::vector<double> xs{10, 20, 30, 40, 50, 60};
std::vector<double> ys{1, 1, 2, 3, 5, 8};
int sign = -1;
auto sxy = std::inner_product(
std::begin(xs),
std::end(xs),
std::begin(ys),
0.0,
[&sign](const double acc, const double e){
return acc + (sign = -sign) * e;
},
[](const decltype(xs)::value_type& x, const decltype(ys)::value_type& y){
return y / x;
});
と書いて計算できる．
std::partial_sum(): 累積和を求める
std::partial_sum() は累積和の列を生成する関数である．
例えば，
std::vector v1{0, 1, 2, 3, 4, 5};
std::vector v2(v1.size());
std::partial_sum(std::begin(v1), std::end(v), std::begin(v2));
とすると，v2 の値は 0, 1, 3, 6, 10, 15 となる．
競技プログラミングにおいては，いもす法などで使える場面がある．
std::iota()
std::iota() は指定した集合に，0, 1, 2, 3と1ずつ増加する値を詰める．
std::vector<int> v(10);
std::iota(std::begin(v), std::end(v), 0);
第3引数は開始する値なので，例えば10, 11, 12と値を詰めたい場合は，
std::vector<int> v(10);
std::iota(std::begin(v), std::end(v), 10);
とするとよい．
僕個人としては，サンプルコードを書く場合には使うことが多いが，それ以外の場面で使ったことはない．
文字列操作
C++の標準ライブラリの文字列操作はあまり充実していない．
splitですらわざわざ自分で実装をする必要がある．
ここでは，基本的な文字列処理の実装を紹介する．
文字列・数値変換
C++11からは数値と文字列間の変換が楽になった．
文字列から数値にするには，数値の型により以下の関数を使いわける．
C言語の古代の文字列から数値へ変換する関数 std::atoi() と異なり，変換エラー発生時は例外を投げるし，異常状態から復帰できないということはない．
| 関数 |
変換元の数値の型 |
std::stoi() |
int |
std::stol() |
long |
std::stoll() |
long long |
std::stof() |
float |
std::stod() |
double |
std::stold() |
long double |
使用例は以下のような感じ．
try {
auto intValue = std::stoi("10");
std::string s1{"20"};
auto longValue = std::stoi(s1);
auto longlongValue = std::stoi(s1);
auto intValue = std::stoi("10.5");
std::string s2{"1e-9"};
auto longDoubleValue = std::stoi(s2);
std::string s3{"3.1415926535"};
auto longlongDoubleValue = std::stoi(s3);
} catch (const std::invalid_argument& e) {
std::cerr << e.what() << "\n";
} catch (const std::out_of_rage& e) {
std::cerr << e.what() << "\n";
}
try ~ catchは任意で実装するとよい．また，std::invalid_argument と std::out_of_rage を分けて実装する必要がなければ，
try {
} catch (const std::exception& e) {
}
のようにまとめて例外を補足してもいいし，そもそも補足せずに上位の関数任せにしてもよい．
逆に数値から文字列にするには std::to_string() 関数を用いればよい．
auto s = std::to_string(123);
数値から文字列に
C++11で，std::to_string() という関数が標準ライブラリに加わったので，それを利用する．
文字列から数値に
大文字・小文字変換
<algorithm> の std::transform() と <cctype> の ::toupper(), ::tolower （C言語関数）を利用する．
std::string s1{"aBcDeFgH"};
std::transform(std::begin(s1), std::end(s1), std::begin(s1), ::toupper);
std::string s2{"aBcDeFgH"};
std::transform(std::begin(s2), std::end(s2), std::begin(s2), ::tolower);
無名名前空間（すなわちC言語ライブラリ）のものを指定しないとダメで，std 名前空間のものを指定すると，候補が複数ありコンパイルエラーとなる．
std::string s1{"aBcDeFgH"};
std::transform(std::begin(s1), std::end(s1), std::begin(s1), std::toupper);
std::string s2{"aBcDeFgH"};
std::transform(std::begin(s2), std::end(s2), std::begin(s2), std::tolower);
以下のように関数ポインタにキャストという形で明示するとコンパイルは通るが，タイプ量が少ない無名名前空間指定の方を使う方がよいだろう．
std::string s1{"aBcDeFgH"};
std::transform(std::begin(s1), std::end(s1), std::begin(s1), static_cast<int (*)(int)>(std::toupper));
std::string s2{"aBcDeFgH"};
std::transform(std::begin(s2), std::end(s2), std::begin(s2), static_cast<int (*)(int)>(std::tolower));
なお，::toupper(), ::tolower はC言語関数であり，いちいち関数コールが発生するようなコード生成がなされるので，以下のように自前の関数を書く方がよいかもしれない．
std::string s1{"aBcDeFgH"};
std::transform(std::begin(s1), std::end(s1), std::begin(s1), [](char c){ return 'a' <= c && c <= 'z' ? c - ('a' - 'A') : c; });
std::string s2{"aBcDeFgH"};
std::transform(std::begin(s2), std::end(s2), std::begin(s2), [](char c){ return 'A' <= c && c <= 'Z' ? c + ('a' - 'A') : c; });
ただし，これは 'a' ~ 'z' の文字コードが連続かつ 'A' ~ 'Z' の文字コードが連続かつ 'A' < 'a' であることを前提にしているので，目ざとい人には咎められるコードではある．
まぁ，ほとんどの環境では動作するので問題はないとしてもよいだろう．
分割 (1文字区切り)
基本的には std::vector に格納し，返り値で返せばよい．
しかし， std::vector 以外にも格納したい場合を考えて，ラムダ式バージョンを用意すると便利かもしれない．
また，ラムダ式バージョンであれば，そもそも何かに格納する必要も無く，そのまま出力を行うこともできる．
#include <string>
#include <sstream>
#include <vector>
template<typename F>
static inline void
split(const std::string& str, char delim, const F& f) noexcept
{
std::istringstream iss{str};
for (std::string token; std::getline(iss, token, delim);) {
f(token);
}
}
static inline std::vector<std::string>
split(const std::string& str, char delim) noexcept
{
std::vector<std::string> tokens;
split(str, delim, [&tokens](const std::string& token){
tokens.push_back(token);
});
return tokens;
}
#include <iostream>
#include <list>
#include <string>
int
main()
{
for (const auto& token : split("10,20,30", ',')) {
std::cout << token << "\n";
}
std::list<std::string> tokenList;
split("abc,def,ghi", ',', [&tokenList](const std::string& token){
tokenList.push_back(token);
});
for (const auto& token : tokenList) {
std::cout << token << "\n";
}
split("apple,banana,cake", ',', [](const std::string& token){
std::cout << token << "\n";
});
return 0;
}
置換 (1文字)
特定の1文字を別の1文字に置き換えるには，<algorithm> の std::replace()，あるいは std::replace_if() を用いるとよい．
例えば，文字列中の 'a' を 'A' に置換するには，
std::string s{"apple,banana,cake"};
std::replace(std::begin(s), std::end(s), 'a', 'A');
とすればよい．また，文字列中の大文字を全て '_' に置き換えるには，
std::string s{"apple,banana,cake"};
std::replace_if(
std::begin(s),
std::end(s),
[](const decltype(s)::value_type& e){
return std::isupper(e);
}, '_');
とすればよい．
分割 (文字列区切り)
1文字区切りと同じようなAPIで利用できるように関数を作る．
#include <string>
#include <sstream>
#include <vector>
template<typename F>
static inline void
split(const std::string& str, const std::string& delim, const F& f) noexcept
{
std::string::size_type spos{0}, epos;
while ((epos = str.find_first_of(delim, spos)) != std::string::npos) {
f(str.substr(spos, epos - spos));
spos = epos + delim.length();
}
f(str.substr(spos));
}
static inline std::vector<std::string>
split(const std::string& str, const std::string& delim) noexcept
{
std::vector<std::string> tokens;
split(str, delim, [&tokens](const std::string& token){
tokens.push_back(token);
});
return tokens;
}
#include <iostream>
#include <list>
#include <string>
int
main()
{
for (const auto& token : split("10, 20, 30", ", ")) {
std::cout << token << "\n";
}
std::list<std::string> tokenList;
split("abc::def::ghi", "::", [&tokenList](const std::string& token){
tokenList.push_back(token);
});
for (const auto& token : tokenList) {
std::cout << token << "\n";
}
split("apple-banana-cake", "-", [](const std::string& token){
std::cout << token << "\n";
});
return 0;
}
C++11からは正規表現が標準ライブラリでサポートされた．
これにより，指定パターンで文字列を分割，置換，パターンにマッチする文字列を取得するといったことができる．
マッチする文字列の抽出
基本的に std::sregex_iterator というイテレータを作成して，ループを行う．
std::sregex_iterator のインスタンスをデフォルトコンストラクタで作成したとき，それはマッチの終端を指す．
std::string text{"abc123cd456efg789"};
std::regex re{"\\d+"};
for (std::sregex_iterator itr{std::begin(text), std::end(text), re}, end; itr != end; ++itr) {
std::cout << "at " << itr->position() << ": " << itr->str() << "\n";
}
マッチ位置などが必要無ければ，std::sregex_token_iterator を用いるとよい．
std::string text{"abc123cd456efg789"};
std::regex re{"\\d+"};
for (std::sregex_token_iterator itr{std::begin(text), std::end(text), re}, end; itr != end; ++itr) {
std::cout << *itr << "\n";
}
std::sregex_token_iterator であれば，マッチした文字列の std::vector 等が作成できる．
std::string text{"abc123cd456efg789"};
std::regex re{"\\d+"};
std::vector<std::string> matchedStrings(std::regex_token_iterator{std::begin(text), std::end(text), re}, std::regex_token_iterator{});
std::string text{"abc123cd456efg789"};
std::regex re{"\\d+"};
std::vector v{"apple", "banana", "cake"};
std::copy(
std::sregex_token_iterator{std::begin(text), std::end(text), re, -1},
std::sregex_token_iterator{},
std::back_inserter(v));
文字列分割
文字列分割は std::sregex_token_iterator を用いる．
マッチと違い，std::sregex_iterator は利用できない．
std::string text{" apple banana cake "};
std::regex re{"\\s+"};
for (std::sregex_token_iterator itr{std::begin(text), std::end(text), re, -1}, end; itr != end; ++itr) {
std::cout << itr->str() << "\n";
}
std::vector 等の作成，末尾への要素挿入は以下のようにできる．
std::string text{" apple banana cake "};
std::regex re{"\\s+"};
std::vector<std::string> matchedStrings(std::regex_token_iterator{std::begin(text), std::end(text), re, -1}, std::regex_token_iterator{});
std::string text{"abc|cd-efg|"};
std::regex re{"[\\-|]"};
std::vector v{"apple", "banana", "cake"};
std::copy(
std::sregex_token_iterator{std::begin(text), std::end(text), re, -1},
std::sregex_token_iterator{},
std::back_inserter(v));
文字列置換
置換に関しては std::regex_replace() という関数がある．
std::cout << std::regex_replace("abcDEF012ghiJKL", std::regex{"[a-z]+"}, "_") << "\n";
1つクラスを定義するので，正確には無名ではないが，C++14以降なら無名再帰できる．
この記事中の FixPoint クラスを用いる．
（本質的ではない [[nodiscard]] や noexcept(noexcept(...)) といった部分は除去した）
#include <utility>
template <typename F>
class FixPoint final : private F
{
public:
template <typename G>
explicit constexpr FixPoint(G&& g) noexcept
: F{std::forward<G>(g)}
{}
template <typename... Args>
constexpr decltype(auto)
operator()(Args&&... args) const
{
return F::operator()(*this, std::forward<Args>(args)...);
}
};
#if defined(__cpp_deduction_guides)
template <typename F>
FixPoint(F&&)
-> FixPoint<std::decay_t<F>>;
#endif
namespace
{
template <typename F>
inline constexpr decltype(auto)
makeFixPoint(F&& f) noexcept
{
return FixPoint<std::decay_t<F>>{std::forward<std::decay_t<F>>(f)};
}
}
#include <iostream>
int
main()
{
auto result = makeFixPoint([](auto f, int n) -> int {
return n < 2 ? n : (f(n - 1) + f(n - 2));
})(10);
std::cout << result << "\n";
return 0;
}
（makeFixPoint という関数名は長すぎるので fix にしてもいいと思う）
ちなみに，同等のものはBoost.Hanaにもある．
AtCoderではBoostが利用可能なので，FixPoint を自分で実装しなくてもよい．
#include <iostream>
#include <boost/hana/functional/fix.hpp>
int
main()
{
auto result = boost::hana::fix([](auto f, int n) -> int {
return n < 2 ? n : (f(n - 1) + f(n - 2));
})(10);
std::cout << result << "\n";
return 0;
}
無名再帰の利点はローカル変数のキャプチャができる点である．
C++11ではジェネリックラムダが無いため，無名再帰ができないので，std::function を用いるしかない．
std::function は実行速度が遅いので，可能な限り用いるべきではないが仕方ない．
#include <functional>
#include <iostream>
#include <utility>
int
main()
{
std::function<int(int)> fib = [&fib](int n) -> int {
return n < 2 ? n : (fib(n - 1) + fib(n - 2));
};
auto result = fib(10);
std::cout << result << "\n";
}
気をつけること
std::function はラムダの型を表さない
std::function はラムダを格納できるが，ラムダの型そのものではない．
ラムダの型は auto やテンプレート，decltype() でしか取得できない．
std::function は実行速度がかなり遅いので，極力用いるべきではない．
（std::function が遅いのは，あらゆる関数っぽいものを格納するために型消去を行っているので，インライン展開が難しいことと，operator() の呼び出しをしたとき，保持している関数があるかどうかを確認するようになっていたりするためである）
例えば，次の std::priority_queue の比較関数の指定は1文で書けるので簡潔であるが，性能としては最悪である．
std::priority_queue<int, std::vector<int>, std::function<bool(const int& x, const int& y)>> pq(
[](const int& x, const int& y) {
return x > y;
});
ちゃんとラムダをラムダのまま渡すべきである．
auto compare = [](const int& x, const int& y){
return x > y;
};
std::priority_queue<int, std::vector<int>, decltype(compare)> pq(std::move(compare));
関数の引数にラムダを渡すときはテンプレートを用いる必要がある．
以下は std::function を用いてしまっているNG例である．
static inline long long
measureTime(const std::function<void>& f)
{
auto start = std::chrono::high_resolution_clock::now();
f();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count();
return elapsed;
}
正しくはこうする．
template<typename F>
static inline long long
measureTime(F&& f) noexcept(noexcept(f()))
{
auto start = std::chrono::high_resolution_clock::now();
f();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count();
return elapsed;
}
クラスのメンバにラムダを持たせる場合も同様である．
以下は std::function として保持している悪い例である．
#include <functional>
#include <utility>
class Finally
{
public:
explicit Finally(const std::function<void()>& f) noexcept
: m_f(f)
{}
~Finally()
{
m_f();
}
private:
const std::function<void()> m_f;
};
#include <iostream>
int
main()
{
{
Finally f{[]{
std::cout << "Exit scope" << std::endl;
}};
std::cout << "Hello World!" << std::endl;
}
return 0;
}
正しくは以下のようにする．
#include <utility>
template<typename F>
class Finally
{
public:
explicit Finally(F&& f) noexcept
: m_f(std::forward<F>(f))
{}
~Finally()
{
m_f();
}
private:
const F m_f;
};
template<typename F>
static inline Finally<F>
makeFinally(F&& f) noexcept
{
return Finally<F>{std::forward<F>(f)};
}
#include <iostream>
int
main()
{
{
auto f1 = makeFinally([]{
std::cout << "Exit scope 01" << std::endl;
});
auto g = []{
std::cout << "Exit scope 02" << std::endl;
};
Finally<decltype(g)> f2(std::move(g));
Finally f3{[]{
std::cout << "Exit scope 03" << std::endl;
}};
std::cout << "Hello World!" << std::endl;
}
return 0;
}
ただし，クラステンプレートの型推論はC++17までできないので，型推論のための関数テンプレートを用意しておかないと使い勝手が悪い．
ローカルに巨大な配列を宣言しない
他の言語の経験はあるが，C言語，あるいはC++に不慣れな人，あるいはプログラミング自体初心者がC言語，C++に触れたときにやらかしがちなミスがスタック領域を食い潰すということである．
例えば，以下のコードは問題なく動作するが，
#include <iostream>
#include <algorithm>
#include <random>
int arr[500000];
int
main()
{
std::cout << "Program started\n";
std::cout << "Initialize array\n";
std::iota(std::begin(arr), std::end(arr), 0);
std::cout << "Show sum of array elements\n";
std::cout << std::accumulate(std::begin(arr), std::end(arr), 0LL) << "\n";
return 0;
}
グローバル変数の配列を main() 関数内に持ってくると，動作しなくなる．
#include <iostream>
#include <algorithm>
#include <numeric>
#include <random>
int
main()
{
std::cout << "Program started\n";
int arr[500000];
std::cout << "Initialize array\n";
std::iota(std::begin(arr), std::end(arr), 0);
std::cout << "Show sum of array elements\n";
std::cout << std::accumulate(std::begin(arr), std::end(arr), 0LL) << "\n";
return 0;
}
これは，グローバル変数とローカル変数とで，使用されるメモリ領域が異なるためである．
グローバル変数は「静的領域」という箇所に置かれ，ローカル変数は「スタック領域」という場所に置かれる．
スタック領域は関数呼び出し時に，その関数の引数，宣言されている変数等のサイズ消費される．
巨大な配列を宣言すれば，その分だけ関数呼び出し時にスタック領域が消費される．
スタック領域はあまり大きな要領を持つことができないため，巨大な配列をローカルで宣言すると，スタック領域の限界を超えてしまう．
（深すぎる再帰呼び出しで「スタックオーバーフロー」となるのは同じ理由）
巨大な配列を使用したい場合は基本的に new などを用いてヒープ領域という領域に動的確保を行う．
std::vector などのSTLコンテナも基本的にメモリを new などで動的確保し，そこに要素を格納している．
しかし，一度書いてしまったローカルに巨大な配列をとるように書いたプログラムを 巨大配列をグローバル変数にしたり，new したり，std::vector に置きかえたりするのは，わずかに面倒である（特に競技プログラミングにおいては）．
そこで，ローカルの巨大配列に static を付けると，とりあえず問題は解決する．
#include <iostream>
#include <algorithm>
#include <numeric>
#include <random>
int
main()
{
std::cout << "Program started\n";
static int arr[500000];
std::cout << "Initialize array\n";
std::iota(std::begin(arr), std::end(arr), 0);
std::cout << "Show sum of array elements\n";
std::cout << std::accumulate(std::begin(arr), std::end(arr), 0LL) << "\n";
return 0;
}
関数内における static 有りの変数は，グローバル変数と同じ静的領域に取られる．
ただし，関数内 static 変数は次の2つの特徴がある．
- 変数の初期化は最初の関数呼び出し時の一度のみ行われる
- 2度目以降の関数呼び出しを行ったとき，前の呼び出し時の値が残っている
この特徴は次のコードで確認できる．
#include <iostream>
void
countup() noexcept
{
static int cnt = 10;
std::cout << "Before countup: " << cnt << "\n";
cnt++;
std::cout << "After countup: " << cnt << "\n";
}
int
main()
{
countup();
countup();
countup();
return 0;
}
関数内 static 変数は，その関数からのみ見えるグローバル変数といえるだろう．
long 型は使用しない
C++では各基本整数型が何byteであるか，明確には定められていないが，今日の大半の環境下では以下のようになっているとしてもよい．
（unsigned は省略）
| 型 |
サイズ（byte） |
char |
1 |
short |
2 |
int |
4 |
long |
4 or 8 |
long long |
8 |
この中で long だけが環境によって4byteか8byteか不定である．
Visual Studioであれば，long は4byte，gccであってもlong はx86なら4byte，x64なら8byteとなっている．
8byte整数を利用したい場合は，long long を用いるべきである．
なお，先に述べたように，C++では基本整数型が何byteであるか定められていないので，本当にこだわるならば，<cstdint> で typedef されている以下の整数型を用いるべきである．
| 型 |
サイズ（byte） |
符号 |
std::int8_t |
1 |
有 |
std::int16_t |
2 |
有 |
std::int32_t |
4 |
有 |
std::int64_t |
8 |
有 |
std::uint8_t |
1 |
無 |
std::uint16_t |
2 |
無 |
std::uint32_t |
4 |
無 |
std::uint64_t |
8 |
無 |
書式指定文字列マクロ
先ほど <cstdint> で typedef されている整数型について触れたので，ついでに紹介しておこうと思う．
std::printf や std::scanf では書式指定文字列が必要となるが，与える引数の型に注意しながら書かなくてはならない．
そのとき，「"%d" だっけ？ "%ld" だっけ？」となることもあるだろう．
そんなとき <cinttypes> のマクロを利用するとよい．
#include <cinttypes>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <array>
int
main()
{
std::int8_t a{114};
std::int16_t b{514};
std::int32_t c{1919};
std::int64_t d{810};
std::printf("%" PRId8 ", %" PRId16 ", %" PRId32 ", %" PRId64 "\n", a, b, c, d);
std::array<char, 1024> lineBuf;
std::fill(std::begin(lineBuf), std::end(lineBuf), '\0');
if (std::fgets(lineBuf.data(), lineBuf.size(), stdin) == nullptr) {
return 1;
}
if (std::sscanf(lineBuf.data(), "%" SCNd8 " %" SCNd16 " %" SCNd32 " %" SCNd64, &a, &b, &c, &d) != 4) {
return 2;
}
std::printf("0x%" PRIx8 ", 0x%" PRIx16 ", 0x%" PRIx32 ", 0x%" PRIx64 "\n", a, b, c, d);
return 0;
}
1つC言語の文字列リテラルに関するカラクリがある．
C言語の文字列リテラルは， "abc" "def" のように，文字列リテラル間にホワイトスペースしか存在しない場合（どちらか一方がカッコで囲われてもダメ），"abcdef" という文字列リテラルと解釈されるというルールがある．
実は PRId32 のマクロはそのまま "d" 等のダブルクォーテーションの文字列リテラルに展開されるようになっているので，この文字列リテラルルールにより， "%" PRId32 が "%d" と同等となっている．
printf系のフォーマット文字列マクロは PRI*XX, scanf系のフォーマット文字列マクロは SCN*XX となっている（* は符号有り，符号無し，8進数，16進数を示す1文字，XX は対象整数のビット数）．
表にまとめると以下の通り．
まず，printf系のフォーマット文字列マクロを掲載する．
| マクロ |
機能 |
例 |
PRId8 |
8bit整数値10進数表示（符号有り） |
char, std::int8_t |
PRId16 |
16bit整数値10進数表示（符号有り） |
short, std::int16_t |
PRId32 |
32bit整数値10進数表示（符号有り） |
int, std::int32_t |
PRId64 |
64bit整数値10進数表示（符号有り） |
long long int, std::int64_t |
PRIdPTR |
ポインタ10進数表示（符号有り） |
int*, unsigned int*, std::intptr_t |
PRIu8 |
8bit整数値10進数表示（符号無し） |
unsigned char, std::uint8_t |
PRIu16 |
16bit整数値10進数表示（符号無し） |
unsigned short, std::uint16_t |
PRIu32 |
32bit整数値10進数表示（符号無し） |
unsigned int, std::uint32_t |
PRIu64 |
64bit整数値10進数表示（符号無し） |
unsigned long long int, std::uint64_t |
PRIuPTR |
ポインタ10進数表示（符号無し） |
int*, unsigned int*, std::uintptr_t |
PRIo8 |
8bit整数値8進数表示 |
char, std::int8_t, std::uint8_t |
PRIo16 |
16bit整数値8進数表示 |
short, std::int16_t, std::uint16_t |
PRIo32 |
32bit整数値8進数表示 |
int, std::int32_t, std::uint32_t |
PRIo64 |
64bit整数値8進数表示 |
long long int, std::int64_t, std::uint64_t |
PRIoPTR |
ポインタ8進数表示 |
int*, unsigned int*, std::uintptr_t |
PRIx8 |
8bit整数値16進数表示（小文字） |
char, std::int8_t, std::uint8_t |
PRIx16 |
16bit整数値16進数表示（小文字） |
short, std::int16_t, std::uint16_t |
PRIx32 |
32bit整数値16進数表示（小文字） |
int, std::int32_t, std::uint32_t |
PRIx64 |
64bit整数値16進数表示（小文字） |
long long int, std::int64_t, std::uint64_t |
PRIxPTR |
ポインタ16進数表示（小文字） |
int*, unsigned int*, std::uintptr_t |
PRIX8 |
8bit整数値16進数表示（大文字） |
char, std::int8_t, std::uint8_t |
PRIX16 |
16bit整数値16進数表示（大文字） |
short, std::int16_t, std::uint16_t |
PRIX32 |
32bit整数値16進数表示（大文字） |
int, std::int32_t, std::uint32_t |
PRIX64 |
64bit整数値16進数表示（大文字） |
long long int, std::int64_t, std::uint64_t |
PRIXPTR |
ポインタ16進数表示（大文字） |
int*, unsigned int*, std::uintptr_t |
次に，scanf系のフォーマット文字列マクロを掲載する．
| マクロ |
機能 |
例 |
SCNd8 |
8bit整数値10進数表示（符号有り） |
char, std::int8_t |
SCNd16 |
16bit整数値10進数表示（符号有り） |
short, std::int16_t |
SCNd32 |
32bit整数値10進数表示（符号有り） |
int, std::int32_t |
SCNd64 |
64bit整数値10進数表示（符号有り） |
long long int, std::int64_t |
SCNdPTR |
ポインタ10進数表示（符号有り） |
int*, unsigned int*, std::intptr_t |
SCNu8 |
8bit整数値10進数表示（符号無し） |
unsigned char, std::uint8_t |
SCNu16 |
16bit整数値10進数表示（符号無し） |
unsigned short, std::uint16_t |
SCNu32 |
32bit整数値10進数表示（符号無し） |
unsigned int, std::uint32_t |
SCNu64 |
64bit整数値10進数表示（符号無し） |
unsigned long long int, std::uint64_t |
SCNuPTR |
ポインタ10進数表示（符号無し） |
int*, unsigned int*, std::uintptr_t |
SCNo8 |
8bit整数値8進数表示 |
char, std::int8_t, std::uint8_t |
SCNo16 |
16bit整数値8進数表示 |
short, std::int16_t, std::uint16_t |
SCNo32 |
32bit整数値8進数表示 |
int, std::int32_t, std::uint32_t |
SCNo64 |
64bit整数値8進数表示 |
long long int, std::int64_t, std::uint64_t |
SCNoPTR |
ポインタ8進数表示 |
int*, unsigned int*, std::uintptr_t |
SCNx8 |
8bit整数値16進数表示（小文字） |
char, std::int8_t, std::uint8_t |
SCNx16 |
16bit整数値16進数表示（小文字） |
short, std::int16_t, std::uint16_t |
SCNx32 |
32bit整数値16進数表示（小文字） |
int, std::int32_t, std::uint32_t |
SCNx64 |
64bit整数値16進数表示（小文字） |
long long int, std::int64_t, std::uint64_t |
SCNxPTR |
ポインタ16進数表示（小文字） |
int*, unsigned int*, std::uintptr_t |
SCNX8 |
8bit整数値16進数表示（大文字） |
char, std::int8_t, std::uint8_t |
SCNX16 |
16bit整数値16進数表示（大文字） |
short, std::int16_t, std::uint16_t |
SCNX32 |
32bit整数値16進数表示（大文字） |
int, std::int32_t, std::uint32_t |
SCNX64 |
64bit整数値16進数表示（大文字） |
long long int, std::int64_t, std::uint64_t |
SCNXPTR |
ポインタ16進数表示（大文字） |
int*, unsigned int*, std::uintptr_t |
std::vector 等の size() メンバ関数の返却値は int ではない
std::vector 等に関して，以下のコードを見ることがある．
std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int sz = v.size();
std::vector<T> の size() の型は int ではなく，std::vector<T>::size_type，もっと言うなら，std::size_t なので，2行目にて暗黙の変換が行われている．
それなりにワーニングフラグを付けてコンパイルしていれば，何らかのワーニングが出ると思うので，
std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int sz = static_cast<int>(v.size());
のように明示的にキャストするか，そもそも，
std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto sz = static_cast<int>(v.size());
のように，size() の返却値と同じ型を使うべきである．
個人的には，可能な限り auto や decltype を用いて，元の型を崩さないようにしておくべきであると思う．
C言語ヘッダのインクルード
C++において，C言語ヘッダをインクルードするとき，<stdio.h> のような.h付きのものではなく，<cstdio> のような先頭にcが付与され，.hが無いものをインクルードするとよい．
理由として大きいものはないが，std:: 名前空間にもC言語関数が定義されること <c*> はC++用にオーバーロードが用意されていることがある（特に <cmath>）からだ．
あと，単純にC++標準ライブラリは.hが無いので，そちらに合わせる方がカッコいい感じが出る（？）
対応表を書くまでもないが，以下の通りである．
| C言語でのインクルード記述 |
C++でのインクルード記述 |
#include <assert.h> |
#include <cassert> |
#include <ctype.h> |
#include <cctype> |
#include <errno.h> |
#include <cerrno> |
#include <float.h> |
#include <cfloat> |
#include <iso646.h> |
#include <ciso646> |
#include <limits.h> |
#include <climits> |
#include <locale.h> |
#include <clocale> |
#include <math.h> |
#include <cmath> |
#include <setjmp.h> |
#include <csetjmp> |
#include <signal.h> |
#include <csignal> |
#include <stdarg.h> |
#include <cstdarg> |
#include <stddef.h> |
#include <cstddef> |
#include <stdio.h> |
#include <cstdio> |
#include <stdlib.h> |
#include <cstdlib> |
#include <string.h> |
#include <cstring> |
#include <time.h> |
#include <ctime> |
#include <complex.h> |
#include <ccomplex> |
#include <fenv.h> |
#include <cfenv> |
#include <inttypes.h> |
#include <cinttypes> |
#include <stdalign.h> |
#include <cstdalign> |
#include <stdbool.h> |
#include <cstdbool> |
#include <stdint.h> |
#include <cstdint> |
#include <tgmath.h> |
#include <ctgmath> |
#include <uchar.h> |
#include <cuchar> |
#include <wchar.h> |
#include <cwchar> |
#include <wctype.h> |
#include <cwctype> |
よくわからないけどアクセス違反で落ちるとき
-g3
gdbでデバッグするときに使うコンパイルオプションである．
-g と違い，-g3 を指定すると，マクロ定数などもシンボル名として残るようになる．
最適化防止のために，-O0 も同時にしておくのが普通である．
-D_FORTIFY_SOURCE=2 or #define _FORTIFY_SOURCE 2
_FORTIFY_SOURCE 2 というマクロ定数をC言語標準ライブラリインクルード前に定義しておくと，文字列やメモリ操作を行うC言語標準ライブラリ関数において，軽いバッファオーバーフロー検出が行われるようになる．
コンパイルオプションに -D_FORTIFY_SOURCE=2 を付与して定義するのがスマートであると思う．
-D_GLIBCXX_DEBUG or #define _GLIBCXX_DEBUG
_GLIBCXX_DEBUG というマクロをSTLコンテナ関係のインクルードの前に定義しておくと，範囲外アクセスを検出できる．
コンパイルオプションに -D_GLIBCXX_DEBUG を付与して定義するのがスマートであると思う．
例えば，
#include <iostream>
#include <vector>
int
main()
{
std::vector<int> vct{1, 1, 4, 5, 1, 4}
std::cout << vct[1] << std::endl;
vct[6] = 1;
std::cout << vct[6] << std::endl;
return 0;
}
というコードを
$ g++ -D_GLIBCXX_DEBUG main.cpp -o main.out`
とコンパイルして実行すると，
/usr/local/gcc-head/include/c++/6.0.0/debug/vector:415:
Error: attempt to subscript container with out-of-bounds index 6, but
container only holds 6 elements.
Objects involved in the operation:
sequence "this" @ 0x0x7ffd676df690 {
type = std::__debug::vector<int, std::allocator<int> >;
}
というエラーが表示されて，アクセス違反箇所でabortするようになる．
-ftrapv
符号有り整数同士での加算，減算，乗算時にオーバーフローした場合，その時点でabortするようになる．
符号有り整数のオーバーフロー検出はできない．
ただし，意図的にオーバーフローさせる場面もあるし，abort位置を教えてくれるわけではないので，そこまで実用性はないかもしれない．
#include <iostream>
#include <limits>
int
main()
{
std::cout << (std::numeric_limits<int>::max() + 1) << std::endl;
std::cout << (std::numeric_limits<int>::min() - 1) << std::endl;
return 0;
}
コンパイルは以下の通り．
$ g++ -ftrapv main.cpp -o main.out`
-fstack-protector-all
コンパイルオプションに -fstack-protector-all を指定すると，スタック破壊を検出可能になる．
スタック破壊が検出されるのは，関数からのリターン直前で，破壊されていればバックトレースを表示してabortする．
#include <iostream>
int
main()
{
int a[10] = {0};
std::cout << a[5] << std::endl;
a[10] = 12;
std::cout << a[10] << std::endl;
return 0;
}
コンパイルは以下の通り．
$ g++ -fstack-protector-all main.cpp -o main.out`
実行結果は以下のようになる．
0
12
*** stack smashing detected ***: ./prog.exe terminated
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(__fortify_fail+0x37)[0x7fb165799e57]
/lib/x86_64-linux-gnu/libc.so.6(__fortify_fail+0x0)[0x7fb165799e20]
./prog.exe[0x400d4f]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xed)[0x7fb1656b176d]
./prog.exe[0x400bc9]
======= Memory map: ========
00400000-00401000 r-xp 00000000 fd:01 4992842 /home/jail/prog.exe
00601000-00602000 rw-p 00001000 fd:01 4992842 /home/jail/prog.exe
00f39000-00f6b000 rw-p 00000000 00:00 0 [heap]
7fb162e56000-7fb162e58000 r-xp 00000000 fd:01 11933814 /lib/x86_64-linux-gnu/libdl-2.15.so
7fb162e58000-7fb163058000 ---p 00002000 fd:01 11933814 /lib/x86_64-linux-gnu/libdl-2.15.so
7fb163058000-7fb163059000 r--p 00002000 fd:01 11933814 /lib/x86_64-linux-gnu/libdl-2.15.so
7fb163059000-7fb16305a000 rw-p 00003000 fd:01 11933814 /lib/x86_64-linux-gnu/libdl-2.15.so
7fb16305a000-7fb1646c5000 r--p 00000000 fd:01 8126494 /usr/local/lib/libicudata.so.52.1
7fb1646c5000-7fb1648c4000 ---p 0166b000 fd:01 8126494 /usr/local/lib/libicudata.so.52.1
7fb1648c4000-7fb1648c5000 rw-p 0166a000 fd:01 8126494 /usr/local/lib/libicudata.so.52.1
7fb1648c5000-7fb1648db000 r-xp 00000000 fd:01 11927780 /lib/x86_64-linux-gnu/libz.so.1.2.3.4
7fb1648db000-7fb164ada000 ---p 00016000 fd:01 11927780 /lib/x86_64-linux-gnu/libz.so.1.2.3.4
7fb164ada000-7fb164adb000 r--p 00015000 fd:01 11927780 /lib/x86_64-linux-gnu/libz.so.1.2.3.4
7fb164adb000-7fb164adc000 rw-p 00016000 fd:01 11927780 /lib/x86_64-linux-gnu/libz.so.1.2.3.4
...
-fsanitize=address
-fsanitize=address を付けてコンパイルすると，範囲外アクセスを検出できるようになる．
-fstack-protector-all と違い，動的確保したメモリに対しても有効である．
ただし，-fno-omit-frame-pointer と併用しなければならない．
#include <iostream>
#include <memory>
int
main()
{
auto ptr = std::make_unique<int[]>(10);
ptr[5] = 10;
std::cout << ptr[5] << std::endl;
ptr[13] = 10;
std::cout << ptr[13] << std::endl;
return 0;
}
コンパイルは以下の通り．
$ g++ -fsanitize=address main.cpp -o main.out`
実行結果は以下のようになる．
10
=================================================================
==721== ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60080000c004 at pc 0x400e48 bp 0x7ffe4eeddb20 sp 0x7ffe4eeddb18
WRITE of size 4 at 0x60080000c004 thread T0
#0 0x400e47 (/home/koturn/workspace/a.out+0x400e47)
#1 0x7f6344ac2ec4 (/lib/x86_64-linux-gnu/libc-2.19.so+0x21ec4)
#2 0x400c28 (/home/koturn/workspace/a.out+0x400c28)
0x60080000c004 is located 12 bytes to the right of 40-byte region [0x60080000bfd0,0x60080000bff8)
allocated by thread T0 here:
#0 0x7f634539188a (/usr/lib/x86_64-linux-gnu/libasan.so.0.0.0+0x1188a)
#1 0x400d33 (/home/koturn/workspace/a.out+0x400d33)
#2 0x7f6344ac2ec4 (/lib/x86_64-linux-gnu/libc-2.19.so+0x21ec4)
Shadow bytes around the buggy address:
0x0c017fff97b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff97c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff97d0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff97e0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff97f0: fa fa fa fa fa fa fa fa fa fa 00 00 00 00 00 fa
=>0x0c017fff9800:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff9810: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff9820: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff9830: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff9840: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c017fff9850: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Heap righ redzone: fb
Freed Heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack partial redzone: f4
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
ASan internal: fe
==721== ABORTING
まとめ
以上をまとめると，デバッグ用には以下のコンパイルオプションを与えるとよい．
g++ -g3 -O0 -D_FORTIFY_SOURCE=2 -D_GLIBCXX_DEBUG -ftrapv -fstack-protector-all -fno-omit-frame-pointer -fsanitize=address main.cpp -o main.out
こういうのはエイリアスで定義しておくと便利だと思われる．
