koturnの日記

転職したい社会人2年生の技術系日記

C++におけるfinallyの実装

はじめに

この記事は世間では十分に議論され尽くしてきたC++におけるfinally句という話について書こうと思う.

C++にはfinally無くて不便ですよね」という言葉は,実際にお仕事をしていて聞くことのある言葉なのだが,やはりC++初心者はfinallyが無い理由を考えないものであるらしい. C++にはRAII(Resource Aquisition Is Initialization)という考え方があり,これはリソース獲得と破棄をctorとdtorを使ってうまくやるというものである.

JavaC#といった言語はGCがあり,ファイナライザやdtorの呼び出しが制御できないようになっている. そのため,わざわざfinally句という枠組みが必要になってしまう. また,同様の理由でtry-with-resource文やusing文といった構文も必要になってしまうわけだ.

しかし,C++のdtorはローカル変数に限れば,その変数の寿命が尽きるとき,すなわちスコープを抜けるときに実行される仕組みとなっている. これがC++がfinally句を必要としない理由である.

ただし,あらゆるリソースの獲得と破棄のコードのためのクラスをいちいち用意していたのでは面倒である. そこで,C++11で取り入れられたラムダ式を利用することにより,より柔軟なRAIIクラスの設計が可能となる.

C++におけるfinallyの実装

以下のコードがfinally句を実現するためのクラスである.

#include <new>
#include <utility>


template<typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
Finally
{
public:
  explicit Finally(F&& f) noexcept
    : m_f(std::forward<F>(f))
  {}

  ~Finally()
  {
    m_f();
  }

  Finally(const Finally&) = delete;

  Finally(Finally&&) = default;

  Finally&
  operator=(const Finally&) = delete;

  Finally&
  operator=(Finally&&) = default;

  static void*
  operator new(std::size_t) = delete;

  static void*
  operator new(std::size_t, ...) = delete;

  static void
  operator delete(void*) = delete;

  static void
  operator delete(void*, ...) = delete;

private:
  const F m_f;
};  // class Finally


template<typename F>
static inline Finally<F>
makeFinally(F&& f) noexcept
{
  return Finally<F>{std::forward<F>(f)};
}

テンプレートパラメータの F は戻り値 void(実は何でもよい),引数無しのラムダ式等の関数を想定している. C++14まではクラステンプレートの型推論はできないために,型推論のための関数テンプレート makeFinally を用意しておく. 戻り値の Finally クラスのインスタンスを無視してはならないので,[[nodiscard]] 属性を付与しておく. もし,返り値を無視した場合,関数呼び出し終了直後に指定したラムダが実行されるようになってしまう.

std::function を利用しないのは,std::function にラムダを格納してしまうとインライン展開が行われることが無くなることと,std::functionoperator() 自体の例外チェックコストにより,性能に大きな影響を及ぼすことがあるためだ. ラムダ式ラムダ式のまま保っておくことにより,インライン展開が期待できる. この記事では std::function を用いた実装が紹介されているが,説明のために簡略化したものであり,実際のコードで用いてはならない.

Finally クラスはコピー等を許可する必要が無いため,コピーctorやコピー代入演算子delete 指定しておく. また,new による動的確保は許可しないでおく.

このクラスは以下のように使用する.

#include <iostream>


int
main()
{
  auto f1 = makeFinally([]{
    std::cout << "Hello World! from finally\n";
  });

  {
    std::cout << "Foo\n";
    auto f2 = makeFinally([]{
      std::cout << "Bar\n";
    });
    std::cout << "Baz\n";
  }

  std::cout << "Hello World!\n";
}

このコードの実行結果は以下の通りである.

Foo
Baz
Bar
Hello World!
Hello World! from finally

変数 f1f2 が破棄されるタイミングでそれぞれ指定したラムダが呼び出されていることがわかる.

さて,この記事のタイトルにもあるfinally句としての Finally クラスの使用を限定すると,

try {
  // 処理
} catch (...) {
  // 例外処理
} finally {
  // finally処理
}

と書きたいコードは以下のように書くことができる.

{
  auto f = makeFinally([]{
    // finally処理
  });
  try {
    // 処理
  } catch (...) {
    // 例外処理
  }
}

具体例としては以下のようなコードになるだろうか. (かなり作為的ではあるが)

#include <iostream>
#include <vector>


int
main()
{
  std::vector<int> v{1, 2, 3, 4, 5};
  auto f = makeFinally([&v]{
    std::cout << "vector size: " << v.size() << std::endl;
  });
  try {
    std::cout << "v[0] = " << v.at(0) << "\n";
    std::cout << "v[10] = " << v.at(10) << "\n";  // 例外発生
    std::cout << "end\n";
  } catch (const std::exception& e) {
    std::cerr << e.what() << std::endl;
  }
}

Finally クラスは単にfinally句を実現する以外の用途にも転用可能である. よくあるのがC言語APIで,いくつかの初期化関数と終了処理関数をセットにして呼び出さなければならない場面だ. std::fopen()std::fclose() のような管理ポインタを返す関数であればスマートポインタを利用すればよい話であるが,全てが全てポインタを返却するような関数でないことがある.

例えば,C言語的な関数 init1()close1()init2()close2()init3()close3() が対応しているとしよう. そして,init1()init2()init3() の呼び出しの後に,目的の処理関数 doHoge() を呼び出す場面を考えると以下のようなコードになる.

void
func()
{
  if (init1() != SUCCESS) {
    return;
  }
  if (init2() != SUCCESS) {
    close1();
    return;
  }
  if (init3() != SUCCESS) {
    close2();
    close1();
    return;
  }

  doHoge();

  close3();
  close2();
  close1();
}

Win32 API等のバリバリのC言語関数を扱っているコードにこういうコードが見られることがあるかもしれない.

途中で1つでも失敗すれば,対応する終了処理関数を呼び出さなくてはならないため,同じ終了処理関数呼び出しを並べることになる. 宗教的・盲目的にgotoが禁止されていれば上記のようなコードを書かざるを得ないのである.

これを Finally クラスを用いて書き直すと以下のようになる.

void
func()
{
  if (init1() != SUCCESS) {
    return;
  }
  auto f1 = makeFinally([]{
    close1();
  });

  if (init2() != SUCCESS) {
    return;
  }
  auto f2 = makeFinally([]{
    close2();
  });

  if (init3() != SUCCESS) {
    return;
  }
  auto f3 = makeFinally([]{
    close3();
  });

  doHoge();
}

初期化処理のすぐ後に終了処理関数を書くことができ,途中で return したときの終了処理関数の呼び忘れを心配する必要が無くなる. スッキリとした記述になり,事故防止にもつながるのである. ちなみに,この例でわかる通り,Finally クラスはGoで言うところの defer に相当することがわかると思う.

余談

Finally クラスは継承を用いて実装することもできる.

