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

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

この章の概要

この章の概要です。

readonly な STLアルゴリズム

この章では、STLアルゴリズムの中から、対象の要素の値や、並び順を変更しないものを取り上げます。 このような分類にそれほど大きな意味はありませんが、数が膨大なので、 この章以降も同様に、ある程度のグループ分けを行って説明していきます。

count

count関数は、指定した範囲内に、指定の値と一致する要素が何個あるかを調べます。 通常の一致 (==演算子による比較)ではなく、もっと複雑な条件一致が必要であれば、count_if関数を検討して下さい。

namespace std {
	template <typename InputIterator, typename T>
	typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value);
}

一致する要素の個数が戻り値で返されますが、型が少々複雑になっています。 std::iterator_traits<InputIterator>::difference_type は、2つのイテレータ間の距離の差を表現するために定義されている型ですが、 単なる整数型であると考えて問題ありません。

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

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

	std::cout << std::count(v.begin(), v.end(), 0) << std::endl;
}

実行結果

2

なお、対象が STLコンテナの場合、countメンバ関数が存在しているのなら、そちらを使った方が効率的です。 例えば、set/multiset(第8章)や map/multimap(第9章)には countメンバ関数があります。

また、指定の値と一致する要素が存在するかどうかだけに興味がある場面では、count関数を使うと非効率です。 count関数は個数を調べることが目的なので、一致する要素が1つ見つかっても、必ず末尾まで処理を続けてしまうからです。 このような目的の場合には、以下のように検討して下さい。

  1. 対象の STLコンテナが findメンバ関数を持っているなら、そちらを使う。
  2. 対象の STLコンテナが countメンバ関数を持っているなら、そちらを使う。
  3. 対象がソート済みであれば、binary_search関数(第22章)を使う。
  4. 対象がソート済みでなければ、find関数を使う。

count_if

count_if関数は、指定した範囲内に、指定の条件と一致する要素が何個あるかを調べます。

namespace std {
	template <typename InputIterator, typename T>
	typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);
}

第3引数が単項叙述関数になっているので、ここに条件を記述した関数や関数オブジェクトを渡すことができます。 例えば、値が偶数の要素の個数を調べるには、次のようにします。

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

namespace {
	bool isEven(int elem)
	{
		return elem % 2 == 0;
	}
}

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

	std::cout << std::count_if(v.begin(), v.end(), isEven) << std::endl;
}

実行結果

3

find

find関数は、指定した範囲内で、指定の値と一致する最初の要素の位置を返します。 一致する要素が無ければ、末尾の次を指すイテレータが返されます。
特定の値との一致ではなく、もっと複雑な条件一致が必要であれば、find_if関数を検討して下さい。

namespace std {
	template <typename InputIterator, typename T>
	InputIterator find(InputIterator first, InputIterator last, const T& value);
}

使い方は次のようになります。

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

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

	std::vector<int>::iterator it = std::find(v.begin(), v.end(), 1);
	if (it == v.end()) {
		std::cout << "not found." << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

1

count関数と違い、一致する要素が見つかった時点で処理が打ち切られるため、 一致する要素の有無を確かめることが目的であれば、count関数よりも効率的です。 ただし、対象が STLコンテナであり、countメンバ関数が存在するのなら、そちらを使った方がより効率的です。

find_if

find_if関数は、指定した範囲内で、指定の条件と一致する最初の要素の位置を返します。 一致する要素が無ければ、末尾の次を指すイテレータが返されます。

namespace std {
	template <typename InputIterator, typename Predicate>
	InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
}

第3引数が単項叙述関数になっているので、ここに条件を記述した関数や関数オブジェクトを渡すことができます。 例えば、値が偶数の要素を探すには、次のようにします。

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

namespace {
	bool isEven(int elem)
	{
		return elem % 2 == 0;
	}
}

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

	std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), isEven);
	if (it == v.end()) {
		std::cout << "not found." << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

0

C++11 (find_if_not)

C++11

C++11 では、find_if関数とは逆に、 指定した範囲内で、指定の条件を「満たさない」最初の要素の位置を返す find_if_not関数が追加されました。

namespace std {
	template <typename InputIterator, typename Predicate>
	InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred);
}

例えば、次のようになります。

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

