ソート済みコレクション同士を比較・結合・抽出する関数の説明です。
概要
2つの範囲の要素はソート済みの必要があります。
要素はシーケンシャルアクセスが必要です。ランダムアクセスは必要ありません。
コレクションの指定方法は、
・std::xxx(C++03): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲を直接指定します。
出力先のイテレーターは、
・insert_itrator を指定した場合は、指定箇所以降に結果が挿入されます。
・通常のイテレーターを指定した場合は、指定箇所以降に結果が上書きされるので、あらかじめ容量を確保しておく必要があります。
比較関数には、より小さい(<)ときに true を返す関数を指定します。
詳細についてはこちらを参照してください。https://mappuri.com/program/cpp20-algorithm/
関数の説明
merge
2つのソート済みの範囲をソート済みの状態で結合します。
inplace_merge
2つのソート済みの範囲が連続して rr にあるとします。これらをソート済みの状態で結合します。
includes
ソート済み範囲 r1 にソート済み範囲 r2 の全ての要素が含まれているか調べます。
set_difference
ソート済み範囲 r1 からソート済み範囲 r2 に含まれない要素を抽出します。(差集合)
set_intersection
2つのソート済み範囲の両方に含まれる要素を抽出します。(積集合)
set_symmetric_difference
2つのソート済み範囲の両方に含まれない要素を抽出します。(対称差集合)
set_union
2つのソート済みの範囲をソート済みの状態で結合します。両方に含まれる要素は1つの要素にまとめられます。(和集合)
サンプルプログラム
C++03 イテレーター指定
#include <iostream>
/** r 内の [first, last) の範囲と値を出力 範囲:[0, 9) 値:1 2 3 4 5 4 5 6 6 */
template<class T, class U, class V>
static void output(T&& r, U&& first, V&& last) {
std::cout << "範囲:[" << std::distance(std::begin(r), first) << ", " << std::distance(std::begin(r), last) << ")";
std::cout << " 値:";
for (auto i = first; i != last; ++i) {
std::cout << *i << " ";
}
std::cout << std::endl;
}
#include <algorithm>
#include <iostream>
#include <list>
#include <vector>
int main(int argc, char* argv[]) {
std::vector<int> r1 = { 1, 2, 3, 3, 3, 4, 5 };
std::vector<int> r2 = { 1, 3, 3, 5, 7 };
// 2つのソート済みの範囲をソート済みの状態で結合します。
// insert_itrator を指定した場合は、指定箇所以降に結果が挿入されます。
std::list<int> r_merge;
std::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), std::inserter(r_merge, r_merge.end()));
output(r_merge, r_merge.begin(), r_merge.end());
// 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// 通常のイテレーターを指定した場合は、指定箇所以降に結果が上書きされるので、あらかじめ容量を確保しておく必要があります。
std::vector<int> v_merge(r1.size() + r2.size());
auto merge = std::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), v_merge.begin());
output(v_merge, v_merge.begin(), merge);
// 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// 比較関数には、より小さい(<)ときに true を返す関数を指定します。
auto merge2 = std::merge(r1.begin(), r1.end(), r2.begin(), r2.end(), v_merge.begin(),
[](int a, int b) { std::cout << a << "," << b << " "; return a < b; });
output(v_merge, v_merge.begin(), merge2);
// 2,1 3,2 3,3 3,3 4,3 5,4 3,1 3,3 5,3 7,5 1,1 1,2 2,1 3,2 3,3 3,3 3,3 3,4 4,3 3,4 4,3 5,4 5,5 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// 2つのソート済みの範囲が連続して rr にあるとします。これらをソート済みの状態で結合します。
std::vector<int> rr = { 1, 2, 3, 3, 3, 4, 5, 1, 3, 3, 5, 7 };
std::inplace_merge(rr.begin(), rr.begin() + 7, rr.end());
output(rr, rr.begin(), rr.end());
// 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// ソート済み範囲 r1 にソート済み範囲 r2 の全ての要素が含まれているか調べます。
bool includes = std::includes(r1.begin(), r1.end(), r2.begin(), r2.end());
std::cout << std::boolalpha << includes << std::endl;
// false
// ソート済み範囲 r1 からソート済み範囲 r2 に含まれない要素を抽出します。(差集合)
std::list<int> r_set_difference;
std::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), std::inserter(r_set_difference, r_set_difference.end()));
output(r_set_difference, r_set_difference.begin(), r_set_difference.end());
// 範囲:[0, 3) 値:2 3 4
// 2つのソート済み範囲の両方に含まれる要素を抽出します。(積集合)
std::list<int> r_set_intersection;
std::set_intersection(r1.begin(), r1.end(), r2.begin(), r2.end(), std::inserter(r_set_intersection, r_set_intersection.end()));
output(r_set_intersection, r_set_intersection.begin(), r_set_intersection.end());
// 範囲:[0, 4) 値:1 3 3 5
// 2つのソート済み範囲の両方に含まれない要素を抽出します。(対称差集合)
std::list<int> r_set_symmetric_difference;
std::set_symmetric_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), std::inserter(r_set_symmetric_difference, r_set_symmetric_difference.end()));
output(r_set_symmetric_difference, r_set_symmetric_difference.begin(), r_set_symmetric_difference.end());
// 範囲:[0, 4) 値:2 3 4 7
// 2つのソート済みの範囲をソート済みの状態で結合します。両方に含まれる要素は1つの要素にまとめられます。(和集合)
std::list<int> r_set_union;
std::set_union(r1.begin(), r1.end(), r2.begin(), r2.end(), std::inserter(r_set_union, r_set_union.end()));
output(r_set_union, r_set_union.begin(), r_set_union.end());
// 範囲:[0, 8) 値:1 2 3 3 3 4 5 7
return 0;
}
C++20 range指定
#include <algorithm>
#include <iostream>
#include <list>
#include <vector>
int main(int argc, char* argv[]) {
std::vector<int> r1 = { 1, 2, 3, 3, 3, 4, 5 };
std::vector<int> r2 = { 1, 3, 3, 5, 7 };
// 2つのソート済みの範囲をソート済みの状態で結合します。
// insert_itrator を指定した場合は、指定箇所以降に結果が挿入されます。
std::list<int> r_merge;
std::ranges::merge(r1, r2, std::inserter(r_merge, r_merge.end()));
output(r_merge, r_merge.begin(), r_merge.end());
// 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// 通常のイテレーターを指定した場合は、指定箇所以降に結果が上書きされるので、あらかじめ容量を確保しておく必要があります。
std::vector<int> v_merge(r1.size() + r2.size());
auto merge = std::ranges::merge(r1, r2, v_merge.begin());
output(v_merge, v_merge.begin(), merge.out);
// 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// 比較関数には、より小さい(<)ときに true を返す関数を指定します。
auto merge2 = std::ranges::merge(r1, r2, v_merge.begin(),
[](int a, int b) { std::cout << a << "," << b << " "; return a < b; });
output(v_merge, v_merge.begin(), merge2.out);
// 1,1 1,2 3,2 3,3 3,3 3,3 3,4 3,4 5,4 5,5 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// 2つのソート済みの範囲が連続して rr にあるとします。これらをソート済みの状態で結合します。
std::vector<int> rr = { 1, 2, 3, 3, 3, 4, 5, 1, 3, 3, 5, 7 };
std::ranges::inplace_merge(rr, rr.begin() + 7);
output(rr, rr.begin(), rr.end());
// 範囲:[0, 12) 値:1 1 2 3 3 3 3 3 4 5 5 7
// ソート済み範囲 r1 にソート済み範囲 r2 の全ての要素が含まれているか調べます。
bool includes = std::ranges::includes(r1, r2);
std::cout << std::boolalpha << includes << std::endl;
// false
// ソート済み範囲 r1 からソート済み範囲 r2 に含まれない要素を抽出します。(差集合)
std::list<int> r_set_difference;
std::ranges::set_difference(r1, r2, std::inserter(r_set_difference, r_set_difference.end()));
output(r_set_difference, r_set_difference.begin(), r_set_difference.end());
// 範囲:[0, 3) 値:2 3 4
// 2つのソート済み範囲の両方に含まれる要素を抽出します。(積集合)
std::list<int> r_set_intersection;
std::ranges::set_intersection(r1, r2, std::inserter(r_set_intersection, r_set_intersection.end()));
output(r_set_intersection, r_set_intersection.begin(), r_set_intersection.end());
// 範囲:[0, 4) 値:1 3 3 5
// 2つのソート済み範囲の両方に含まれない要素を抽出します。(対称差集合)
std::list<int> r_set_symmetric_difference;
std::ranges::set_symmetric_difference(r1, r2, std::inserter(r_set_symmetric_difference, r_set_symmetric_difference.end()));
output(r_set_symmetric_difference, r_set_symmetric_difference.begin(), r_set_symmetric_difference.end());
// 範囲:[0, 4) 値:2 3 4 7
// 2つのソート済みの範囲をソート済みの状態で結合します。両方に含まれる要素は1つの要素にまとめられます。(和集合)
std::list<int> r_set_union;
std::ranges::set_union(r1, r2, std::inserter(r_set_union, r_set_union.end()));
output(r_set_union, r_set_union.begin(), r_set_union.end());
// 範囲:[0, 8) 値:1 2 3 3 3 4 5 7
return 0;
}
コメント