template<typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
Finally
  : private F
{
public:
  explicit Finally(F&& f) noexcept
    : F(std::forward<F>(f))
  {}

  ~Finally()
  {
    F::operator()();
  }

  Finally(const Finally&) = delete;

  Finally(Finally&&) = default;

  Finally&
  operator=(const Finally&) = delete;

  Finally&
  operator=(Finally&&) = default;

  static void*
  operator new(std::size_t) = delete;

  static void*
  operator new(std::size_t, ...) = delete;

  static void
  operator delete(void*) = delete;

  static void
  operator delete(void*, ...) = delete;
};  // class Finally


template<typename F>
static inline Finally<F>
makeFinally(F&& f) noexcept
{
  return Finally<F>{std::forward<F>(f)};
}

ただし,この場合は関数ポインタや final 指定のある関数オブジェクトは指定できない. ラムダとfinal 指定のない関数オブジェクトのみを受け取ることができる.

まぁ,ラムダ式を渡す場合がほとんどだと思うので,この実装でもさほど困らないと思うが.

まとめ

C++はctorとdtorによるRAIIにより,finally句が必要無い. この記事で紹介した Finally クラスは単なるfinally句だけではなく,もっと幅広いリソースの獲得と破棄処理に用いることができる.

多次元の std::array を楽に扱う

はじめに

前回の記事では,多次元の std::vector について書いた. 今回は多次元の std::array について書こうと思う.

まず,std::array は組み込み配列と同等の機能を提供するクラスである(というより,組み込み配列のラッパークラスである). 使用方法としては std::array<int, 4> arr のように,第1テンプレート引数に要素型,第2テンプレート引数に要素数を渡す. std::array<int, 4> arrint arr[4] に相当する宣言となる.

しかし,std::array を多次元にする場合を考えると,

std::array<std::array<std::array<int, 30>, 20>, 10> arr;

と宣言が長い宣言が必要になる. また,上記の3次元の std::array と同等の組み込み配列は int arr[10][20][30] であり,要素数の順が逆になっている.

この記事では,これらの問題を解決することについて書く.

実装

以下のコードがこの記事に書きたいことの全てである.

#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>


struct is_range_impl
{
  template<typename T>
  static auto
  check(T&& obj) -> decltype(std::begin(obj), std::end(obj), std::true_type{});

  template<typename T>
  static auto
  check(...) -> std::false_type;
};  // struct is_range_impl

template<typename T>
class is_range :
  public decltype(is_range_impl::check<T>(std::declval<T>()))
{};  // class is_range


template<
  typename R,
  typename T,
  typename std::enable_if<
    is_range<R>::value && !is_range<typename std::iterator_traits<decltype(std::begin(std::declval<R>()))>::value_type>::value,
    std::nullptr_t
  >::type = nullptr
>
static inline void
fill(R&& range, T&& value) noexcept
{
  std::fill(std::begin(range), std::end(range), std::forward<T>(value));
}


template<
  typename R,
  typename T,
  typename std::enable_if<
    is_range<R>::value && is_range<typename std::iterator_traits<decltype(std::begin(std::declval<R>()))>::value_type>::value,
    std::nullptr_t
  >::type = nullptr
>
static inline void
fill(R&& range, T&& value) noexcept
{
  for (auto&& e : range) {
    fill(std::forward<decltype(e)>(e), std::forward<T>(value));
  }
}


template<
  typename T,
  std::size_t kN,
  std::size_t... kSizes
>
struct ndarray_impl
{
  using type = std::array<typename ndarray_impl<T, kSizes...>::type, kN>;
};  // struct ndarray_impl

template<
  typename T,
  std::size_t kN
>
struct ndarray_impl<T, kN>
{
  using type = std::array<T, kN>;
};  // struct ndarray_impl

template<typename T, std::size_t kN, std::size_t... kSizes>
using NdArray = typename ndarray_impl<T, kN, kSizes...>::type;


int
main()
{
  NdArray<int, 4> arr1;
  fill(arr1, 0);
  for (const auto& e : arr1) {
    std::cout << e << " ";
  }
  std::cout << "\n\n";

  NdArray<int, 4, 4> arr2;
  fill(arr2, -1);
  for (const auto& e1 : arr2) {
    for (const auto& e2 : e1) {
      std::cout << e2 << " ";
    }
    std::cout << "\n";
  }
  std::cout << "\n";

  NdArray<int, 4, 4, 4> arr3;
  fill(arr3, 114514);
  for (const auto& e1 : arr3) {
    for (const auto& e2 : e1) {
      for (const auto& e3 : e2) {
        std::cout << e3 << " ";
      }
      std::cout << "\n";
    }
    std::cout << "\n";
  }
  std::cout << "\n";

  return 0;
}

std::array はテンプレート引数に要素数が必要なので,前回の記事NdVector とは異なり, NdArray<int, 10, 20, 30> とする必要がある. NdVector<int, 10, 20, 30> arr;int arr[10][20][30]; と同等であり,組み込み配列と遜色無い使用感になっていると思う.

なお,組み込み配列と同様に std::array 生成時に要素は初期化されないので,ローカル変数で使う分には初期化が必要となる. std::array は組み込み配列のみをメンバー変数に持つラッパークラスであり,全次元を通して領域が連続していることを利用して,

NdAarray<int, 3, 4, 5> arr;
std::fill(
  reinterpret_cast<int*>(arr.data()),
  reinterpret_cast<int*>(arr.data() + arr.size()),
  0);

のようにしてしまうのもアリだが,お行儀が悪いので,ちゃんとRange-based forでループを行って初期値を入れる関数 fill() を用意した.

なお,この fill() は他の多次元のものに対しても利用可能であるので,例えば多次元の組み込み配列にも適用可能である.

int arr[3][4][5][6];
fill(arr, 0);

当然,前回の記事の NdVector にも適用可能である. (各関数,クラスの実装は前回の記事を参照)

auto nv = makeNdVector(3, 4, 5, -1);

std::cout << "nv =\n[";
for (const auto& e1 : arr3) {
  std::cout << "  [\n";
  for (const auto& e2 : e1) {
    std::cout << "    [";
    for (const auto& e3 : e2) {
      std::cout << e3 << ", ";
    }
    std::cout << "],\n";
  }
  std::cout << "  ],\n";
}
std::cout << "]\n";


fill(nv, 0);

std::cout << "nv =\n[";
for (const auto& e1 : arr3) {
  std::cout << "  [\n";
  for (const auto& e2 : e1) {
    std::cout << "    [";
    for (const auto& e3 : e2) {
      std::cout << e3 << ", ";
    }
    std::cout << "],\n";
  }
  std::cout << "  ],\n";
}
std::cout << "]\n";

他にも多次元の std::list にも fill() を適用することが可能である.

別実装

いなむ神に以下のような実装を教えていただいた.

#include <array>


template<typename T, std::size_t N, std::size_t... Extents>
struct extents_expander
  : extents_expander<std::array<T, N>, Extents...>
{};  // struct extents_expander

template<typename T, std::size_t N>
struct extents_expander<T, N>
{
  using type = std::array<T, N>;
};  // struct extents_expander

