C++11/C++20 アルゴリズム関数まとめ

C++
2022.07.24

C++11 の algorithm ライブラリと C++20 の ranges ライブラリでは、様々なデータコレクションに対して共通の操作ができます。これらの特徴についてまとめます。

サポートするコレクション

サポートするコレクション

STL コンテナ(vector, list, string, …)のほかに、組み込み配列も渡せます。
コレクションは少なくともシーケンシャルアクセス可能でなければなりません。一部の関数はランダムアクセス必須か、計算量が大きくなります。

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

int main(int argc, char* argv[]) {
	// 配列
	int array[] = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_array1 = std::find(array, array + 9, 1);
	auto found_array2 = std::find(std::begin(array), std::end(array), 1);
	auto found_array3 = std::ranges::find(array, 1);
	std::sort(array, array + 9);
	std::sort(std::begin(array), std::end(array));
	std::ranges::sort(array);

	// ランダムアクセス可能なコンテナ
	std::vector<int> vector = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_vector1 = std::find(vector.begin(), vector.end(), 1);
	auto found_vector2 = std::find(std::begin(vector), std::end(vector), 1);
	auto found_vector3 = std::ranges::find(vector, 1);
	std::sort(vector.begin(), vector.end());
	std::sort(std::begin(vector), std::end(vector));
	std::ranges::sort(vector);

	// シーケンシャルアクセス可能なコンテナ
	std::list<int> list = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_list1 = std::find(list.begin(), list.end(), 1);
	auto found_list2 = std::find(std::begin(list), std::end(list), 1);
	auto found_list3 = std::ranges::find(list, 1);
	//動作するが、計算量が大きくなる
	std::list<int> list2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	bool binary_search_list1 = std::binary_search(list2.begin(), list2.end(), 1);
	bool binary_search_list2 = std::ranges::binary_search(list2.begin(), list2.end(), 1);
	bool binary_search_list3 = std::ranges::binary_search(list2, 1);
	//コンパイルエラー
	//std::sort(list.begin(), list.end());
	//std::sort(std::begin(list), std::end(list));
	//std::ranges::sort(list);

	// 文字列
	std::string string = "674589123";
	auto found_string1 = std::find(string.begin(), string.end(), '1');
	auto found_string2 = std::find(std::begin(string), std::end(string), '1');
	auto found_string3 = std::ranges::find(string, '1');
	std::sort(string.begin(), string.end());
	std::sort(std::begin(string), std::end(string));
	std::ranges::sort(string);

	return 0;
}

STLコンテナの対応状況

#include <algorithm>
#include <iostream>
#include <array>
#include <deque>
#include <vector>
#include <span>
#include <forward_list>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>