namespace {
	bool isEven(int elem)
	{
		return elem % 2 == 0;
	}
}

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

	std::vector<int>::iterator it = std::find_if_not(v.begin(), v.end(), isEven);
	if (it == v.end()) {
		std::cout << "not found." << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

1

find_if_not関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

search

search関数は、範囲を2つ指定し、1つ目の範囲の中から、2つ目の範囲と同じ内容になっている部分を探します。 最初に見つかった、条件に合う範囲の先頭の要素を指すイテレータを返し、見つからなければ第2引数と同じイテレータを返します。

namespace std {
	template<typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

	template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
}

1つ目の形式の場合は、通常の一致比較 (==演算子による比較)が行われます。

#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);
	v.push_back(3);
	v.push_back(4);

	std::list<int> lst;
	lst.push_back(2);
	lst.push_back(3);
	lst.push_back(4);

	std::vector<int>::iterator it = std::search(v.begin(), v.end(), lst.begin(), lst.end());
	if (it == v.end()) {
		std::cout << "not found." << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

2

2つ目の形式の場合は、第5引数に与えた二項叙述関数を使って比較を行います。 以下の例では、文字列が空(長さが 0)であるべきか否かを bool型配列に入れておき、その指定に従っている範囲を探しています。

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

namespace {
	bool checkEmpty(const std::string& s, bool flag)
	{
		return s.empty() == flag;
	}
}

int main()
{
	std::vector<std::string> v;
	v.push_back("abc");
	v.push_back("");
	v.push_back("xxxxx");
	v.push_back("");
	v.push_back("");

	// 「空文字列でない」「空文字列である」「空文字列である」の順で要素が並んでいる部分を探したい
	const bool flags[] = { false, true, true };

	std::vector<std::string>::iterator it = std::search(v.begin(), v.end(), flags, flags + 3, checkEmpty);
	if (it == v.end()) {
		std::cout << "not found." << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

xxxxx

find_end

find_end関数は、範囲を2つ指定し、1つ目の範囲の中から、2つ目の範囲と同じ内容になっている部分を探します。 最後に見つかった、条件に合う範囲の先頭の要素を指すイテレータを返し、見つからなければ第2引数と同じイテレータを返します。

この関数は、search関数の「最後」に見つかった範囲を返すバージョンであり、find関数との関連性はありません。 本来なら、search_end関数という名称であるべきものと思われますが、 標準化の際のミスで、このような分かりづらい命名になってしまったようです。

namespace std {
	template<typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

	template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
}

使い方は search関数と同じと考えて問題ありません。 一致する範囲が見つかったときに返される結果が異なるだけです。

find_first_of

find_first_of関数は、範囲を2つ指定し、1つ目の範囲の中から、2つ目の範囲にも含まれている要素を探します。 見つけた場合は、1つ目の範囲に含まれている要素を指すイテレータを返し、見つからなかった場合は、第2引数のイテレータを返します。

namespace std {
	template <typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

	template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
}

1つ目の形式の場合は、通常の一致比較 (==演算子による比較)が行われます。 より複雑な条件が必要であれば、第5引数に二項叙述関数を渡せる2つ目の形式の方を使用できます。

#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);
	v.push_back(3);
	v.push_back(4);

	std::list<int> lst;
	lst.push_back(7);
	lst.push_back(3);
	lst.push_back(5);

	std::vector<int>::iterator it = std::find_first_of(v.begin(), v.end(), lst.begin(), lst.end());
	if (it == v.end()) {
		std::cout << "not found." << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

3

C++11(イテレータの変更)

C++11 では、find_first_of関数が使用するイテレータのカテゴリが変更されました。 これまでは、2つの範囲を表現するために前方イテレータ(第14章)が使われていましたが、 1つ目の範囲については入力イテレータ(第14章)に変更になっています。 この変更は、無用な制約を緩和するものです。

namespace std {
	template <typename InputIterator, typename ForwardIterator>
	InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2);

	template <typename InputIterator, typename ForwardIterator, typename BinaryPredicate>
	InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred);
}

この変更は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも行われていません

mismatch

mismatch関数は、2つの指定した範囲内の要素を比較し、最初に登場する異なった要素を指すイテレータのペア (std::pair)を返します。 すべての要素が一致した場合は、第2引数のイテレータと、2つ目の範囲内の対応する要素を指すイテレータとのペアを返します。
2つの範囲内の要素がすべて一致しているかどうかを調べたければ、equal関数(第18章)を使って下さい。

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

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

1つ目の形式の場合は、通常の一致比較 (==演算子による比較)が行われます。 より複雑な条件が必要であれば、第4引数に二項叙述関数を渡せる2つ目の形式の方を使用できます。

#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);
	v.push_back(3);

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

	typedef std::pair<std::vector<int>::iterator, std::list<int>::iterator> IteratorPair;
	IteratorPair itPair = std::mismatch(v.begin(), v.end(), lst.begin());
	if (itPair.first == v.end()) {
		std::cout << "same" << std::endl;
	}
	else {
		std::cout << "[" << (*itPair.first) << "," << (*itPair.second) << "]" << std::endl;
	}
}

実行結果

[3,4]

min_element

min_element関数は、指定した範囲内から一番小さい値を持つ要素を探し、その要素を指すイテレータを返します。 一番小さい要素が複数存在する場合、先頭に近い方が返されます。 指定した範囲が空の場合は、第2引数に指定したイテレータが返されます。

namespace std {
	template<typename ForwardIterator>
	ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

	template<typename ForwardIterator, typename Compare>
	ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);
}

1つ目の形式の場合は、要素の比較に <演算子が使われます。

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

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

	std::vector<int>::iterator it = std::min_element(v.begin(), v.end());
	if (it == v.end()) {
		std::cout << "empty" << std::endl;
	}
	else {
		std::cout << *it << std::endl;
	}
}

実行結果

0

