C++編【標準ライブラリ】 第18章 STLアルゴリズム

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

STLアルゴリズム

STLアルゴリズムは、コンテナの各要素を処理するために用意された関数群です。 膨大な数が存在するので、ここから数章に分けて順次取り上げていきます。

STLアルゴリズムは、メンバ関数ではなく、std名前空間に含まれる通常の関数になっています。 処理対象の要素へはイテレータを介してアクセスするようになっており、 特定の種類のコンテナに依存しない、高い柔軟性を持っています。

汎用的であるが故に、特定の種類のコンテナに対しては非効率になってしまうアルゴリズムもあります。 もし、あるコンテナが、STLアルゴリズムの関数と同名のメンバ関数を持っていたら、普通は、メンバ関数版を使った方が効率的です。

ほとんどの STLアルゴリズムは、algorithm という標準ヘッダに含まれています。 例外的に、第23章で登場する数値演算関係の STLアルゴリズムについては、numeric という標準ヘッダに含まれます。

for_each

まず、最も基本的かつ重要な for_each関数を取り上げます。

namespace std {
	template <typename InputIterator, typename Function>
	Function for_each(InputIterator first, InputIterator last, Function f);
}

for_each関数は、2つのイテレータで表現される範囲内にある各要素に対して、f を呼び出します。 要素を elem と表現すると、順次、f(elem) を呼び出していく関数ということになります。

この先、紹介する他の関数でも同様ですが、関数宣言の型名にも注意してみて下さい。 for_each の場合、イテレータは InputIterator という名前にしており、これは「入力イテレータ」のことです。 第14章でイテレータのカテゴリを取り上げていますが、この分類と一致した名前が付けられています。

例えば、以下のサンプルプログラムは、対象の各要素を標準出力へ出力します。

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

void Println(int elem)
{
	std::cout << elem << std::endl;
}

int main()
{
	std::vector<int> v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);

	std::for_each(v.begin(), v.end(), Println);
}

実行結果

0
1
2

for_each関数の戻り値は、第3引数のコピーです。 第3引数に通常の関数を渡す場合にはあまり意味がありませんが、関数オブジェクトを使うと、 各要素の処理を行いながら情報を蓄積していき、最後に結果を問い合わせるような使い方が可能になります。

C++11 では、std::move(f) を返すようになりました。

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

class Printer {
public:
	Printer() : mCount(0)
	{}

	void operator()(int elem)
	{
		std::cout << elem << std::endl;
		++mCount;
	}

	int GetCount() const
	{
		return mCount;
	}

private:
	int  mCount;
};

int main()
{
	std::vector<int> v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);

	const int count = std::for_each(v.begin(), v.end(), Printer()).GetCount();
	std::cout << "count: " << count << std::endl;
}

実行結果

0
1
2
count: 3

equal

eqaul関数は、ある2つの範囲内に含まれている要素が一致しているかどうかを調べます。

namespace std {
	template <typename InputIterator1, typename InputIterator2>
	bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

	template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
	bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);
}

どちらの形式でも、第1・第2引数が1つの範囲を表現しており、第3引数でもう1つの範囲の開始点を表現します。 範囲の大きさは、第1・第2引数によって決まるので、2つ目の範囲の方が小さくならないように注意する必要があります

第1・第2引数の型と、第3引数の型が異なっていることに注目して下さい。 これは、2つの範囲が、異なる型のコンテナであって構わないことを示しています。 例えば、次のように vector と list の要素を比較できます。

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

int main()
{
	std::vector<int> v;
	v.push_back(0);
	v.push_back(1);
	v.push_back(2);

	std::list<int> lst;
	lst.push_back(0);
	lst.push_back(1);
	lst.push_back(2);

	std::cout << std::boolalpha
	          << std::equal(v.begin(), v.end(), lst.begin())
	          << std::endl;
}

実行結果

true


2つ目の形式の方は、第4引数に関数や関数オブジェクトを渡して、一致比較の条件を指定できるようになっています。 ここで指定する関数や関数オブジェクトは、2つの引数を受け取り、結果として bool型の値を返す必要があります。 true を返せば一致しているとみなされ、false を返せば不一致であるとみなされます。
なお、後述しますが、このような関数は、叙述関数と呼ばれています。

例えば、以下の例では、正確に表現できない小さな誤差を許容した比較を行います。

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

bool equalDouble(double a, double b)
{
	return std::abs(a - b) < std::numeric_limits<double>::epsilon();
}

int main()
{
	std::vector<double> v;
	v.push_back(0.0);
	v.push_back(0.0);
	v.push_back(1.0);

	std::list<double> lst;
	lst.push_back(0.0);
	lst.push_back(0.0000000000000001);
	lst.push_back(0.9999999999999999);

	std::cout << std::boolalpha
	          << std::equal(v.begin(), v.end(), lst.begin(), equalDouble)
	          << std::endl;
}

実行結果

true

叙述関数

equal関数の第4引数のように、比較結果などを bool型で返す関数は、叙述関数(プレディケート)と呼ばれています。 また、引数が1つの場合を単項叙述関数、2つの場合を二項叙述関数と呼びます。

equal関数の宣言を見ると、第4引数の型名が「BinaryPredicate」となっていますが、 これは、二項(Binary) の叙述関数(Predicate) であることを表しています。

STL は、叙述関数に関して、同じ引数を与えた場合には常に同じ結果を返さなければならないと規定しています。 そのため、特に関数オブジェクトを使う場合には、メンバ変数が変化しないようにして注意しなければなりません。 叙述関数として使う関数オブジェクトでは、operator() を常に constメンバ関数にするのが安全でしょう


練習問題

問題@ for_each関数がどのように実装されているか、想像して自力の実装を書いてみて下さい。

問題A for_each関数を使って、各要素の平均値を計算する処理を作成して下さい。

問題B for_each関数や equal関数は、通常の配列に対しても使用できるでしょうか? 予想を立てた後、実際にプログラムを書いて確かめて下さい。


解答ページはこちら

参考リンク

更新履歴

'2016/11/19 新規作成。



前の章へ

次の章へ

C++編のトップページへ

Programming Place Plus のトップページへ