int main(int argc, char* argv[]) {
	// ランダムアクセス可能なコンテナ
	std::array<int, 9> array = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	std::ranges::sort(array);

	std::deque<int> deque = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	std::ranges::sort(deque);

	std::vector<int> vector = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	std::ranges::sort(vector);

	std::span<int> span(vector);
	std::ranges::sort(vector);

	// シーケンシャルアクセス可能なコンテナ
	std::forward_list<int> forward_list = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_forward_list = std::ranges::find(forward_list, 1);

	std::list<int> list = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_list = std::ranges::find(list, 1);

	std::map<int, std::string> map = { {6, "f"}, {7, "g"}, {4, "d"}, {5, "e"}, {8, "h"}, {9, "i"}, {1, "a"}, {2, "b"}, {3, "c"} };
	auto found_map = std::ranges::find(map, std::pair<int const, std::string>{ 1, "a" });

	std::multimap<int, std::string> multimap = { {6, "f"}, {7, "g"}, {4, "d"}, {5, "e"}, {8, "h"}, {9, "i"}, {1, "a"}, {2, "b"}, {3, "c"} };
	auto found_multimap = std::ranges::find(multimap, std::pair<int const, std::string>{ 1, "a" });

	std::unordered_map<int, std::string> unordered_map = { {6, "f"}, {7, "g"}, {4, "d"}, {5, "e"}, {8, "h"}, {9, "i"}, {1, "a"}, {2, "b"}, {3, "c"} };
	auto found_unordered_map = std::ranges::find(unordered_map, std::pair<int const, std::string>{ 1, "a" });

	std::unordered_multimap<int, std::string> unordered_multimap = { {6, "f"}, {7, "g"}, {4, "d"}, {5, "e"}, {8, "h"}, {9, "i"}, {1, "a"}, {2, "b"}, {3, "c"} };
	auto found_unordered_multimap = std::ranges::find(unordered_multimap, std::pair<int const, std::string>{ 1, "a" });

	std::set<int> set = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_set = std::ranges::find(set, 1);

	std::multiset<int> multiset = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_multiset = std::ranges::find(multiset, 1);

	std::unordered_set<int> unordered_set = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_unordered_set = std::ranges::find(unordered_set, 1);

	std::unordered_multiset<int> unordered_multiset = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
	auto found_unordered_multiset = std::ranges::find(unordered_multiset, 1);

	// 終端しかアクセスできない
	std::queue<int> queue({ 6, 7, 4, 5, 8, 9, 1, 2, 3 });
	//auto found_queue = std::ranges::find(queue, 1);

	std::priority_queue<int> priority_queue { {}, { 6, 7, 4, 5, 8, 9, 1, 2, 3 } };
	//auto found_priority_queue = std::ranges::find(priority_queue, 1);

	std::stack<int> stack({ 6, 7, 4, 5, 8, 9, 1, 2, 3 });
	//auto found_stack = std::ranges::find(stack, 1);

	return 0;
}

コレクションの指定方法

std::xxx(C++11): 対象の範囲 [first, last) のイテレータ―を指定します。
std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
std::ranges::xxx(C++20): 対象の範囲を直接指定します。
std::begin(), std::end() は配列、コンテナ区別なく使用できます(cbegin, rbegin, crbegin なども同様)。
コレクション全体だけでなく、イテレーター(ポインター含む)・view を使うことで特定の範囲を渡すことができます。

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

int main(int argc, char* argv[]) {
	// 配列
	int a[] = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };

	// std::xxx(C++11): 対象の範囲 [first, last) のイテレータ―を指定します。
	std::sort(a, a + 9);
	std::sort(std::begin(a), std::end(a));

	// std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
	std::ranges::sort(a, a + 9);
	std::ranges::sort(std::begin(a), std::end(a));

	// std::ranges::xxx(C++20): 対象の範囲を直接指定します。
	std::ranges::sort(a);

	// コレクション全体だけでなく、イテレーター(ポインター含む)・view を使うことで特定の範囲を渡すことができます。
	std::sort(a, std::find(a, a + 9, 1));
	std::ranges::sort(std::ranges::subrange(std::begin(a), std::ranges::find(a, 1)));

	// vector
	std::vector<int> v = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };

	// std::xxx(C++11): 対象の範囲 [first, last) のイテレータ―を指定します。
	std::sort(v.begin(), v.end());
	std::sort(std::begin(v), std::end(v));

	// std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
	std::ranges::sort(v.begin(), v.end());
	std::ranges::sort(std::begin(v), std::end(v));

	// std::ranges::xxx(C++20): 対象の範囲を直接指定します。
	std::ranges::sort(v);

	// コレクション全体だけでなく、イテレーター(ポインター含む)・view を使うことで特定の範囲を渡すことができます。
	std::sort(v.begin(), std::find(v.begin(), v.end(), 1));
	std::ranges::sort(std::ranges::subrange(v.begin(), std::find(v.begin(), v.end(), 1)));

	return 0;
}

戻り値の違い

同名の関数でも std::xxx(C++11) と std::ranges::xxx(C++20) で戻り値が違うものがあります。

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