template<typename T, std::size_t... Extents>
struct ndarray_helper
{
  using type = typename extents_expander<T, Extents...>::type;
};  // struct ndarray_helper

template<typename T, std::size_t N, std::size_t... Extents>
struct ndarray_helper<T[N], Extents...>
{
  using type = typename ndarray_helper<T, N, Extents...>::type;
};  // struct ndarray_helper

template<typename T>
using NdArray = typename ndarray_helper<T>::type;

これは以下のように使用できる.

NdArray<int[10][20][30]> arr;

こちらの方が直感的であると感じた.

まとめ

多次元 std::array の型の記述を簡単にするエイリアステンプレートの実装と,初期化関数を紹介した. 工夫すれば,多次元の std::array は多次元の組み込み配列と同じぐらい容易に扱うことが可能になる.

多次元の std::vector を楽に扱う

はじめに

C++には std::vector という動的配列を扱うクラスが用意されている. このクラスはよく利用され,時には std::vectorstd::vector,すなわち多次元の std::vecotr が用いられることがある.

しかし,この多次元の std::vector

std::vector<std::vector<int>> vct2d;

のように長い型宣言を伴うのと,初期サイズを指定する場合,

std::vector<std::vector<int>> vct2d(5, std::vector<int>(10));

のような記述となり,なかなかに煩雑である.

この記事では,上記のような多次元 std::vector をある程度楽に扱えるようにすることについて記述する.

多次元の std::vector を生成する関数

まずは実装を紹介する.

#include <vector>
#include <type_traits>
#include <utility>


template<
  typename T,
  typename U
>
static inline std::vector<U>
makeNdVector(T&& n, U&& val) noexcept
{
  static_assert(std::is_integral<T>::value, "[makeNdVector] 1st argument must be an integer type");
  return std::vector<U>(std::forward<T>(n), std::forward<U>(val));
}


#if __cplusplus >= 201402L
template<
  typename T,
  typename... Args
>
static inline decltype(auto)
makeNdVector(T&& n, Args&&... args) noexcept
{
  static_assert(std::is_integral<T>::value, "[makeNdVector] 1st argument must be an integer type");
  return std::vector<decltype(makeNdVector(std::forward<Args>(args)...))>(std::forward<T>(n), makeNdVector(std::forward<Args>(args)...));
}
#else
template<
  typename T,
  typename... Args
>
static inline auto
makeNdVector(T&& n, Args&&... args) noexcept
  -> decltype(std::vector<decltype(makeNdVector(std::forward<Args>(args)...))>(std::forward<T>(n), makeNdVector(std::forward<Args>(args)...)))
{
  static_assert(std::is_integral<T>::value, "[makeNdVector] 1st argument must be an integer type");
  return std::vector<decltype(makeNdVector(std::forward<Args>(args)...))>(std::forward<T>(n), makeNdVector(std::forward<Args>(args)...));
}
#endif


#include <iostream>


int
main()
{
  // 10x5 の 全要素が 1 の 2次元vectorを生成
  auto vct2d = makeNdVector(5, 10, 1);
  for (std::size_t i = 0; i < 5; i++) {
    for (std::size_t j = 0; j < 10; j++) {
      std::cout << vct2d[i][j] << " ";
    }
    std::cout << "\n";
  }

  return 0;
}

C++11でもコンパイル可能なように,返り値の型を懇切丁寧に記述したものも用意した.

makeNdVector() 関数は,std::vector のコンストラクタと同様に扱えるように,一番最後の要素が全要素の初期値とする値にし,他は各次元における要素数とした. 要素数の順は多次元の組み込み配列と同じになるようにしている. 例えば,int arr[10][20][30] に対応するのは makeNdVector(10, 20, 30, 0); である.

多次元 std::vector の型の簡略化

多次元 std::vector を生成する関数の戻り値を auto で受け取る分には問題ないが,他の関数に渡すとなったときに void f(const std::vector<std::vector>& vct) と書かなくてはならない問題が残っている. そこで,型を簡略に記述できるようにしてみる.

#include <type_traits>
#include <vector>


template<
  typename T,
  std::size_t N,
  typename std::enable_if<(N > 0), std::nullptr_t>::type = nullptr
>
struct ndvector_impl
{
  using type = std::vector<typename ndvector_impl<T, N - 1>::type>;
};  // struct ndvector_impl


template<typename T>
struct ndvector_impl<T, 1>
{
  using type = std::vector<T>;
};  // struct ndvector_impl


template<
  typename T,
  std::size_t N
>
using NdVector = typename ndvector_impl<T, N>::type;


int
main()
{
  static_assert(std::is_same<NdVector<int, 1>, std::vector<int>>::value, "NG");
  static_assert(std::is_same<NdVector<double, 2>, std::vector<std::vector<double>>>::value, "NG");
  static_assert(std::is_same<NdVector<int, 4>, std::vector<std::vector<std::vector<std::vector<int>>>>>::value, "NG");

  return 0;
}

上記のコードに示す通り,例えば std::vector<std::vector<int>>NdVector<int, 2> と書けるようになる. これで関数の引数として型を記述するのも楽になる.

#include <vector>
#include <type_traits>
#include <utility>


template<
  typename T,
  typename U
>
static inline std::vector<U>
makeNdVector(T&& n, U&& val) noexcept
{
  static_assert(std::is_integral<T>::value, "[makeNdVector] The 1st argument must be an integer");
  return std::vector<U>(std::forward<T>(n), std::forward<U>(val));
}


template<
  typename T,
  typename... Args
>
static inline decltype(auto)
makeNdVector(T&& n, Args&&... args) noexcept
{
  static_assert(std::is_integral<T>::value, "[makeNdVector] The 1st argument must be an integer");
  return std::vector<decltype(makeNdVector(std::forward<Args>(args)...))>(std::forward<T>(n), makeNdVector(std::forward<Args>(args)...));
}


template<
  typename T,
  std::size_t N,
  typename std::enable_if<(N > 0), std::nullptr_t>::type = nullptr
>
struct ndvector_impl
{
  using type = std::vector<typename ndvector_impl<T, N - 1>::type>;
};  // struct ndvector_impl


template<typename T>
struct ndvector_impl<T, 1>
{
  using type = std::vector<T>;
};  // struct ndvector_impl


template<
  typename T,
  std::size_t N
>
using NdVector = typename ndvector_impl<T, N>::type;


#include <iostream>


static inline void
showAllElement(const NdVector<int, 2>& vct2d) noexcept
{
  for (const auto& row : vct2d) {
    for (const auto& col : row) {
      std::cout << col << " ";
    }
    std::cout << "\n";
  }
}


int
main()
{
  auto vct2d = makeNdVector(5, 10, 1);
  showAllElement(vct2d);

  return 0;
}

(どうでもいいけど,何故かメタ関数はスネークケース,インスタンス作ったりするクラスはパスカルケースで書きたい気持ちがあるんだよなぁ)

まとめ

多次元 std::vector を簡単に生成する関数と,型の記述を簡単にするエイリアステンプレートの実装を紹介した.

