TechFULの中の人

triple-four’s blog

範囲を楽に扱おう

こんにちは!TechFULで問題制作アルバイトをしているSiiiecです。

この記事では、 C++での範囲に対する処理 について触れていきたいと思います。
量も多いので、どんなことができるかを知る位の軽い気持ちで読んでみると良いかと思います。

はじめに

プログラミングでは、配列などの範囲に対しての処理が多く登場します。例えば、以下のようなものです。

  • 全ての要素に処理を行いたい
  • 最大値・最小値・合計値を求めたい
  • 全ての要素が条件を満たしているか調べたい

for文を使って回すのも良いのですが、どうせなら楽にわかりやすく書きたいですね。

ということで、私自身使うことの多いものを中心に紹介していきます。

事前準備

範囲に対する処理では、3つのものが登場します。

  • モノの入れ物を抽象化したコンテナ
  • 繰り返し処理に使用するイテレータ
  • 繰り返しの内容を表す関数オブジェクト

範囲を扱う関数に、イテレータ、関数オブジェクトを渡すことで、処理を行います。
範囲を扱う関数は、<algorithm>または<numeric>ヘッダに含まれています。

コンテナ

配列を始めとして、連結リストや動的配列など、モノの入れ物のことを表します。

イテレータ

イテレータ - Wikipedia https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%86%E3%83%AC%E3%83%BC%E3%82%BF

イテレータ(英語: iterator)とは、プログラミング言語において配列やそれに類似する集合的データ構造(コレクションあるいはコンテナ)の各要素に対する繰り返し処理の抽象化である。実際のプログラミング言語では、オブジェクトまたは文法などとして現れる。

イテレータは反復子とも呼ばれていますが、名前が示すようにコンテナの要素全体について反復した処理を行う際に使用します。
標準ライブラリの全てのコンテナは、先頭要素を表すイテレータを返すbegin()、末尾要素の一つ後ろを表すイテレータを返すend()メンバ関数を持っています。
また、通常の配列についても、std::begin()std::end()関数に渡すことでイテレータを得ることができます。

イテレータの指す要素の値を得るには、ポインタのように*->を使用します。

関数オブジェクト

()演算子によって、関数のように呼ぶことができるものを表します。
関数自体も関数オブジェクトですが、ラムダ式が使われることが多いです。

ラムダ式

ラムダ式 - cpprefjp https://cpprefjp.github.io/lang/cpp11/lambda_expressions.html

ラムダ式(lambda expressions)」は、簡易的な関数オブジェクトをその場で定義するための機能である。

範囲を扱う関数に関数オブジェクトを渡す必要がありますが、通常の関数を範囲を扱う度に定義すると、一度しか使わない関数が何個も定義され、管理が煩わしくなります。

基本的にはラムダ式は、以下のような形式で書きます。なお、ここでは省略可能部分については説明しません。

[キャプチャ](引数){処理};

例えば、2つのint型引数の差を返すラムダ式の使用は以下のようになります。
呼び出す場合は通常の関数と同じで()を使用します。

auto minus = [](int a, int b) { return a -b; };
int result = minus(5, 3);   // resultには2が格納される

ラムダ式の外側にある変数をラムダ式内で使う場合は、キャプチャ部分に記述します。

記法 説明
[] キャプチャしない
[&] デフォルトでスコープ内の全変数を参照する
[=] デフォルトでスコープ内の全変数をコピーする
[&変数名] 指定された変数を参照する
[変数名] 指定された変数をコピーする
[this] クラスのメンバを参照する

,を使うことで複数の参照方式を記述することが可能です。

for_each

全ての要素に処理を行います

// コンテナ内の要素を全て表示する

std::vector<int> v = {1, 2, 3, 4, 5, 6};
std::for_each(v.begin(), v.end(), [](int e)
{
    std::cout << e << " ";
});

// 1 2 3 4 5 6 
// と表示される

引数を参照で取ることで、ラムダ式内で要素の変更を行うことも可能です。

find, find_if

指定された要素を探します

// 2を検索し、見つかった場合は値を表示する

std::vector<int> v = {1, 2, 3};
auto result = std::find(v.begin(), v.end(), 2);

if (result == v.end())
    std::cout << "not_found" << std::endl;
else
    std::cout << *result << std::endl;

// 2
// と表示される

複数ある場合は、最初イテレータを返します。

find_ifでは、条件としてラムダ式を渡し、最初にtrueとなるイテレータを返します。
上記のresult初期化部分は以下のように書くことができます。

auto result = std::find_if(v.begin(), v.end(), [](int e)
{
    return e == 2;
});

count, count_if

指定された要素の数を数えます

countでは値を渡すことで、count_ifでは関数オブジェクトを渡すことで条件の指定をします。

// 偶数の数を数える

std::vector<int> v = {1, 2, 3, 4, 6, 10};

auto n = std::count(v.begin(), v.end(), [](int e)
{
    return e % 2 == 0;
}); 

// nの値は4となる

all_of, any_of, none_of

全ての(いずれかの)要素が条件を満たしているか調べます

3つの関数は以下のような違いがあります。

  • all_of: 全ての要素が条件を満たしている場合true
  • any_of: いずれかの要素が条件を満たしている場合true
  • none_of: 全ての要素が条件を満たしていない場合false