int main(int argc, char* argv[]) {
	std::cout << "//// 検索" << std::endl;

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

	// C++11: 2つ目の範囲が最初に見つかった位置
	auto search11 = std::search(v.begin(), v.end(), k.begin(), k.end());
	std::cout << "位置:" << std::distance(v.begin(), search11) << " 値:" << *search11; // 位置:3 値:4
	std::cout << std::endl << std::endl;

	// C++20: 2つ目の範囲が最初に見つかった範囲
	auto search20 = std::ranges::search(v, k);
	std::cout << "範囲:[" << std::distance(v.begin(), search20.begin()) << ", " << std::distance(v.begin(), search20.end()) << ") 値:";
	for (auto x : search20) { std::cout << x << " "; } // 範囲:[3, 5) 値:4 5
	std::cout << std::endl << std::endl;

	return 0;
}

関数オブジェクト

比較関数

要素の比較のための関数を指定することができます。

  • シーケンシャルアクセスする関数
    • 下記以外
    • 等しい(==)とき true を返す
  • ランダムアクセスする関数
    • ソートや二分探索など
    • より小さい(<)とき true を返す
#include <algorithm>
#include <iostream>
#include <vector>

struct S1 {
	const char* s1;
};

int main(int argc, char* argv[]) {
	// 等しいとき true を返す関数を渡す
	std::vector<S1> v1 = { {"111"}, {"22"}, {"3"} };
	std::vector<S1> k1 = { {"22"}, {"3"} };
	auto search = std::ranges::search(v1, k1,
		[](auto& a, auto& b) { return std::atoi(a.s1) == std::atoi(b.s1); }); // pred

	std::cout << "範囲:[" << std::distance(v1.begin(), search.begin()) << ", " << std::distance(v1.begin(), search.end()) << ") 値:";
	for (auto i : search) { std::cout << i.s1 << " "; } // 範囲:[1, 3) 値:22 3
	std::cout << std::endl << std::endl;

	// より小さいとき true を返す関数を渡す
	std::vector<S1> v2 = { {"111"}, {"222"}, {"333"} };
	S1 k2 = { "222" };
	bool binary_search = std::ranges::binary_search(v2, k2,
		[](auto& a, auto& b) { return std::atoi(a.s1) < std::atoi(b.s1); }); // comp

	std::cout << "結果:" << std::boolalpha << binary_search << std::endl; // 結果:true

	return 0;
}

射影(projection)関数

比較対象を決めるための関数を指定することができます。

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

struct S1 {
	const char* s1;
};

int main(int argc, char* argv[]) {
	// 等しいとき true を返す関数を渡す
	std::vector<S1> v1 = { {"111"}, {"22"}, {"3"} };
	std::vector<S1> k1 = { {"22"}, {"3"} };
	auto search = std::ranges::search(v1, k1,
		{}, // pred
		[](const auto& a) { return std::atoi(a.s1); }, // proj1
		[](const auto& b) { return std::atoi(b.s1); }); // proj2

	std::cout << "範囲:[" << std::distance(v1.begin(), search.begin())
		<< ", " << std::distance(v1.begin(), search.end()) << ") 値:";
	for (auto i : search) { std::cout << i.s1 << " "; } // 範囲:[1, 3) 値:22 3
	std::cout << std::endl << std::endl;

	return 0;
}

関数オブジェクトの指定方法

比較関数、射影(projection)関数などの関数オブジェクトを渡す例です。

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

struct S1 {
	const char* s1;
};

bool comp_s1(const S1& a, const S1& b) {
	return std::atoi(a.s1) < std::atoi(b.s1);
}

int main(int argc, char* argv[]) {
	std::vector<S1> v1 = { {"111"}, {"22"}, {"3"} };
	std::vector<int> v2 = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };

	// ラムダ関数
	std::ranges::sort(v1, [](auto& a, auto& b) { return std::atoi(a.s1) < std::atoi(b.s1); });

	// ラムダ関数変数
	auto f = [](auto& a, auto& b) { return std::atoi(a.s1) < std::atoi(b.s1); };
	std::ranges::sort(v1, f);

	// 関数
	std::ranges::sort(v1, comp_s1);

	// 組み込み関数
	std::ranges::sort(v2, std::ranges::greater()); // 大きい順にソート

	// 射影(projection)にはメンバー変数ポインターも可
	std::ranges::sort(v1, strcmp, &S1::s1); // 辞書順にソート

	return 0;
}