なお,この記事で紹介した方法では std::vector の第2テンプレート引数(メモリアロケータ)を指定できるようにはなっていないが,各次元において別のメモリアロケータを指定する場合などを考えると複雑であるし,そもそもメモリアロケータを指定したい人がわざわざ要素アクセス速度の遅い多次元の std::vector を使うとは思えないので省略した. (多次元 std::vector はいわゆるジャグ配列なので,全次元を通してメモリが連続に確保されるとはいえないので,キャッシュ効率の観点から不利なのは明らか)

競技プログラミングとC++のアレコレ

はじめに

この記事は,C++初心者だけど競技プログラミングC++を使っている,C++競技プログラミングをやってみようと思っている人に向けた記事である. 「C++初心者」対象であって,プログラミングそのものが初心者である人向けではないかもしれない.

なるべくC++11で可能な範囲で記述している. (最近の各種ジャッジサーバーではC++14も使えるからあんまりC++11にこだわる必要もないのだが一応)

なお,この記事は気が向いたきに不定期に更新される可能性が高い.

using namespace std;

競技プログラミングではタイプ量を少なくするために,using namespace std; というおまじないを書き,std:: を書かなくてもよいようにする.

#include <iostream>

using namespace std;

int
main()
{
  // std::cout << 42 << std::endl; と書かなくてよくなる
  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::coutstd::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/ 以下にプリコンパイル済みヘッダが作成される.

#!/bin/sh -eu

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つインクルードする競プロテンプレートを用意しておいた方が便利なこともある. 以下は標準ライブラリヘッダの羅列である. ただし,明らかに競プロに使わないであろうものはコメントアウトしてある.

// C headers
#include <cassert>
#include <cctype>
// #include <cerrno>
#include <cfloat>
// #include <ciso646>
#include <climits>
// #include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
// #include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
// #include <cstdbool>
#include <cstdint>
// #include <ctgmath>
// #include <cuchar>
// #include <cwchar>
// #include <cwctype>
#endif
// C++ headers
#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 <atomic>
#include <chrono>
// #include <codecvt>
// #include <condition_variable>
#include <forward_list>
// #include <future>
#include <initializer_list>
// #include <mutex>
#include <random>
#include <ratio>
#include <regex>
// #include <scoped_allocator>
#include <system_error>
// #include <thread>
#include <tuple>
// #include <typeindex>
#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& の場合と生成されるコードは変わらないので,

  1. タイプ量少なめに,高速にコードを書きたい場合は auto&& オンリー
  2. 事故を防止したい,丁寧なコードを書きたい場合は 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;
// v.reserve(n);  // reserveすることでメモリの再確保の頻発は避けられる
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::ostreamSTLコンテナ間の operator<<オーバーロードを用意すればよい. ただし,全STLコンテナに対してオーバーロードを用意するのはしんどいので,テンプレートでまとめる.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <ostream>
#include <string>
#include <type_traits>


// コンテナかどうかを雑に判定するメタ関数
// メンバ関数にbegin(), end(), empty()を持っていればコンテナと判定
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;
};  // struct is_range

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 << "]";
}


// STLコンテナ用
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 << "]";
}


// std::map, std::unprdered_map等のために,std::pair用のオーバーロードも用意しておくと便利
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;
};  // class Range


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;
};  // class IntegerIterator


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;
};  // class ReversedIntegerIterator


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_MAXINT_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));  // C++03まではポインタを与えていた
std::sort(std::begin(arr), std::end(arr));  // C++11からはこう書ける

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;
  });
// 負の数が1つも無いかどうか
auto ret2 = std::none_of(
  std::begin(v),
  std::end(v),
  [](const decltype(v)::value_type& e){
    return e < 0;
  });
// 1つでも3の倍数があるかどうか
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);  // 0
auto maxValue = std::max(0, 10);  // => 10
auto mmPair = std::max(0, 10);  // => 0と1のstd::pair

実は,3つ以上でもいける.これは std::initialize_list を取るオーバーロードがあるためである.

auto minValue = std::min({3, 1, 4, 1, 5, 9, 2, 6, 5});  // => 1
auto maxValue = std::max({1, 1, 4, 5, 1, 4});  // => 5
auto mmPair = std::minmax({2, 7, 1, 8, 2, 8, 1, 8});  // 1と8のstd::pair<int, int>

最小値,最大値の更新で次のように書くことはよくある.

// valueは適当な値
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>{});
// C++14では以下のように書ける
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};
// C++11ではstd::rbegin()とstd::rend()が無いので,組み込み配列アドレスを渡すしかない.
std::sort(arr, arr + (sizeof(a) / sizeof(a[0])), std::greater<decltype(a[0])>{});
// C++14では以下のように書ける
// std::sort(std::rbegin(v), std::rendl(v));

第三引数に比較関数を指定することができる. 以下は第三引数に比較関数を指定しているが,何も指定しない場合と同等の処理である.

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::pairstd::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);  // => 0で埋める

std::fill_n は指定した個数だけ指定した値で埋める. 基本的にポインタ引数を与えて用いる.

// pはint*
static constexpr int INF = 0x3f3f3f3f;
std::fill_n(p, 10, INF);  // => p[0]からp[9]まで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;
  });
// C++14以降なら,[](const auto& e){ ... } でよい
// また,constは無くてもよい

とするとよい.

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);
// vを0,3,6,9,12...で初期化
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 longdouble などにして,オーバーフローが発生しないように気をつける必要がある. (例えば, 0LL0.0 にするなど)

第4引数で各要素を足し合わせるときのアクションを指定できる. まず,第4引数を指定しない場合と同等の処理は,

std::vector<int> v{1, 2, 3, 4, 5};
std::accumulate(
  std::begin(s),
  std::end(s),
  0,
  // 第1引数が合計値,第2引数が要素
  [](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,
  // 第1引数が合計値,第2引数が要素
  [](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_argumentstd::out_of_rage を分けて実装する必要がなければ,

try {
  // ...
} catch (const std::exception& e) {

}

のようにまとめて例外を補足してもいいし,そもそも補足せずに上位の関数任せにしてもよい.

逆に数値から文字列にするには std::to_string() 関数を用いればよい.

auto s = std::to_string(123);  // s は "123"

数値から文字列に

C++11で,std::to_string() という関数が標準ライブラリに加わったので,それを利用する.

文字列から数値に

大文字・小文字変換

<algorithm>std::transform()<cctype>::toupper(), ::tolowerC言語関数)を利用する.

// 大文字化
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(), ::tolowerC言語関数であり,いちいち関数コールが発生するようなコード生成がなされるので,以下のように自前の関数を書く方がよいかもしれない.

// 大文字化
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+"};  // std::sregex_token_iteratorに即値として渡してはならない
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+"};  // std::sregex_token_iteratorに即値として渡してはならない
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::sregex_token_iteratorに即値として渡してはならない
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::sregex_token_iteratorに即値として渡してはならない
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::sregex_token_iteratorに即値として渡してはならない
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::sregex_token_iteratorに即値として渡してはならない
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 クラスを用いる.

#include <utility>


template<typename F>
class FixPoint : F
{
public:
  explicit constexpr FixPoint(F&& f) noexcept
    : F(std::forward<F>(f))
  {}

  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};  // class FixPoint


template<typename F>
static inline constexpr decltype(auto)
makeFixPoint(F&& f) noexcept
{
  return FixPoint<F>{std::forward<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;
}

無名再帰の利点はローカル変数のキャプチャができる点である.

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;
};  // class Finally


#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;
};  // class Finally

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));
    // 以下のようなクラステンプレートの型推論はC++17から
    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つの特徴がある.

  1. 変数の初期化は最初の関数呼び出し時の一度のみ行われる
  2. 2度目以降の関数呼び出しを行ったとき,前の呼び出し時の値が残っている

