C++ の <algorithm> 入門

はじめに

本記事は、 C++ の初心者に向けてアルゴリズムとその有用性をご紹介するものです。
自分自身の経験からも、アルゴリズムはおそらく最初のハードルが高いのではないかと思いますが、 C++ プログラマーなら知っておいて損はないと思います。

アルゴリズムとは何かは、このあとご説明します。

対象読者

• C++ の初心者
• std::vector などのコンテナは知っていて日常的に使っている方
• アルゴリズムを知らない方、あるいは知っているけどまだ使ったことがない方

アルゴリズムとは

この記事で「アルゴリズム」と呼んでいるものは、 Wikipedia の記事にあるような「選択」や「ソート」の方法や手順のことではなくて、それらを実現する具体的な関数テンプレートのことです。

たとえば、標準ライブラリが提供する std::find や std::sort などがこの記事におけるアルゴリズムの例です。
標準ライブラリのアルゴリズムのほとんどは、 <algorithm> ヘッダで提供されます^[1]。

C++ のバージョン

本記事では C++17 を対象としています。
C++11, C++14 でもそれほど変わりません。

C++20 について

C++20 では Ranges ライブラリ (<ranges> で提供される) が追加されるとともに既存のアルゴリズムも Ranges 対応しており、これまでとは違った書き方・使い方ができるようになっていますが、本記事ではそれは紹介しません。
その理由は、

• C++20 の普及度が現時点ではまだ今ひとつと思われる。
• C++17 までのアルゴリズムの使い方を知っておけば、今後 C++20 での使い方を学習する際にも簡単だと考えられる。
• これまでに書かれた大量のコードを読むには、 C++17 までのアルゴリズムの使い方を理解しておく必要がある。
• 筆者自身が C++20 のアルゴリズムの使い方にまだ慣れていない。

からです。

イテレータ

アルゴリズムを使うには、イテレータを理解しておく必要があります。
すでに理解されている方は読み飛ばしてください。

イテレータとは

イテレータ (iterator) は日本語では反復子 (はんぷくし) とも呼ばれますが、私の個人的な印象ではそのままイテレータと呼ばれることが多いです。

イテレータは、コンテナの要素を順番にたどる方法を提供します。

イテレータの使用例

と突然言われてもわからないと思うので、先に例を見てみましょう。
std::vector<int> オブジェクトの要素をひとつずつ順番に出力するコードです。

イテレータを使わない例

まずはイテレータを使わないコードです:

例 1

#include <iostream>
#include <vector>

