C++編【標準ライブラリ】 第23章 ソートされた範囲を扱う STLアルゴリズム

先頭へ戻る

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

この章の概要

この章の概要です。

ソートされた範囲を扱う STLアルゴリズム

この章では、STLアルゴリズムの中から、ソートされた範囲に対して処理を行うものを取り上げます。

これらのアルゴリズムを、ソートされていない範囲に対して適用した場合の結果は未定義です。

binary_search

binary_search関数は、指定の範囲内から、特定の値を持った要素があるかどうかを調べます。

namespace std {
	template <typename ForwardIterator, typename T>
	bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

	template <typename ForwardIterator, typename T, typename Compare>
	bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

第1、2引数に、対象の範囲を指定し、第3引数に、探したい値を指定します。 第4引数には、要素の大小関係を定義する関数や関数オブジェクトを指定できます。
該当する要素が見つかった場合は true を、見つからなかった場合は false を返します。

binary_search関数は、名前の通り、二分探索(アルゴリズムとデータ構造編【探索】第4章)によって実装されています。

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

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::cout << std::boolalpha
	          << std::binary_search(v.begin(), v.end(), 3)
	          << std::endl;
}

実行結果

true

lower_bound

lower_bound関数は、指定の範囲内で、指定の値以上の要素が現れる最初の位置を返します。

namespace std {
	template <typename ForwardIterator, typename T>
	ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