この特徴は次のコードで確認できる.

#include <iostream>

void
countup() noexcept
{
  static int cnt = 10;  // この = 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であってもlongx86なら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::printfstd::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;
  }
  // 16進数で表示
  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() の返却値と同じ型を使うべきである. 個人的には,可能な限り autodecltype を用いて,元の型を崩さないようにしておくべきであると思う.

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>

デバッグ (gcc)

よくわからないけどアクセス違反で落ちるとき

-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[300] だと関数の管理領域外なので,この関数のreturn時にはおそらく検出不可能
  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

こういうのはエイリアスで定義しておくと便利だと思われる.

C++の配列・STLコンテナで区切り文字を入れてostreamに出力する

はじめに

C++において,たまに std:coutstd:ofstreamstd::ostringstream といった出力ストリームに,配列や std::vector の要素を何かの区切り文字を入れて出力したいことがある. この「区切り文字を入れて出力」というのは少々面倒で,末端要素の後に区切り文字を入れないようにしないといけない. 可能な限り,そういった処理を簡潔に記述したいものである.

for

インデックスベースのforを利用するなら以下のように書くだろう.

#include <iostream>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  if (!v.empty()) {
    for (decltype(v)::size_type i = 0; i < v.size() - 1; i++) {
      std::cout << v[i] << ",";
    }
    std::cout << v[v.size() - 1] << std::endl;
  }

  return 0;
}

std::ostream_iterator

<algorithm>std::copy()<iterator>std::ostream_iterator を利用する方法がある. 個人的にはこの方法が一番良いと思う.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  if (!v.empty()) {
    std::copy(
      std::cbegin(v),
      std::prev(std::cend(v)),
      std::ostream_iterator<const decltype(v)::value_type&>(std::cout, ","));
    std::cout << *std::crbegin(v) << std::endl;
  }

  return 0;
}

例のごとく,C++11にはフリー関数の cbegin(), cend(), crbegin() が無い. この程度で別にconstイテレータを取得する必要はないので, cbegin(), cend()begin(), end()を,crbegin()rbegin() メンバ関数を利用する.

#include <algorithm>
#include <iterator>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  if (!v.empty()) {
    std::copy(
      std::begin(v),
      std::prev(std::end(v)),
      std::ostream_iterator<const decltype(v)::value_type&>(std::cout, ","));
    std::cout << *v.rbegin() << std::endl;
  }

  return 0;
}

std::experimental::ostream_joiner

標準ライブラリではないが,試験的機能の1つとして std::experimental::ostream_joiner というものが存在する. gccであればバージョン6.1.0以上,clangであればバージョン3.9.1以上であれば利用可能であることは確認した. そして,当然のようにMSVCでは利用できない.

この ostream_joiner には型推論のためのフリー関数テンプレートである std::experimental::make_ostream_joiner() も存在するので,それを利用する.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#include <experimental/iterator>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::copy(
    std::cbegin(v),
    std::cend(v),
    std::experimental::make_ostream_joiner(std::cout, ","));
  std::cout << std::endl;

  return 0;
}

Range-based forで何とかする

前回の記事Range クラスを利用する.

#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>


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;
};  // class Range


template<typename Iterator>
static inline Range<Iterator>
makeRange(Iterator&& begin, Iterator&& end) noexcept
{
  return Range<Iterator>{std::forward<Iterator>(begin), std::forward<Iterator>(end)};
}


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  if (!v.empty()) {
    for (const auto& e : makeRange(std::cbegin(v), std::prev(std::cend(v)))) {
      std::cout << e << ",";
    }
    std::cout << *std::crbegin(v) << std::endl;
  }

  return 0;
}

Range-based forで逆順走査したい

はじめに

C++を書いていると,Range-based forで逆順操作をしたいことがたまにある. Range-based forは順方向の走査のみで,逆順に走査することはできない. なので,通常のインデックスベースのforを用いて,

std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto i = v.size() - 1; i != static_cast<decltype(i)>(-1); i--) {
  std::cout << v[i] << std::endl;
}

と書いたり,イテレータを利用して,

std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto itr = std::rbegin(v); itr != std::rend(v); ++itr) {
  std::cout << *itr << std::endl;
}

と書いたりする.

だが,このようなループにおいて欲しいのはインデックスやイテレータではなく,要素そのものが欲しい. ここにRange-based forで逆順に走査したいというモチベーションがある.

boost::adaptors::reverse

天下のBoostライブラリにはまさにそういうものがある.

#include <iostream>
#include <vector>

#if defined(__GNUC__) && __GNUC_PREREQ(4, 6)
#  pragma GCC diagnostic push
#  pragma GCC diagnostic ignored "-Wconversion"
#  pragma GCC diagnostic ignored "-Weffc++"
#  pragma GCC diagnostic ignored "-Wparentheses"
#  if __cplusplus >= 201103L
#    pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
#    if __GNUC_PREREQ(5, 0)
#      pragma GCC diagnostic ignored "-Wsuggest-override"
#    endif  // __GNUC_PREREQ(5, 0)
#  endif  // __cplusplus >= 201103L
#endif  // defined(__GNUC__) && __GNUC_PREREQ(4, 6)
#include <boost/range/adaptors.hpp>
#if defined(__GNUC__) && __GNUC_PREREQ(4, 6)
#  pragma GCC diagnostic pop
#endif  // defined(__GNUC__) && __GNUC_PREREQ(4, 6)

int
main()
{
  std::vector v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (const auto& e : boost::adaptors::reverse(v)) {
    std::cout << e << std::endl;
  }

  return 0;
}

ワーニングオプションを盛り沢山にしていると,Boostからそれなりにワーニングが出てくるので,ある程度抑えるようにしておいた.

boostを使わずにやりたい

場合によっては,boostに頼らずにやりたいこともあると思われる. range-based forが受理するのは,begin()end() というメンバ関数を持つクラスのインスタンスである. なので,以下のようにしてみる.

#include <iostream>
#include <iterator>
#include <type_traits>
#include <vector>