対象の範囲が空でないことが分かっているのなら、いちいち戻り値を受け取らず、 以下のように書いてしまうことができます。

std::cout << *std::min_element(v.begin(), v.end()) << std::endl;

2つ目の形式では、第3引数に指定した関数を使って判定を行います。 この関数は、2つの要素が引数で渡されるので、第1引数の方が小さい場合に true を返すように実装します。
以下のサンプルプログラムは、絶対値による比較を行う例です。

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

namespace {
	bool absLess(int elem1, int elem2)
	{
		return std::abs(elem1) < std::abs(elem2);
	}
}

int main()
{
	std::vector<int> v;
	v.push_back(-5);
	v.push_back(3);
	v.push_back(7);

	std::cout << *std::min_element(v.begin(), v.end(), absLess) << std::endl;
}

実行結果

3

max_element

max_element関数は、指定した範囲内から一番大きい値を持つ要素を探し、その要素を指すイテレータを返します。 一番大きい要素が複数存在する場合、先頭に近い方が返されます。 指定した範囲が空の場合は、第2引数に指定したイテレータが返されます。

namespace std {
	template<typename ForwardIterator>
	ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

	template<typename ForwardIterator, typename Compare>
	ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);
}

min_element関数と同じことなので、詳しい使い方は省略しますが、少し捕捉しておきます。

1つ目の形式のとき、比較に使用されるのは min_element関数と同じく <演算子です。 2つの要素を elem1、elem2 だとすると、min_element関数では「elem1 < elem2」のように比較しますが、 max_element関数では「elem2 < elem1」のように比較します。

また、2つ目の形式で比較関数を指定する際も、2つの引数が入れ替えられた状態で渡されてくるようになっているので、 min_element関数と同じルールで比較関数を実装して下さい。

C++11 (minmax_element)

C++11

C++11 では、min_element関数max_element関数を組み合わせた minmax_element関数が追加されています。

namespace std {
	template<typename ForwardIterator>
	pair<ForwardIterator, ForwardIterator> minmax_element(ForwardIterator first, ForwardIterator last);

	template<typename ForwardIterator, typename Compare>
	pair<ForwardIterator, ForwardIterator> minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
}

結果は、一番小さい要素を指すイテレータと、一番大きい要素を指すイテレータのペアで返されます。 指定した範囲が空の場合は、第2引数に指定したイテレータが返されます。

min_element関数、max_element関数と同様に、1つ目の形式では、比較に <演算子が使われます。 2つ目の形式のときに渡す比較関数の実装ルールも、min_element関数、max_element関数と同じです。

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

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

	typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> IteratorPair;
	IteratorPair itPair = std::minmax_element(v.begin(), v.end());
	if (itPair.first == v.end()) {
		std::cout << "empty" << std::endl;
	}
	else {
		std::cout << "[" << (*itPair.first) << "," << (*itPair.second) << "]" << std::endl;
	}
}

実行結果

[0,2]

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

C++11 (all_of)

C++11

C++11 で追加された all_of関数は、指定した範囲内のすべての要素が条件を満たしているかどうかを調べます。

namespace std {
	template <typename InputIterator, typename Predicate>
	bool all_of(InputIterator first, InputIterator last, Predicate pred);
}

次のサンプルプログラムは、すべての要素が偶数かどうかを調べる例です。

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

int main()
{
	std::vector<int> v = {0, 1, 2};

	std::cout << std::boolalpha
	          << std::all_of(std::begin(v), std::end(v), [](int elem){ return elem % 2 == 0; })
	          << std::endl;
}

実行結果

false

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

C++11 (any_of)

C++11

C++11 で追加された any_of関数は、指定した範囲内の要素が、1つだけでも条件を満たしているかどうかを調べます。

namespace std {
	template <typename InputIterator, typename Predicate>
	bool any_of(InputIterator first, InputIterator last, Predicate pred);
}

次のサンプルプログラムは、偶数の要素が1つでも含まれているかどうかを調べる例です。

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

int main()
{
	std::vector<int> v = {0, 1, 2};

	std::cout << std::boolalpha
	          << std::any_of(std::begin(v), std::end(v), [](int elem){ return elem % 2 == 0; })
	          << std::endl;
}

実行結果

true

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

C++11 (none_of)

C++11

C++11 で追加された none_of関数は、指定した範囲内の要素が、1つも条件を満たさないかどうかを調べます。

namespace std {
	template <typename InputIterator, typename Predicate>
	bool none_of(InputIterator first, InputIterator last, Predicate pred);
}

次のサンプルプログラムは、偶数の要素が1つも含まれていないことを調べる例です。

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

int main()
{
	std::vector<int> v = {0, 1, 2};

	std::cout << std::boolalpha
	          << std::none_of(std::begin(v), std::end(v), [](int elem){ return elem % 2 == 0; })
	          << std::endl;
}

実行結果

false

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。


練習問題

問題@ find、find_if、search、find_end、find_first_of の各関数について、その関係性を整理して下さい。


解答ページはこちら

参考リンク

更新履歴

'2017/3/25 VisualC++ 2017 に対応。

'2016/11/20 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