演算子オーバーロードによる比較動作の実装

比較関数を指定しない場合、==, < 演算子を使って要素が比較されますが、演算子のオーバーロードで比較動作を実装する例を示します。
なお、< 演算子のオーバーロードはコンパイルが通らず、うまくいかなかったので、代わりに三方演算子 <=> をオーバーロードしています。

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

class S1 {
public:
	const char* s1;

	bool operator==(const S1& s) const {
		std::cout << "S1::== ";
		return std::atoi(this->s1) == std::atoi(s.s1);
	}
	/*
	//binary_search でエラー
	//エラー (アクティブ)	E0304	オーバーロードされた関数 "std::ranges::_Binary_search_fn::operator()" のインスタンスが引数リストと一致しません
	bool operator<(const S1& s) const {
		std::cout << "S1::< ";
		return std::atoi(this->s1) < std::atoi(s.s1);
	}
	*/
	auto operator<=>(const S1& s) const {
		std::cout << "S1::<=> ";
		return std::atoi(this->s1) - std::atoi(s.s1);
	}
};

class S2 {
public:
	const char* s2;
};

bool operator==(const class S2& a, const class S2& b) {
	std::cout << "== ";
	return std::atoi(a.s2) == std::atoi(b.s2);
}
/*
//binary_search でエラー
//エラー (アクティブ)	E0304	オーバーロードされた関数 "std::ranges::_Binary_search_fn::operator()" のインスタンスが引数リストと一致しません
bool operator<(const class S2& a, const class S2& b) {
	std::cout << "< ";
	return std::atoi(a.s2) < std::atoi(b.s2);
}
*/
auto operator<=>(const class S2& a, const class S2& b) {
	std::cout << "<=> ";
	return std::atoi(a.s2) - std::atoi(b.s2);
}

int main(int argc, char* argv[]) {
	// std::ranges::search
	{
		// 等しいとき true を返す関数を渡す
		std::vector<int> v = { 6, 7, 4, 5, 8, 9, 1, 2, 3 };
		std::vector<int> k = { 5, 8 };
		auto search = std::ranges::search(v, k, [](int a, int b) { return a == b; });
		std::cout << "位置:" << std::distance(v.begin(), search.begin()) << std::endl; // 位置:3
	}
	{
		// オーバーロード operator==
		std::vector<S1> v = { {"111"}, {"22"}, {"3"} };
		std::vector<S1> k = { {"22"}, {"3"} };
		auto search = std::ranges::search(v, k);
		std::cout << "位置:" << std::distance(v.begin(), search.begin()) << std::endl; // S1::== S1::== S1::== 位置:1
	}
	{
		// 非メンバー operator==
		std::vector<S2> v = { {"111"}, {"22"}, {"3"} };
		std::vector<S2> k = { {"22"}, {"3"} };
		auto search = std::ranges::search(v, k);
		std::cout << "位置:" << std::distance(v.begin(), search.begin()) << std::endl; // == == == 位置:1
	}

	// std::ranges::binary_search
	{
		// より小さいとき true を返す関数を渡す
		std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		bool binary_search = std::ranges::binary_search(v, 3, [](int a, int b) { return a < b; });
		std::cout << "結果:" << std::boolalpha << binary_search << std::endl; // 結果:true
	}
	{
		// オーバーロード operator<=>
		std::vector<S1> v = { {"111"}, {"222"}, {"333"} };
		S1 k = { "222" };
		bool binary_search = std::ranges::binary_search(v, k);
		std::cout << "結果:" << std::boolalpha << binary_search << std::endl; // S1::<=> S1::<=> S1::<=> 結果:true
	}
	{
		// 非メンバー operator<=>
		std::vector<S2> v = { {"111"}, {"222"}, {"333"} };
		S2 k = { "222" };
		bool binary_search = std::ranges::binary_search(v, k);
		std::cout << "結果:" << std::boolalpha << binary_search << std::endl; // <=> <=> <=> 結果:true
	}

	return 0;
}

コメント

タイトルとURLをコピーしました