// C++11ではrbegin(), rend()を持つかどうかを判定するメタ関数
// C++14以降では,std::rbegin(), std::rend()に受理されるかどうかを判定するメタ関数
template<typename T>
struct has_rbegin_rend
{
private:
  template<typename U>
  static auto
#if __cplusplus >= 201402L
  check(U&& obj) -> decltype(std::rbegin(obj), std::rend(obj), std::true_type{});
#else
  check(U&& obj) -> decltype(obj.rbegin(), obj.rend(), std::true_type{});
#endif

  static std::false_type
  check(...);

public:
  static constexpr bool value = decltype(check(std::declval<T>()))::value;
};


#if __cplusplus >= 201402L
template<typename T>
constexpr bool has_rbegin_rend_v = has_rbegin_rend<T>::value;
#endif


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;
};  // class Range


template<typename Iterator>
static inline Range<Iterator>
makeRange(Iterator&& begin, Iterator&& end) noexcept
{
  return Range<Iterator>{std::forward<Iterator>(begin), std::forward<Iterator>(end)};
}


#if __cplusplus >= 201402L
// std::initiaizer_listをわざわざ逆順にしたい人は皆無だと思うけど,一応...
template<typename T>
static inline decltype(auto)
makeReversedRange(const std::initializer_list<T>& iniList) noexcept
{
  return makeRange(std::rbegin(iniList), std::rend(iniList));
}


template<
  typename T,
  typename std::enable_if_t<has_rbegin_rend_v<T>, std::nullptr_t> = nullptr
>
static inline decltype(auto)
makeReversedRange(T&& c) noexcept
{
  return makeRange(std::rbegin(c), std::rend(c));
}
#else
template<typename T>
static inline auto
makeReversedRange(const std::initializer_list<T>& iniList) noexcept
  -> decltype(makeRange(iniList.rbegin(), iniList.rend()))
{
  return makeRange(iniList.rbegin(), iniList.rend());
}


template<
  typename T,
  typename std::enable_if<has_rbegin_rend<T>::value, std::nullptr_t>::type = nullptr
>
static inline auto
makeReversedRange(T&& c) noexcept
  -> decltype(makeRange(c.rbegin(), c.rend()))
{
  return makeRange(c.rbegin(), c.rend());
}
#endif


// rbegin(), rend()を持たないものはこっちに分岐させて,エラーメッセージを少なくする
template<
  typename T,
  typename std::enable_if<!has_rbegin_rend<T>::value, std::nullptr_t>::type = nullptr
>
static inline void
makeReversedRange(T&&) noexcept
{
  static_assert(has_rbegin_rend<T>::value, "Specified argument doesn't have reverse iterator.");
}


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (const auto& e : makeReversedRange(v)) {
    std::cout << e << std::endl;
  }

  return 0;
}

どうしてもC++11でなくてはならないときに備えて,C++11でもコンパイルが通るようにした. (この部分のコードを削除すれば,上記コードは少し短くなるだろう.) C++11はフリー関数版の rbegin()rend() が無いので,メンバ関数を呼び出すようにしている. そのため上記コードは,C++11において,組み込み配列の逆順走査はできない. わざわざ フリー関数の rbegin()rend() を実装するのは面倒なので,その点は妥協した.

また, makeReversedRange に,STLコンテナや配列以外を与えた場合のコンパイルエラーメッセージを抑えるため,SFINAEを利用している. その部分も省けば,上記コードはもっと短くなる.

おまけ

本記事の趣旨とは外れるが,そもそも std::for_each() で逆順走査ができる. C++14以降なら,

#include <algorithm>
#include <iostream>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::for_each(std::rbegin(v), std::rend(v), [](const auto& e){
    std::cout << e << std::endl;
  });

  return 0;
}

で,C++11なら,

#include <algorithm>
#include <iostream>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::for_each(v.rbegin(), v.rend(), [](const decltype(v)::value_type& e){
    std::cout << e << std::endl;
  });

  return 0;
}

と書ける. だが,どうしてもRang-based forで書きたいのだ!という人達もいるはずである(ホンマか?)

一応,std::for_each() のRange-based forに劣る点を挙げるならば,

  1. イテレータの指定が必要な分,どうしてもユーザコードが膨れ上がる.
  2. C++11にはジェネリックラムダが無いため,forの処理部分のラムダの引数の記述が冗長になりがちである.

の2点がある.

まとめ

  1. Boost.Range の boost::adaptors::reverse()STLコンテナ等を渡せば,簡単に逆順走査できる
  2. boost::adaptors::reverse() 相当のものは簡単に作れる

C++のラムダで再帰する

はじめに

C++において,ラムダで再帰したいと考えることはたまにある. この記事ではラムダで再帰する手法をいくつか紹介する. 例として扱う再帰関数はフィボナッチ数列の関数(もっとも単純な実装)とする.

int
fib(int n) noexcept
{
  return n < 2 ? n : (fib(n - 1) + fib(n - 2));
}

生成コード

ラムダで再帰を行いたいと考えるのは変数のキャプチャをしつつ再帰をしたい場面であると思う. 例えば,メモ化再帰を行うと考えた場合,

  1. グローバル変数としてメモ化配列を用意する
  2. メモ化再帰用のクラスを用意する(メンバにメモ化配列を用意する)
  3. 再帰関数の引数にメモ化配列を与える

といった方法が考えられるが,グローバル変数や専用のクラス定義が必要であり,あまりやりたくない. 引数にメモ化配列を与えるとなると,全ての再帰呼び出し箇所の記述が冗長になってしまう. ラムダで再帰ができれば,ローカル変数にメモ化用の配列を用意してもキャプチャできるようになるため,スッキリすると思われる.

3つの手法

この記事ではラムダで再帰を実現する手法を3つ紹介する.

1. std::function による無名再帰

C++11でない限り,絶対に使うべきではない

実装としては以下の通り.

#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 << std::endl;
}

生成コード

利点と欠点は以下の通り.

利点

  1. C++11でも使用可能

欠点

  1. std::function を用いるため,実行コストが大きい(速度)
  2. std::function を用いるため,再帰可能深度が小さい
  3. 無名にできない
  4. std::function とラムダそのものに引数等の返り値を書く必要があり冗長

なぜかC++関連の記事を見ていると,この手法を紹介している記事が目につくのだが,言うまでもなく std::function を用いているのがとにかく良くない. よく知られている通り,std::function は型消去を行うため,与えた関数をインライン展開できない,実行コストが大きいといった欠点を持つ. std::functionoperator() の実装,あるいは生成されるコードを見ればわかるように( std::function 自体の operator() はインライン展開されるので,g++で -S --verbose-asm のようなオプションを付けてアセンブリを吐かせ,呼び出し部分のコードを確認すれば見てとれる),

  1. 保持している関数が有効かどうか(関数を保持しているかどうか)をチェックするコードが operator() に含まれる
  2. 関数が有効でない場合の, std::bad_function_call 例外を投げるためのコードが含まれる