int main() {
  std::vector<int> iv{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (std::vector<int>::size_type i{0}; i < iv.size(); ++i) {
    std::cout << iv[i] << '\n';
  }
}

std::vector::size_type は、要素の数やインデックスを表す型です。
for (int i{0}; i < iv.size(); ++i) { ... } のように int としても (通常は) 問題ありませんが、 std::vector::size() の返り値や std::vector::operator[]() の引数の型は int ではありません。

size_type i{0}; は、 size_type i = 0; と (ほぼ) 同じです。
C++11 から導入された uniform initialization を使っています。

イテレータを使った例

同じものを、イテレータを使って書いてみるとこうなります:

例 2

#include <iostream>
#include <vector>

int main() {
  std::vector<int> iv{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (std::vector<int>::iterator it{iv.begin()}, end{iv.end()}; it != end; ++it) {
    std::cout << *it << '\n';
  }
}

何やらごちゃごちゃ込み入っているように見えますが、説明のための例だからです。
実際にはこんなめんどうそうなコードを書くことはないので心配しないでください。

異なっている部分 (for 文です) を見てみましょう:

• std::vector<int>::iterator がイテレータの型です。
  イテレータは、コンテナ内のいずれかの要素を指すポインタのようなものです。
• iv.begin(), iv.end() がイテレータオブジェクトを返します。
  • begin() は先頭の要素を指すイテレータを返します。
  • end() は末尾の要素の「次」を指すイテレータを返します。
    (理由があってこのような設計になっています)
• it != end; のようにイテレータ同士は比較できます。
  両イテレータが同一の要素を指しているとき、イテレータ同士も等しくなります。
• ++it とすると、イテレータが指している要素がひとつ先に進みます。
• *it とすると、イテレータが指している要素が得られます。

つまり、

1. イテレータオブジェクト it は、はじめに iv.begin() によって iv の先頭の要素を指すように初期化され、
2. *it によって指している要素を出力し、
3. ++it によって次の要素に進みます。
4. 2～3 をくり返し、 iv の末尾の要素の次を指すイテレータオブジェクト end に到達したら終了します。

このように、イテレータを使ってコンテナの要素を順番にたどることができます。

イテレータを使う理由

ただ、イテレータを使わなくても、例 1 のようにコンテナの要素を順番にたどることはできました。
わざわざイテレータというひと手間をかけるのはなぜでしょうか。

例 1 では 0 から size() - 1 までのインデックスを使ってコンテナの要素にアクセスしました。
しかし、このようにインデックスを使って要素にアクセスできるコンテナは、 std::vector のほかは std::array と std::deque のみです。
それ以外のコンテナ、たとえば std::list や std::map の要素はインデックスではアクセスできないのです。
これはコンテナ内部の構造の違いに理由があります。

コンテナ内部の構造

標準ライブラリの代表的なコンテナの内部の構造を図にしました。
図中の □ が要素です。

std::array, std::vector などのコンテナ

std::array, std::vector などのコンテナ

この種類のコンテナは、図のようにすべての要素が順番にすき間なく^[2]配置されます。
そのため、先頭の要素から順番にたどっていくことも、インデックスを指定されて途中の要素にいきなりアクセスすることもできます。
後者が可能なのは、指定されたインデックスの要素のアドレスがすぐにわかるためです。

std::forward_list, std::list などのコンテナ

std::forward_list, std::list などのコンテナ

この種類のコンテナは、図のように各要素のノードがポインタでつながれた構造を取ります。
隣接するノードには簡単にアクセスすることができますが、途中の要素にいきなりアクセスすることはできません。
operator[]() が提供されていないのはそのためです。

std::map, std::set などのコンテナ

std::map, std::set などのコンテナ

この種類のコンテナは、図のように二分木で実装されることが多いです。
やはり、途中の要素にいきなりアクセスすることはできません。

なお、 std::map は operator[]() を提供していますが、これはインデックスを指定してその位置の要素を得るものではありません。

このように、コンテナの内部の構造によってインデックスを指定して要素にアクセスできるものとそうではないものがあります。
コンテナの種類によって要素をたどる方法を使い分けなくてもすむように、統一された方法を提供するのがイテレータが導入されている理由です。

イテレータはコンテナの内部の構造と、要素のたどり方 (次の要素を得る方法) を知っています。
そのため、イテレータオブジェクトはコンテナが提供・生成します。

検索 - アルゴリズムを使わない例

イテレータが理解できたところで、いよいよ本題です。

まず、「検索」を、アルゴリズムを使わずに実装することを考えてみましょう。
int 型の std::vector (つまり std::vector<int>) のオブジェクト iv が与えられたとき、その中に特定の値 value と等しい要素が含まれているかどうかを検索します。

例 1: for 文 + if 文 + インデックス

本記事の対象読者でイテレータにもなじみがない方であれば、このようなコードを書かれるのではないでしょうか？

検索-1

bool contains(const std::vector<int> &iv, int value) {
  for (std::vector<int>::size_type i{0}; i < iv.size(); ++i) {
    if (iv[i] == value) {
      return true;
    }
  }
  return false;
}

何も間違っていませんね。

例 2: for 文 + if 文 + イテレータ

または、イテレータの扱いに慣れている方はこう書かれるかもしれません。

検索-2

bool contains(const std::vector<int> &iv, int value) {
  for (auto it = iv.cbegin(), end = iv.cend(); it != end; ++it) {
    if (*it == value) {
      return true;
    }
  }
  return false;
}

これも間違っていません。

cbegin() や cend() は const_iterator オブジェクトを返します。
通常の iterator オブジェクトと違って、イテレータが指している要素を変更することができないものです。

例 3: 範囲 for 文 + if 文

あるいは、 C++11 から導入された range-based for statement をご存知の方は次のように書かれるかもしれません。

検索-3

bool contains(const std::vector<int> &iv, int value) {
  for (int e : iv) {
    if (e == value) {
      return true;
    }
  }
  return false;
}

こちらも間違いではありません。

検索 - アルゴリズムを使った例

次に、アルゴリズムを使って同じことをするコードを見てみましょう。

例 4: std::find アルゴリズム

特定の値に一致する要素を検索するには std::find アルゴリズムが使えます。
std::find アルゴリズムは標準ライブラリの <algorithm> ヘッダで提供されているので、事前にこのヘッダをインクルードしておきます。

検索-4

bool contains(const std::vector<int> &iv, int value) {
  return std::find(iv.cbegin(), iv.cend(), value) != iv.cend();
}

いかがでしょうか。

シンプル

ずいぶんとシンプルになりましたね。
「アルゴリズムを使わない例」ではどれも 6 行でしたが、「アルゴリズムを使った例」では 1 行ですんでいます。

同じ目的を達成するならコードはシンプルであればあるほどよいです。
複雑なコードはタイプの労力が増えるだけでなく、ミスの誘発につながります。
たとえば、やや強引ですが、検索-1 のようなコードでは、 for 文の条件式を i < iv.size() ではなく i <= iv.size() と書き間違えてしまう恐れがあります^[3]。
コードレビューをするときにも、そういった本質的でないところに注意しなくてはなりません。

std::find アルゴリズムには引数が 3 個ありますが、これは「範囲 [iv.cbegin(), iv.cend())^[4] の中で value と等しいものを検索せよ」という意味です。
これ以上は減らせないほど最小限の、そして本質的な情報だけですんでいることに注目してください。

how ではなく what

「アルゴリズムを使わない例」のコードは for 文や if 文など、「検索の実現方法」、つまり「how」を書いていました。
一方、「アルゴリズムを使った例」のコードにはそのような how は見られず、コードが表しているのは find という「何をしているのか (したいのか)」、つまり「what」です。

これは、込み入ったロジックを抽出して名前の付いた関数にするようなよくあるリファクタリング手法と同様に、コードの可読性 (readability)・理解容易性 (understandability) を向上させます。

補足

std::find アルゴリズムは、指定された値と等しい要素が見つかった場合はその要素へのイテレータを, 見つからなかった場合は第 2 引数 (この例の場合は iv.cend()) を返します。
そのため、 return 文の式 std::find(...) != iv.cend() は「指定された値 value と等しい要素が見つかった」という意味となります。

条件指定

先ほどの例は指定された値と等しい要素を検索するものでした。
実際にはもう少し複雑な条件で検索したいこともあるでしょう。

せっかくなので、今度は std::find に代わって要素の数を数える std::count_if アルゴリズムを取り上げます。
このように名前に "_if" がつくものは条件を指定できるようになっています。

この条件の指定方法でいくつかのバリエーションがあるため、ひとつずつご紹介します。

例 5: std::count_if アルゴリズム + 関数ポインタ

まずは関数ポインタ版です。

カウント-1

// 引数 n が偶数なら true を返す。
bool isEven(int n) {
  return (n % 2) == 0;
}

// 引数 iv 内の偶数の数を返す。
std::size_t countEven(const std::vector<int> &iv) {
  return std::count_if(iv.cbegin(), iv.cend(), isEven);
}

std::count_if アルゴリズムも引数を 3 個受け取ります。
第 1, 第 2 引数は std::find アルゴリズムと同様に対象範囲です。
第 3 引数に、数える要素の条件を指定します。
この例では isEven 関数へのポインタを渡しています。

std::count_if アルゴリズムは、範囲 [iv.cbegin(), iv.cend()) を順番に走査し、その要素をひとつずつ引数にして関数 isEven を呼び出します。
呼び出した結果が true と評価される場合にカウントを増やします。
関数 isEven は、コンテナ iv の要素の数だけコールバックされます。

理解できれば難しくないと思います。

例 6: std::count_if アルゴリズム + 関数オブジェクト

次は関数オブジェクト版です。

カウント-2

struct IsEven {
  bool operator()(int n) const {
    return (n % 2) == 0;
  }
};

std::size_t countEven(const std::vector<int> &iv) {
  return std::count_if(iv.cbegin(), iv.cend(), IsEven{});
}

この例では、 std::count_if アルゴリズムの第 3 引数に関数オブジェクトを渡しています。
関数オブジェクトというのは関数のように扱えるオブジェクト、またはその型であるクラスのことです。
具体的には、 operator()() をオーバーロードしているようなクラスです。
この例では IsEven クラスが関数オブジェクトです。

std::count_if アルゴリズムの第 3 引数の IsEven{} は、同クラスのデフォルトコンストラクタを呼び出して、無名の一時オブジェクトを生成しています。
使い捨てする場合はこう書くことが多いです。
このあともくり返し使うようであれば、名前のあるオブジェクトとするのがよいと思います。

関数ポインタと関数オブジェクトの違い

関数ポインタ (例 5) に対する関数オブジェクト (例 6) の最大の強みは、「状態を持てる」ということです。
普通の関数は同じ引数に対しては常に同じ結果しか返せませんが、関数オブジェクトは普通のクラスなので状態を持つことができます。
これによって、同じ引数の operator()() 呼び出しに対しても、状態に応じて異なる値を返すことができます。

例を示します:

カウント-3

struct IsDivisible {
 public:
  IsDivisible(int divisor) : divisor_{divisor} {}
  bool operator()(int n) const {
    return (n % divisor_) == 0;
  }
 private:
  int divisor_;
};

std::size_t countDivisibleBy3(const std::vector<int> &iv) {
  return std::count_if(iv.cbegin(), iv.cend(), IsDivisible{3});
}

カウント-2 のコードの IsEven 関数オブジェクトは偶数かどうかの判断しかできませんでしたが、これを一般化して任意の整数で割り切れるかどうかを判断する関数オブジェクト IsDivisible を用意します。
※簡単のため 0 除算は考慮していません。
このクラスをインスタンス化する際に IsDivisible{3} と除数を指定しています。

関数の場合はこういうことはできません。

...

厳密にはできないわけではなくて、たとえば次のように <functional> ヘッダで提供される std::bind を使うと関数でも同じことができます。

カウント-4

bool isDivisibleBy(int n, int divisor) {
  return (n % divisor) == 0;
}

std::size_t countDivisibleBy3(const std::vector<int> &iv) {
  using namespace std::placeholders;
  return std::count_if(iv.cbegin(), iv.cend(), std::bind(isDivisibleBy, _1, 3));
}

ただ、読みやすさはいまいちだと思うので、こう書くくらいなら次にご紹介するラムダ式の方がよいと考えます。

例 7: std::count_if アルゴリズム + ラムダ式

最後はラムダ式版です。

カウント-5

std::size_t countEven(const std::vector<int> &iv) {
  return std::count_if(iv.cbegin(), iv.cend(), [](int e) {
    return (e % 2) == 0;
  });
}

std::count_if アルゴリズムの第 3 引数 [](int e) { return (e % 2) == 0; } がラムダ式です。
ラムダ式はさまざまなところで詳しく解説されているのでこの記事では説明しません。

最後に持ってきましたが、実際にはこのバリエーションがもっともよく使われると思います。
関数にしろ関数ポインタにしろ、使うところ (この例では countEven 関数) の外側で定義しなくてはならないのでちょっと使いにくいのです。
条件が一般的・汎用的であれば、あらかじめその条件に合う関数オブジェクトをライブラリとして用意しておく作戦がとれますが、アドホックな条件であればあるほど、遠く離れた場所で定義するのは嫌なものです。

そのほかのアルゴリズム

ここでは std::find と std::count_if をご紹介しましたが、標準ライブラリにはほかにもすぐに役に立ちそうなアルゴリズムがそろっています。
いくつか例をあげます:

• std::all_of, std::any_of, std::none_of
• std::copy
• std::fill
• std::transform
• std::generate
• std::shuffle
• std::sample
• std::sort
• ...

ライブラリの常で、引数のパターンや条件に指定できる述語の要件はどのアルゴリズムでも似通っています。

時間があるときにアルゴリズムの一覧に目を通しておくと、ロジックを手書きしようとしたときに「まてよ、確かこれと同じようなアルゴリズムが標準ライブラリにあったはず...」と気づけるようになると思います。

おわりに

本記事では C++ のアルゴリズムをご紹介しました。
for 文や if 文の組み合わせでも同じことはできますが、用意されたアルゴリズムを使うことで開発スピードや品質が向上します。

特に、 how ではなく what で述べたように、適切な名前の付いたアルゴリズムを使うことで、そのコードが何をしたいのか, 何をしているのかが一目で読み取れることのメリットは大きいです。

これまでアルゴリズムを知らなかった方, 何となく避けてきた方にもぜひ使っていただきたいと思います。

なお、イテレータを使う理由で述べましたが、アルゴリズムを使ったコードは要件が合っていれば^[5]あとでコンテナを変更してもそのまま使えます。

脚注

1. 一部 <numeric> など他のヘッダで提供されるアルゴリズムもあります。

2. アラインメント要求を満たすためのパディングが挿入されることはあります。

3. そんなプログラマーはいないと思いたいですが...

4. このように表現される範囲を「半開区間」と呼び、 iv.cbegin() は含み、 iv.cend() は含まないことを表します。

5. たとえば、 std::sort アルゴリズムはランダムアクセスイテレータを要求するので、これに適合しない std::list は使えません。