// 全ての要素が偶数化どうか判定
std::vector<int> v = {2, 4, 6, 8};

auto isEven = std::all_of(v.begin(), v.end(), [](int e)
{
    return e % 2 == 0;
});

// isEvenはtrueとなる

copy, copy_n, copy_if

指定された範囲の値を出力イテレータ(別のコンテナ)にコピーします

// コピー元コンテナ
std::vector<int> v = {1, 2, 3, 4};
// コピー先コンテナ
std::vector<int> dst(v.size()); // コピー元以上の要素数を確保する

std::copy(v.begin(), v.end(), dst.begin());

// dstには、{1, 2, 3, 4}がコピーされる

copy_nでは終端イテレータではなく要素数を指定します。
copy_ifでは関数オブジェクトを値の代わりに渡します。

replace, replace_if

指定の値と一致する要素の値を置き換えます

// 値1の要素の値を20にする

std::vector<int> v = {1, 2, 1, 1, 5};

std::replace(v.begin(), v.end(), 1, 20);

// vの要素は、{20, 2, 20, 20, 5}となる

他の関数と同様、条件を関数オブジェクトで渡す場合replace_ifを使用します。

要素を置き換えた結果を出力イテレータにコピーするreplace_copyreplace_if_copyもあります。

remove, remove_if

指定された値を持つ要素をコンテナから削除します

// 値1の要素を削除する

std::vector<int> v = {1, 2, 1, 1, 5};

std::remove(v.begin(), v.end(), 1);

// vの要素は、{2, 5}となる

削除されたものより後ろの要素は、前に寄せられます

要素を置き換えた結果を出力イテレータにコピーするremove_copyremove_if_copyもあります。

sort

要素を並び替えます

// コンテナの要素を昇順に並べ替える

std::vector<int> v = {3, 2, 4, 1, 5};
std::sort(v.begin(), v.end());

// vの要素は、{1, 2, 3, 4, 5}となる

デフォルトでは昇順に並べ替えますが、比較用の関数オブジェクトを渡すこともできます。

reverse

要素の並ぶ順序を逆にします

// コンテナを逆順にする

std::vector<int> v = {3, 2, 4, 1, 5};
std::reverse(v.begin(), v.end());

// vの要素は、{5, 1, 4, 2, 3}となる

逆順にした結果を他のコンテナにコピーするreverse_copyもあります。

lower_bound

整列された要素に対して、指定された値以上の要素が最初に現れる位置のイテレータを返します

// 4以上の要素の位置を検索
std::vector<int> v = {3, 2, 4, 1, 6};
std::sort(v.begin(), v.end());
auto it = std::lower_bound(v.begin(), v.end(), 4);

auto pos = it - v.begin();

// posの値は3

二分探索を行い、要素の検索を行います。 要素が見つからなかった場合は、終端イテレータを返します。

min_element, max_element

最小値(最大値)を指すイテレータを返します

// 最大値を検索
std::vector<int> v = {3, 2, 4, 1, 6};
auto maxElem = *std::max_element(v.begin(), v.end());

// maxElemの値は6

最小値と最大値を指す要素へのイテレータをペアで返すminmax_elemntもあります。

accumulate

指定された範囲について、集計操作を行います

// 要素の値mに対してm(m + 1)の総和を計算する

std::vector<int> v = {3, 2, 4, 1, 6};
auto result = std::accumulate(v.begin(), v.end(), 0, [](int init, int e)
{
    return init + e * (e + 1);
});

// resultの値は82

単純な総和の計算や、畳み込みと言われる処理を行うことが可能です。
三番目の引数に初期値、四番目の引数に任意で集計操作を表す関数オブジェクトを渡します。四番目の引数がない場合は、総和を取ります。

渡される関数オブジェクトは一番目の引数に累計値、二番目の引数に要素をとります。

partial_sum

指定された範囲について、部分和を計算します

// 累積和を計算する

std::vector<int> v = {3, 2, 4, 1, 6};
std::vector<int> result(v.size());
std::partial_sum(v.begin(), v.end(), result.begin());

// resultは{3, 5, 9, 10, 16}

accumulateでは結果のみを出力していましたが、partial_sumでは計算の途中結果を出力イテレータに書き込みます。

初期値は渡されたイテレータの最初の要素となります。

adjacent_difference

隣り合う要素感の差を計算します

// 隣接要素の差を計算する

std::vector<int> v = {3, 2, 4, 1, 6};
std::vector<int> result(v.size());

std::adjacent_difference(v.begin(), v.end(), result.begin());

// resultは{3, -1, 2, -3, 5}

要素間の差分を出力イテレータに書き込みます。
出力される最初の要素の値は、入力される最初の要素の値となります。

accumulateと同様に、差分処理を関数オブジェクトで渡すことができます。

おわりに

以前の記事では文法に固執しないということをが大事だとありました。 triple-four.hatenablog.com 固執しすぎるのは良くないのですが、やはり知っているかどうかの差は大きいため紹介させていただきました。

そういえばこんな機能があったな、と思い出していただけると幸いです。

参考サイト

cpprefjp - C++日本語リファレンス

イテレータの解説をするなんて今更佳代