といった欠点がある.これらの理由により,1回の関数呼び出しに時間がかかるだけでなく,消費スタック量が大きく,再帰可能深度が小さくなる. そのため,C++11でない限りは使うべきではない. 強いて利点を挙げるならば,下準備に必要な関数およびクラスがないため,ゼロからコードを書く場合には楽という利点はあるかもしれない.

本記事の「ラムダで再帰」に限った話ではなく,std::function を使用するべきかどうかは慎重にならなければならない. autoやテンプレートの型パラメータを用いることによって,いかにラムダをラムダのまま保持するかを考えるべきだ.

2. ジェネリックラムダを用いる方法

実装としては以下の通り. 可変引数はとりあえず完全転送すればよい.

#include <iostream>
#include <utility>


template<typename F>
static inline constexpr decltype(auto)
fix(F&& f) noexcept
{
  return [f = std::forward<F>(f)](auto&&... args) {
    return f(f, std::forward<decltype(args)>(args)...);
  };
}


int
main()
{
  auto result = fix([](auto f, int n) -> int {
    return n < 2 ? n : (f(f, n - 1) + f(f, n - 2));
  })(10);
  std::cout << result << std::endl;
}

生成コード

利点と欠点は以下の通り.

利点

  1. 実行コストは小さい
  2. 無名再帰可能
  3. C++17以降ではコンパイル時計算可能なラムダによる再帰関数を記述可能

欠点

  1. C++14以降
  2. 再帰関数の引数にその再帰関数自身を与える必要があるため,関数本体の記述が冗長.

この手法はこの記事のものである. ジェネリックラムダを用いる必要があるため,C++14以降でなければならない. 2018年の今となっては困ることはないと思うが,例えば競プロのジャッジサーバがC++11までしか対応していない場面では利用できない.

std::function を用いる方法と違い,ラムダをラムダのまま保持しているので,関数呼び出しのコストは小さい. C++17以降では,ラムダが constexpr に対応するため,コンパイル時計算が可能となる. これは上記コードの auto resultconstexpr auto result に書き換えて,C++17対応のコンパイラコンパイルすれば確認できる.

3. ジェネリックラムダと operator() を用いる方法

実装としては以下の通り.

#include <iostream>
#include <utility>


template<typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint : F
{
public:
  explicit constexpr FixPoint(F&& f) noexcept
    : F(std::forward<F>(f))
  {}

  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};  // class FixPoint


template<typename F>
static inline constexpr decltype(auto)
makeFixPoint(F&& f) noexcept
{
  return FixPoint<F>{std::forward<F>(f)};
}


int
main()
{
  auto result = makeFixPoint([](auto f, int n) -> int {
    return n < 2 ? n : (f(n - 1) + f(n - 2));
  })(10);
  std::cout << result << std::endl;
}

生成コード

利点

  1. 実行コストは小さい
  2. 無名再帰可能
  3. C++17以降ではコンパイル時計算可能なラムダによる再帰関数を記述可能

欠点

  1. C++14以降

手法としてはこれがベストである. 2つ目の手法異なり,再帰関数の引数にその再帰関数自身を与える必要もない.

類似する実装として,こういうものがあるが,これでは2つ目の手法と変わりない. ラムダの第一引数に FixPoint クラスのオブジェクトを与える(すなわち, *this を与える)ように, FixPoint::operator() を定義するのがポイントである.

C++17以降では constexpr なラムダでコンパイル時計算可能であるが,C++14でも constexpr な関数オブジェクトを用意すれば一応コンパイル時計算は可能である. ラムダではないので,本記事の趣旨とは外れるが....

#include <iostream>
#include <utility>


template<typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint : F
{
public:
  explicit constexpr FixPoint(F&& f) noexcept
    : F(std::forward<F>(f))
  {}

  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};  // class FixPoint


template<typename F>
static inline constexpr decltype(auto)
makeFixPoint(F&& f) noexcept
{
  return FixPoint<F>{std::forward<F>(f)};
}


class Fib
{
public:
  template<typename F>
  constexpr int
  operator()(F&& f, int n) const noexcept
  {
    return n < 2 ? n : (f(n - 1) + f(n - 2));
  }
};  // class Fib


int
main()
{
  constexpr auto result = makeFixPoint(Fib())(10);
  std::cout << result << std::endl;
}

C++17以降ではクラステンプレートのテンプレートパラメータ推論が可能になったため,推論のためのmake関数も不要になる.

#include <iostream>
#include <utility>


template<typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint : F
{
public:
  explicit constexpr FixPoint(F&& f) noexcept
    : F(std::forward<F>(f))
  {}

  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};  // class FixPoint


int
main()
{
  auto result = FixPoint{[](auto f, int n) -> int {
    return n < 2 ? n : (f(n - 1) + f(n - 2));
  }}(10);
  std::cout << result << std::endl;
}

おまけの話題

FixPoint の実装

3つ目の手法ではラムダを継承して FixPoint を実装したが,別にメンバーにラムダを持つ実装でもよい. 僕個人としては,ラムダを継承する方がスッキリしていると感じたのと,次の章のオーバーロード実装を考えると継承の方を紹介するのが自然と考えた.

実は継承を用いる方法はいなむ神に教えていただいた

#include <iostream>
#include <utility>


template<typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint
{
public:
  explicit constexpr FixPoint(F&& f) noexcept
    : m_f(std::forward<F>(f))
  {}

  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return m_f(*this, std::forward<Args>(args)...);
  }

private:
  const F m_f;
};  // class FixPoint


int
main()
{
  auto result = FixPoint{[](auto f, int n) -> int {
    return n < 2 ? n : (f(n - 1) + f(n - 2));
  }}(10);
  std::cout << result << std::endl;
}

再帰ラムダのオーバーロード

これもいなむ神に教えていただいたものである. C++17のusing宣言のパック展開を用いると,オーバーロードが可能となる.

#include <iostream>
#include <utility>


template<typename... Fs>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
[[nodiscard]]
#elif defined(__GNUC__) && __GNUC_PREREQ(3, 4)
__attribute__((warn_unused_result))
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint : Fs...
{
  using Fs::operator()...;

public:
  explicit constexpr FixPoint(Fs&&... fs) noexcept
    : Fs(std::forward<Fs>(fs))...
  {}

  template<typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
  {
    return operator()(*this, std::forward<Args>(args)...);
  }
};  // class FixPoint


int
main()
{
  auto fib = FixPoint{
    [](auto f, int n) -> int {
      return n < 2 ? n : (f(n - 1) + f(n - 2));
    },
    [](auto f, double n) -> double {
      return n < 2 ? n : (f(n - 1) + f(n - 2));
    }};
  std::cout << fib(10) << std::endl;
  std::cout << fib(10.0) << std::endl;
}

上記の例では double 型のオーバーロードを用意しているが,単にオーバーロード可能ということを示すためのものにすぎない.

追記 (2018/06/10)

いなむ神にラムダのみで再帰する方法を提示していただいた. ラムダのみでYコンビネータとZコンビネータを実現しており,非常に面白い. この記事で散々取り扱っているフィボナッチ数列の関数を,上記記事のYコンビネータとZコンビネータを用いて実装すると,それぞれ以下のようになる.

