C++11/C++20 の検索系の関数についてのまとめです。
find: 値が最初に見つかった位置
find_if: 条件を最初に満たす位置
find_if_not: 条件を最初に満たさない位置
find_end: 範囲が最後に見つかった位置/範囲
find_first_of: いずれかの値が最初に見つかった位置
adjacent_find: 隣の要素が一致する最初の位置
adjacent_find_if: 隣の要素が条件を満たす最初の位置
search: 2つ目の範囲が最初に見つかった位置/範囲
search_n: 指定した個数指定した値が連続する範囲が最初に見つかった位置/範囲
binary_search: 二分探索で見つかったか
lower_bound: 二分探索で指定した値以上の最初の位置
upper_bound: 二分探索で指定した値より大きい最初の位置
equal_range: 二分探索で指定した値と等しい範囲(lower_bound,upper_boundの組)
使用しないで実装した例(一部)
#include <iostream>
/** v 内の [first, last) の範囲と値を出力 範囲:[0, 9) 値:1 2 3 4 5 4 5 6 6 */
template<class T, class U>
static void output(T&& v, U&& first, U&& last) {
std::cout << "範囲:[" << std::distance(std::begin(v), first) << ", " << std::distance(std::begin(v), last) << ")";
std::cout << " 値:";
for (auto i = first; i != last; ++i) {
std::cout << *i << " ";
}
std::cout << std::endl << std::endl;
}
/** v 内の it の位置と値を出力 位置:2 値:3 */
template<class T, class U>
static void output(T&& v, U&& it) {
std::cout << "位置:" << std::distance(std::begin(v), it);
std::cout << " 値:";
if (&*it == nullptr || it == std::end(v)) {
std::cout << "end";
}
else {
std::cout << *it;
}
std::cout << std::endl << std::endl;
}
#include <algorithm>
#include <iostream>
#include <string>
#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::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::vector<int> v2 = { 4, 5 };
std::cout << "std::vector<int> v2 = ";
output(v2, v2.begin(), v2.end());
std::cout << "find // 最初に見つかった位置" << std::endl;
auto find = v.begin();
for (; find != v.end(); ++find) {
if (3 == *find) {
break;
}
}
output(v, find); // 位置:2 値:3
std::cout << "find_end // 2つ目の範囲が最後に見つかった位置" << std::endl;
auto find_end = v.end();
if (v2.begin() != v2.end()) {
for (auto i = v.begin(); i != v.end(); ++i) {
auto i_tmp = i;
for (auto i2 = v2.begin(); i2 != v2.end(); ++i2, ++i_tmp) {
if (i_tmp == v.end()) {
goto find_end_not_found_all;
}
if (*i_tmp != *i2) {
goto find_end_next_v;
}
}
find_end = i;
find_end_next_v:;
}
find_end_not_found_all:;
}
output(v, find_end); // 位置:5 値:4
std::cout << "find_first_of // 2つ目の範囲のいずれかの要素が最初に見つかった位置" << std::endl;
auto find_first_of = v.end();
if (v2.begin() != v2.end()) {
for (auto i = v.begin(); i != v.end(); ++i) {
for (auto i2 = v2.begin(); i2 != v2.end(); ++i2) {
if (*i == *i2) {
find_first_of = i;
goto find_first_of_all_found;
}
}
}
find_first_of_all_found:;
}
output(v, find_first_of); // 位置:3 値:4
std::cout << "adjacent_find // 隣の要素が一致する最初の位置" << std::endl;
auto adjacent_find = v.end();
if (v.begin() != v.end()) {
for (auto i = v.begin(); i + 1 != v.end(); ++i) {
if (*i == *(i + 1)) {
adjacent_find = i;
break;
}
}
}
output(v, adjacent_find); // 位置:7 値:6
std::cout << "search // 2つ目の範囲が最初に見つかった位置" << std::endl;
auto search = v.end();
if (v2.begin() != v2.end()) {
for (auto i = v.begin(); i != v.end(); ++i) {
auto i_tmp = i;
for (auto i2 = v2.begin(); i2 != v2.end(); ++i2, ++i_tmp) {
if (i_tmp == v.end()) {
goto search_not_found_all;
}
if (*i_tmp != *i2) {
goto search_next_v;
}
}
search = i;
break;
search_next_v:;
}
search_not_found_all:;
}
output(v, search); // 位置:3 値:4
std::cout << "search_n // 指定した個数指定した値が連続する範囲が最初に見つかった位置" << std::endl;
auto search_n = v.end();
if (v2.begin() != v2.end()) {
for (auto i = v.begin(); i != v.end(); ++i) {
auto i_tmp = i;
for (int i2 = 0; i2 < 2; ++i2, ++i_tmp) {
if (i_tmp == v.end()) {
goto search_n_not_found_all;
}
if (*i_tmp != 6) {
goto search_n_next_v;
}
}
search_n = i;
break;
search_n_next_v:;
}
search_n_not_found_all:;
}
output(v, search_n); // 位置:7 値:6
return 0;
}
ソートされているデータを検索する場合は二分探索が使用できます。
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
int main(int argc, char* argv[]) {
std::cout << std::boolalpha;
std::cout << "//// 二分探索(バイナリーサーチ)" << std::endl;
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
{
std::cout << "binary_search // 二分探索で見つかったか" << std::endl;
auto i_first = v.begin();
int distance = std::distance(v.begin(), v.end());
while (distance >= 1) {
auto i = i_first;
int d = distance / 2;
std::advance(i, d);
if (*i < 3) {
i_first = i + 1;
distance -= d + 1;
} else {
distance = d;
}
}
bool binary_search = (i_first != v.end() && *i_first <= 3);
std::cout << binary_search; // true
std::cout << std::endl << std::endl;
}
{
std::cout << "lower_bound // 二分探索で指定した値以上の最初の位置" << std::endl;
auto lower_bound = v.begin();
int distance = std::distance(v.begin(), v.end());
while (distance >= 1) {
auto i = lower_bound;
int d = distance / 2;
std::advance(i, d);
if (*i < 3) {
lower_bound = i + 1;
distance -= d + 1;
} else {
distance = d;
}
}
output(v, lower_bound); // 位置:2 値:3
}
{
std::cout << "upper_bound // 二分探索で指定した値より大きい最初の位置" << std::endl;
auto upper_bound = v.begin();
int distance = std::distance(v.begin(), v.end());
while (distance >= 1) {
auto i = upper_bound;
int d = distance / 2;
std::advance(i, d);
if (*i <= 3) {
upper_bound = i + 1;
distance -= d + 1;
} else {
distance = d;
}
}
output(v, upper_bound); // 位置:3 値:4
}
{
printf("int* res_bsearch = (int*)bsearch(&key, a, sizeof(a) / sizeof(int), sizeof(int),... // 二分探索\n");
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int key = 3;
int* res_bsearch = (int*)bsearch(&key, a, sizeof(a) / sizeof(int), sizeof(int),
[](const void* a, const void* b) { return *(const int*)a - *(const int*)b; });
if (NULL == res_bsearch) {
printf("見つからなかった\n\n");
} else {
printf("位置:%d 値:%d\n\n", res_bsearch - a, *res_bsearch); // 位置:2 値:3
}
}
return 0;
}
std::find, std::search, … (C++11)
第1,2引数に指定した範囲を検索します。
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
std::cout << std::boolalpha;
std::cout << "//// 二分探索(バイナリーサーチ)" << std::endl;
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::cout << "// 二分探索で見つかったか" << std::endl;
std::cout << "std::binary_search(v.begin(), v.end(), 3);" << std::endl;
std::cout << std::binary_search(v.begin(), v.end(), 3);
std::cout << std::endl << std::endl; // true
std::cout << "std::binary_search(v.begin(), v.end(), 4, [](int x, int y) { return x < y; });" << std::endl;
std::cout << std::binary_search(v.begin(), v.end(), 4, [](int x, int y) { return x < y; });
std::cout << std::endl << std::endl; // true
std::cout << "// 二分探索で指定した値以上の最初の位置" << std::endl;
std::cout << "auto lower_bound = std::lower_bound(v.begin(), v.end(), 3);" << std::endl;
auto lower_bound = std::lower_bound(v.begin(), v.end(), 3);
output(v, lower_bound); // 位置:2 値:3
std::cout << "// 二分探索で指定した値より大きい最初の位置" << std::endl;
std::cout << "auto upper_bound = std::upper_bound(v.begin(), v.end(), 3);" << std::endl;
auto upper_bound = std::upper_bound(v.begin(), v.end(), 3);
output(v, upper_bound); // 位置:3 値:4
std::cout << "// 二分探索で指定した値と等しい範囲(lower_bound,upper_boundの組)" << std::endl;
std::cout << "auto equal_range = std::equal_range(v.begin(), v.end(), 3);" << std::endl;
auto equal_range = std::equal_range(v.begin(), v.end(), 3);
output(v, equal_range.first, equal_range.second); // 範囲:[2, 3) 値:3
return 0;
}
std::binary_search, … (C++11)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
std::cout << std::boolalpha;
std::cout << "//// 二分探索(バイナリーサーチ)" << std::endl;
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::cout << "// 二分探索で見つかったか" << std::endl;
std::cout << "std::binary_search(v.begin(), v.end(), 3);" << std::endl;
std::cout << std::binary_search(v.begin(), v.end(), 3);
std::cout << std::endl << std::endl; // true
std::cout << "std::binary_search(v.begin(), v.end(), 4, [](int x, int y) { return x < y; });" << std::endl;
std::cout << std::binary_search(v.begin(), v.end(), 4, [](int x, int y) { return x < y; });
std::cout << std::endl << std::endl; // true
std::cout << "// 二分探索で指定した値以上の最初の位置" << std::endl;
std::cout << "auto lower_bound = std::lower_bound(v.begin(), v.end(), 3);" << std::endl;
auto lower_bound = std::lower_bound(v.begin(), v.end(), 3);
output(v, lower_bound); // 位置:2 値:3
std::cout << "// 二分探索で指定した値より大きい最初の位置" << std::endl;
std::cout << "auto upper_bound = std::upper_bound(v.begin(), v.end(), 3);" << std::endl;
auto upper_bound = std::upper_bound(v.begin(), v.end(), 3);
output(v, upper_bound); // 位置:3 値:4
std::cout << "// 二分探索で指定した値と等しい範囲(lower_bound,upper_boundの組)" << std::endl;
std::cout << "auto equal_range = std::equal_range(v.begin(), v.end(), 3);" << std::endl;
auto equal_range = std::equal_range(v.begin(), v.end(), 3);
output(v, equal_range.first, equal_range.second); // 範囲:[2, 3) 値:3
return 0;
}
std::ranges::find, std::ranges::search, … (C++20)
ranges の関数は第1引数に範囲を指定します。第1,2引数に範囲を指定するバージョンも用意されています。
範囲対範囲の検索を行う関数は、戻り値に開始と終了のペアを返します。
#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::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::vector<int> v2 = { 4, 5 };
std::cout << "std::vector<int> v2 = ";
output(v2, v2.begin(), v2.end());
std::cout << "// 最初に見つかった位置" << std::endl;
std::cout << "auto find = std::ranges::find(v, 3);" << std::endl;
auto find = std::ranges::find(v, 3);
output(v, find); // 位置:2 値:3
std::cout << "auto find_if = std::ranges::find_if(v, [](int x) { return 3 == x; });" << std::endl;
auto find_if = std::ranges::find_if(v, [](int x) { return 3 == x; });
output(v, find_if); // 位置:2 値:3
std::cout << "auto find_if_not = std::ranges::find_if_not(v, [](int x) { return 3 == x; });" << std::endl;
auto find_if_not = std::ranges::find_if_not(v, [](int x) { return 3 == x; });
output(v, find_if_not); // 位置:0 値:1
std::cout << "// 2つ目の範囲が最後に見つかった範囲" << std::endl;
std::cout << "auto find_end = std::ranges::find_end(v, v2);" << std::endl;
auto find_end = std::ranges::find_end(v, v2);
output(v, find_end.begin(), find_end.end()); // 範囲:[5, 7) 値:4 5
std::cout << "// 2つ目の範囲のいずれかの要素が最初に見つかった位置" << std::endl;
std::cout << "auto find_first_of = std::ranges::find_first_of(v, v2);" << std::endl;
auto find_first_of = std::ranges::find_first_of(v, v2);
output(v, find_first_of); // 位置:3 値:4
std::cout << "// 隣の要素が一致する最初の位置" << std::endl;
std::cout << "auto adjacent_find = std::ranges::adjacent_find(v);" << std::endl;
auto adjacent_find = std::ranges::adjacent_find(v);
output(v, adjacent_find); // 位置:7 値:6
std::cout << "// 隣の要素が条件を満たす最初の位置" << std::endl;
std::cout << "auto adjacent_find_if = std::ranges::adjacent_find(v, [](int x, int y) { return x > y; });" << std::endl;
auto adjacent_find_if = std::ranges::adjacent_find(v, [](int x, int y) { return x > y; });
output(v, adjacent_find_if); // 位置:4 値:5
std::cout << "// 2つ目の範囲が最初に見つかった範囲" << std::endl;
std::cout << "auto search = std::ranges::search(v, v2);" << std::endl;
auto search = std::ranges::search(v, v2);
output(v, search.begin(), search.end()); // 範囲:[3, 5) 値:4 5
std::cout << "// 指定した個数指定した値が連続する範囲が最初に見つかった範囲" << std::endl;
std::cout << "auto search_n = std::ranges::search_n(v, 2, 6);" << std::endl;
auto search_n = std::ranges::search_n(v, 2, 6);
output(v, search_n.begin(), search_n.end()); // 範囲:[7, 9) 値:6 6
return 0;
}
std::ranges::binary_search, … (C++20)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
std::cout << std::boolalpha;
std::cout << "//// 二分探索(バイナリーサーチ)" << std::endl;
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::cout << "// 二分探索で見つかったか" << std::endl;
std::cout << "std::ranges::binary_search(v, 3);" << std::endl;
std::cout << std::ranges::binary_search(v, 3);
std::cout << std::endl << std::endl; // true
std::cout << "std::ranges::binary_search(v, 4, [](int x, int y) { return x < y; });" << std::endl;
std::cout << std::ranges::binary_search(v, 4, [](int x, int y) { return x < y; });
std::cout << std::endl << std::endl; // true
std::cout << "// 二分探索で指定した値以上の最初の位置" << std::endl;
std::cout << "auto lower_bound = std::ranges::lower_bound(v, 3);" << std::endl;
auto lower_bound = std::ranges::lower_bound(v, 3);
output(v, lower_bound); // 位置:2 値:3
std::cout << "// 二分探索で指定した値より大きい最初の位置" << std::endl;
std::cout << "auto upper_bound = std::ranges::upper_bound(v, 3);" << std::endl;
auto upper_bound = std::ranges::upper_bound(v, 3);
output(v, upper_bound); // 位置:3 値:4
std::cout << "// 二分探索で指定した値と等しい範囲(lower_bound,upper_boundの組)" << std::endl;
std::cout << "auto equal_range = std::ranges::equal_range(v, 3);" << std::endl;
auto equal_range = std::ranges::equal_range(v, 3);
output(v, equal_range.begin(), equal_range.end()); // 範囲:[2, 3) 値:3
return 0;
}
std::ranges::find, std::ranges::search, … (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::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::vector<int> v2 = { 4, 5 };
std::cout << "std::vector<int> v2 = ";
output(v2, v2.begin(), v2.end());
std::cout << "// 最初に見つかった位置" << std::endl;
std::cout << "auto find = std::ranges::find(v.begin(), v.end(), 3);" << std::endl;
auto find = std::ranges::find(v.begin(), v.end(), 3);
output(v, find); // 位置:2 値:3
std::cout << "auto find_if = std::ranges::find_if(v.begin(), v.end(), [](int x) { return 3 == x; });" << std::endl;
auto find_if = std::ranges::find_if(v.begin(), v.end(), [](int x) { return 3 == x; });
output(v, find_if); // 位置:2 値:3
std::cout << "auto find_if_not = std::ranges::find_if_not(v.begin(), v.end(), [](int x) { return 3 == x; });" << std::endl;
auto find_if_not = std::ranges::find_if_not(v.begin(), v.end(), [](int x) { return 3 == x; });
output(v, find_if_not); // 位置:0 値:1
std::cout << "// 2つ目の範囲が最後に見つかった範囲" << std::endl;
std::cout << "auto find_end = std::ranges::find_end(v.begin(), v.end(), v2.begin(), v2.end());" << std::endl;
auto find_end = std::ranges::find_end(v.begin(), v.end(), v2.begin(), v2.end());
output(v, find_end.begin(), find_end.end()); // 範囲:[5, 7) 値:4 5
std::cout << "// 2つ目の範囲のいずれかの要素が最初に見つかった位置" << std::endl;
std::cout << "auto find_first_of = std::ranges::find_first_of(v.begin(), v.end(), v2.begin(), v2.end());" << std::endl;
auto find_first_of = std::ranges::find_first_of(v.begin(), v.end(), v2.begin(), v2.end());
output(v, find_first_of); // 位置:3 値:4
std::cout << "// 隣の要素が一致する最初の位置" << std::endl;
std::cout << "auto adjacent_find = std::ranges::adjacent_find(v.begin(), v.end());" << std::endl;
auto adjacent_find = std::ranges::adjacent_find(v.begin(), v.end());
output(v, adjacent_find); // 位置:7 値:6
std::cout << "// 隣の要素が条件を満たす最初の位置" << std::endl;
std::cout << "auto adjacent_find_if = std::ranges::adjacent_find(v.begin(), v.end(), [](int x, int y) { return x > y; });" << std::endl;
auto adjacent_find_if = std::ranges::adjacent_find(v.begin(), v.end(), [](int x, int y) { return x > y; });
output(v, adjacent_find_if); // 位置:4 値:5
std::cout << "// 2つ目の範囲が最初に見つかった範囲" << std::endl;
std::cout << "auto search = std::ranges::search(v.begin(), v.end(), v2.begin(), v2.end());" << std::endl;
auto search = std::ranges::search(v.begin(), v.end(), v2.begin(), v2.end());
output(v, search.begin(), search.end()); // 範囲:[3, 5) 値:4 5
std::cout << "// 指定した個数指定した値が連続する範囲が最初に見つかった範囲" << std::endl;
std::cout << "auto search_n = std::ranges::search_n(v.begin(), v.end(), 2, 6);" << std::endl;
auto search_n = std::ranges::search_n(v.begin(), v.end(), 2, 6);
output(v, search_n.begin(), search_n.end()); // 範囲:[7, 9) 値:6 6
return 0;
}
std::ranges::binary_search, … (C++20)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
std::cout << std::boolalpha;
std::cout << "//// 二分探索(バイナリーサーチ)" << std::endl;
std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "std::vector<int> v = ";
output(v, v.begin(), v.end());
std::cout << "// 二分探索で見つかったか" << std::endl;
std::cout << "std::ranges::binary_search(v.begin(), v.end(), 3);" << std::endl;
std::cout << std::ranges::binary_search(v.begin(), v.end(), 3);
std::cout << std::endl << std::endl; // true
std::cout << "std::ranges::binary_search(v.begin(), v.end(), 4, [](int x, int y) { return x < y; });" << std::endl;
std::cout << std::ranges::binary_search(v.begin(), v.end(), 4, [](int x, int y) { return x < y; });
std::cout << std::endl << std::endl; // true
std::cout << "// 二分探索で指定した値以上の最初の位置" << std::endl;
std::cout << "auto lower_bound = std::ranges::lower_bound(v.begin(), v.end(), 3);" << std::endl;
auto lower_bound = std::ranges::lower_bound(v.begin(), v.end(), 3);
output(v, lower_bound); // 位置:2 値:3
std::cout << "// 二分探索で指定した値より大きい最初の位置" << std::endl;
std::cout << "auto upper_bound = std::ranges::upper_bound(v.begin(), v.end(), 3);" << std::endl;
auto upper_bound = std::ranges::upper_bound(v.begin(), v.end(), 3);
output(v, upper_bound); // 位置:3 値:4
std::cout << "// 二分探索で指定した値と等しい範囲(lower_bound,upper_boundの組)" << std::endl;
std::cout << "auto equal_range = std::ranges::equal_range(v.begin(), v.end(), 3);" << std::endl;
auto equal_range = std::ranges::equal_range(v.begin(), v.end(), 3);
output(v, equal_range.begin(), equal_range.end()); // 範囲:[2, 3) 値:3
return 0;
}
コメント