	template <typename ForwardIterator, typename T, typename Compare>
	ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

第1、2引数の範囲から、第3引数の値以上の要素が現れる最初の位置を返します。
この関数は、ソートされた状態を崩すことなく、第3引数の値を挿入できる位置はどこかを取得できるということです。

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

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

int main()
{
	std::vector<int> v;
	v.push_back(0);
	v.push_back(3);
	v.push_back(4);
	v.push_back(6);
	v.push_back(9);

	const int value = 5;
	v.insert(std::lower_bound(v.begin(), v.end(), value), value);

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

実行結果

0
3
4
5
6
9

upper_bound

upper_bound関数は、指定の範囲内で、指定の値より大きい要素が現れる最初の位置を返します。

namespace std {
	template <typename ForwardIterator, typename T>
	ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

	template <typename ForwardIterator, typename T, typename Compare>
	ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

第1、2引数の範囲から、第3引数の値以上の要素が現れる最初の位置を返します。
この関数は、ソートされた状態を崩すことなく、第3引数の値を挿入できる位置はどこかを取得できるということです。

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

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

int main()
{
	std::vector<int> v;
	v.push_back(0);
	v.push_back(3);
	v.push_back(4);
	v.push_back(6);
	v.push_back(9);

	const int value = 5;
	v.insert(std::upper_bound(v.begin(), v.end(), value), value);

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

実行結果

0
3
4
5
6
9

equal_range

equal_range関数は、指定の範囲内で、指定の値以上の要素が現れる最初の位置と、指定の値より大きい要素が現れる最初の位置を返します。

namespace std {
	template <typename ForwardIterator, typename T>
	pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);

	template <typename ForwardIterator, typename T, typename Compare>
	pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

この関数は、lower_bound関数upper_bound関数の組み合わせです。

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

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

	const int value = 5;

	typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> IteratorPair;
	IteratorPair itPair = std::equal_range(v.begin(), v.end(), value);

	std::cout << std::distance(v.begin(), itPair.first)
	          << ", "
	          << std::distance(v.begin(), itPair.second)
	          << std::endl
	          ;
}

実行結果

2, 4

includes

includes関数は、指定の範囲内に、別の指定範囲内の要素がすべて含まれているかどうかを調べます。

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

	template <typename InputIterator1, typename InputIterator2, typename Compare>
	bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
}

第1、2引数で指定した範囲内に、第3、4引数で指定した範囲内の要素がすべて含まれていれば true を返します。 そうでなければ false が返されます。
第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(v.begin(), v.end());

	std::cout << std::boolalpha
	          << std::includes(v.begin(), v.end(), lst.begin(), lst.end())
	          << ", "
	          << std::includes(lst.begin(), lst.end(), v.begin(), v.end())
	          << std::endl;

	lst.push_back(5);
	std::cout << std::boolalpha
	          << std::includes(v.begin(), v.end(), lst.begin(), lst.end())
	          << ", "
	          << std::includes(lst.begin(), lst.end(), v.begin(), v.end())
	          << std::endl;
}

実行結果

true, true
false, true

merge

merge関数は、指定した2つのソート済み範囲の要素を併合(マージ)して、ソートされた新たな範囲を生成します。

namespace std {
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第1、第2引数で1つのソート済み範囲を、第3、4引数でもう1つのソート済み範囲を指定します。 第5引数で指定した位置へ、併合してソートした結果を出力します。 第6引数は、要素の比較に用いる関数や関数オブジェクトです。
戻り値は、最後に出力された要素の位置を返します。

なお、対象が std::list の場合には、メンバ関数の merge(第6章)があるので、そちらを使う方が効率的です。

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

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

int main()
{
	std::vector<int> v1, v2;
	v1.push_back(0);
	v1.push_back(3);
	v1.push_back(4);
	v2.push_back(1);
	v2.push_back(2);

	std::vector<int> result(v1.size() + v2.size());

	std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
	std::for_each(result.begin(), result.end(), Println);
}

実行結果

0
1
2
3
4

set_union

set_union関数は、指定した2つのソートされた範囲のどちらか一方(あるいは両方)に含まれている要素からなる新たな集合を生成します。 いわゆる「和集合」を作る関数です。

namespace std {
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第1、第2引数で1つのソート済み範囲を、第3、4引数でもう1つのソート済み範囲を指定します。 第5引数で指定した位置へ、和集合を出力します。 第6引数は、要素の比較に用いる関数や関数オブジェクトです。
戻り値は、最後に出力された要素の位置を返します。

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

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

int main()
{
	std::vector<int> v1, v2;
	v1.push_back(0);
	v1.push_back(1);
	v1.push_back(3);
	v2.push_back(1);
	v2.push_back(2);

	std::vector<int> result(v1.size() + v2.size());
	std::vector<int>::iterator it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

	std::for_each(result.begin(), it, Println);
}

実行結果

0
1
2
3

set_intersection

set_intersection関数は、指定した2つのソートされた範囲の両方に含まれている要素からなる新たな集合を生成します。 いわゆる「積集合」を作る関数です。

namespace std {
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第1、第2引数で1つのソート済み範囲を、第3、4引数でもう1つのソート済み範囲を指定します。 第5引数で指定した位置へ、積集合を出力します。 第6引数は、要素の比較に用いる関数や関数オブジェクトです。
戻り値は、最後に出力された要素の位置を返します。

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

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

int main()
{
	std::vector<int> v1, v2;
	v1.push_back(0);
	v1.push_back(1);
	v1.push_back(3);
	v2.push_back(1);
	v2.push_back(2);

	std::vector<int> result(v1.size() + v2.size());
	std::vector<int>::iterator it = std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

	std::for_each(result.begin(), it, Println);
}

実行結果

1

set_difference

set_difference関数は、指定した1つ目のソートされた範囲に含まれているが、 2つ目のソートされた範囲には含まれていない要素からなる新たな集合を生成します。 いわゆる「差集合」を作る関数です。

namespace std {
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第1、第2引数で1つのソート済み範囲を、第3、4引数でもう1つのソート済み範囲を指定します。 第5引数で指定した位置へ、1つ目の範囲にだけ含まれている要素からなる差集合を出力します。 第6引数は、要素の比較に用いる関数や関数オブジェクトです。
戻り値は、最後に出力された要素の位置を返します。

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

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

int main()
{
	std::vector<int> v1, v2;
	v1.push_back(0);
	v1.push_back(1);
	v1.push_back(3);
	v2.push_back(1);
	v2.push_back(2);

	std::vector<int> result(v1.size() + v2.size());
	std::vector<int>::iterator it = std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

	std::for_each(result.begin(), it, Println);
}

実行結果

0
3

set_symmetric_difference

set_symmetric_difference関数は、指定した2つのソートされた範囲の一方にだけ含まれている要素からなる新たな集合を生成します。 いわゆる「互いに素な集合」を作る関数です。

namespace std {
	template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
	OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

	template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
	OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第1、第2引数で1つのソート済み範囲を、第3、4引数でもう1つのソート済み範囲を指定します。 第5引数で指定した位置へ、一方の範囲にだけ含まれている要素からなる集合を出力します。 第6引数は、要素の比較に用いる関数や関数オブジェクトです。
戻り値は、最後に出力された要素の位置を返します。

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

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

int main()
{
	std::vector<int> v1, v2;
	v1.push_back(0);
	v1.push_back(1);
	v1.push_back(3);
	v2.push_back(1);
	v2.push_back(2);

	std::vector<int> result(v1.size() + v2.size());
	std::vector<int>::iterator it = std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

	std::for_each(result.begin(), it, Println);
}

実行結果

0
2
3


練習問題

問題@ ある範囲内に、ある値を持つ要素が幾つあるか調べるために equal_range関数を使う方法があります。 このような目的を果たすプログラムを作成して下さい。


解答ページはこちら

参考リンク

更新履歴

'2016/11/30 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