ラムダオンリーのYコンビネータによるフィボナッチ数列の関数の実装

#include <iostream>
#include <utility>


int
main()
{
  auto result = [g=[](auto f, int n) -> int {
    return n < 2 ? n : (f(f, n - 1) + f(f, n - 2));
  }](auto&&... args) {
    return g(g, std::forward<decltype(args)>(args)...);
  }(10);
  std::cout << result << std::endl;
}

生成コード

なお,MSVCでコンパイルしたとき,上記の実装だとMSVCがポンコツなためICEとなってコンパイルが通らないので,以下の実装を用いる方が安全かもしれない. MSVCでは初期化キャプチャでラムダをキャプチャすると,ICEとなるようだ.

#include <iostream>
#include <utility>


int
main()
{
  auto ret = [](auto f) {
    return [=](auto&&... args) {
      return f(f, std::forward<decltype(args)>(args)...);
    };
  }([](auto f, int n) -> int {
    return n < 2 ? n : f(f, n - 1) + f(f, n - 2);
  })(10);
  std::cout << ret << std::endl;
}

f:id:koturn:20180621043652p:plain

ラムダオンリーのZコンビネータによるフィボナッチ数列の関数の実装

#include <iostream>
#include <utility>


int
main()
{
  auto result = [](auto f) {
    return [=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    }([=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    });
  }([](auto f, int n) -> int {
    return n < 2 ? n : (f(n - 1) + f(n - 2));
  })(10);
  std::cout << result << std::endl;
}

生成コード

C++に不慣れな人にとっては,上記記事のZコンビネータほど複雑であれば実行効率が気になるところかもしれない(ラムダを返すラムダが云々で何となく遅そうなイメージ)が,生成コードを見れば要らぬ心配であることがわかると思う. そして,上記のYコンビネータ,Zコンビネータから生成されるコードは記事の本編で紹介した関数やクラスを用いる方法と同一のコードが生成されていることもわかる. C++はよしなにラムダのインライン展開を行ってくれるのだ!

僕はいなむ神のYコンビネータとZコンビネータの実装に感銘を受け,VimプラグインであるShougo/neosnippet.vimスニペットファイルに下記のスニペットを追加した.

snippet ycombinator
alias ycomb
  [](auto f) {
    return [=](auto&&... args) {
      return f(f, std::forward<decltype(args)>(args)...);
    };
  }([${1:&}](auto ${2:f}, ${3:#:args...}) {
    ${0}
  })

snippet zcombinator
alias zcomb
  [](auto f) {
    return [=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    }([=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    });
  }([${1:&}](auto ${2:f}, ${3:#:args...}) {
    ${0};
  })

これでいつでも再帰するラムダを楽に書ける. なお,ラムダを受ける引数はユニヴァーサル参照等の参照系で受けると単にautoで受けるよりも数命令多く,消費スタック量もわずかに多いので,いなむ神の記事の通り,autoで受けたり,コピーキャプチャを行う方が良い.

※Zコンビネータに関して:g++とMSVCではコンパイルは通るが,clang++ではコンパイルが通らないようなので気を付けてほしい.

速度比較

実際に実行時間を計測してみることにしよう. 再帰に関して,C++では様々な方法で実現することが可能であるが,この記事では,以下の4つのような関数オブジェクトによる再帰手法も紹介している. これらも含めて,実行時間を計測することにする.

class Fibonacci01
{
public:
  constexpr int
  operator()(int n) const noexcept
  {
    return n < 2 ? n : (Fibonacci01{}(n - 1) + Fibonacci01{}(n - 2));
  }
};  // struct Fibonacci01


class Fibonacci02
{
public:
  constexpr int
  operator()(int n) const noexcept
  {
    return n < 2 ? n : ((*this)(n - 1) + (*this)(n - 2));
  }
};  // struct Fibonacci02


class Fibonacci03
{
public:
  constexpr int
  operator()(int n) const noexcept
  {
    return n < 2 ? n : (operator()(n - 1) + operator()(n - 2));
  }
};  // struct Fibonacci03


class Fibonacci04
{
public:
  constexpr int
  operator()(Fibonacci04 f, int n) const noexcept
  {
    return n < 2 ? n : (f(f, n - 1) + f(f, n - 2));
  }
};  // struct Fibonacci04

この内 Fibonacci01 は本記事で紹介した FixPoint クラスによる手法と生成コードは同一であるため除外する. また Fibonacci02Fibonacci03 の生成コードは同一であり,比較する意味はないため, Fibonacci02 は除外する. 他にも,本記事において同一のコードが生成されたもの同士は意味が無いので,ユニークになるように除外して計測する.

計測に際して,以下のコードを用意した.

記事中のコードではフィボナッチ数の型を一律 int としていたが,計測コードでは std::uint64_t とした. x64環境であれば,64bitレジスタに乗せるだけなので,32bitから64bitに変更しても大きな影響はない. Wandboxは実行時間制限があるため,fib(42) をそれぞれ1回計算するコードにしてあるが,手元では fib(45) をそれぞれ5回計算するのにかかった平均時間を計測した.

使用したコンパイラは g++ 7.3.0 であり,コンパイルオプションは下記の通りである.

$ g++ -O2 -march=native main.cpp -o main.out
$ ./main.out

計測結果は以下の表に示す通りである.

手法 実行時間
普通の関数 2832.08 ms
std::function<> 7481.06 ms
fix() 省略
FixPoint クラス 2475.44 ms
FixPoint クラス (参照受け) 2715.21 ms
Yコンビネータ 省略
Zコンビネータ 省略
Fibonacci01 省略
Fibonacci02 省略
Fibonacci03 2903.60 ms
Fibonacci04 省略

つまり,

FixPoint クラス(追記のZコンビネータも含む) < FixPoint クラス(本体のラムダにおいて参照で受ける) < 普通の関数 < Fibonacci03 < std::function

という結果になった.

表の結果からも分かるように std::function は特に遅い. 普通の関数で実装したよりも3倍の実行時間を必要とする. そして,本記事で紹介したようなラムダで再帰を行う手法は,通常の関数で再帰を行う手法よりも高速である.

ただし,ラムダや関数オブジェクトを引数で受けるときに参照で受けた場合,わずかに遅くなる. 実際,参照で受ける場合のコードを確認してみると,余分なlea命令が生成されていた. 関数オブジェクトによる再帰の記事にもあるように,ラムダや関数オブジェクトはコピーで受け渡す方,あるいは都度生成する方がよいのだろう.

まとめ

  • C++11でない限り,ラムダの再帰std::function を用いるべきでない(約3倍の実行時間になる)
  • ジェネリックラムダと operator() を用いた実装を使うべき

いくつかの実装を紹介したが,C++14のジェネリックラムダによる再帰はいずれも同一のコード生成がなされ,また無駄な処理がなく,普通の関数による再帰よりも高速に動作することがわかった.

参考文献