C++の標準テンプレートライブラリ(STL)は、多くのアルゴリズムを提供しており、これらはコンテナ内の要素を効率的に操作するためのものです。
1. 非変更アルゴリズム
これらのアルゴリズムは、操作対象となるコンテナの要素を変更しません。
1.1 findとfind_if
find(first, last, value):valueと一致する最初の要素を見つけてイテレータを返します（見つからなければlastを返します）。find_if(first, last, pred): 条件predを満たす最初の要素を見つけてイテレータを返します。find_end(first1, last1, first2, last2): サブシーケンスが最後に現れる位置を見つけてイテレータを返します。
std::vector<int> data = {10, 20, 30, 40, 50};
auto itr = std::find(data.begin(), data.end(), 30);
if (itr != data.end()) {
std::cout << "見つかった値: " << *itr << std::endl; // 出力: 30
}
auto itr2 = std::find_if(data.begin(), data.end(), [](int x) {
return x > 25;
});
std::cout << "25より大きい最初の値: " << *itr2 << std::endl; // 出力: 30
std::vector<int> sub = {20, 30};
auto itr3 = std::find_end(data.begin(), data.end(), sub.begin(), sub.end());
if (itr3 != data.end()) {
std::cout << "サブシーケンスの開始位置: " << std::distance(data.begin(), itr3) << std::endl; // 出力: 1
}1.2 countとcount_if
count(first, last, value):valueと一致する要素の数をカウントします。count_if(first, last, pred): 条件predを満たす要素の数をカウントします。
std::vector<int> sample = {1, 2, 2, 3, 4, 2, 5};
int count2 = std::count(sample.begin(), sample.end(), 2); // 2の出現回数: 3
int countEven = std::count_if(sample.begin(), sample.end(), [](int x) {
return x % 2 == 0;
}); // 偶数の個数: 41.3 for_each
範囲内の各要素に対して関数を適用します。
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::for_each(numbers.begin(), numbers.end(), [](int& x) {
x += 5; // 各要素に5を足す
});
// 現在numbersは{6, 7, 8, 9, 10}となる1.4 equalとmismatch
equal(first1, last1, first2): 2つの範囲が等しいかどうかを判定します。mismatch(first1, last1, first2): 2つの範囲で最初に異なる要素のペアのイテレータを返します。
std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {1, 2, 4};
bool isEqual = std::equal(vec1.begin(), vec1.end(), vec2.begin());
std::cout << "vec1 == vec2? " << std::boolalpha << isEqual << std::endl; // 出力: false
auto miss = std::mismatch(vec1.begin(), vec1.end(), vec2.begin());
if (miss.first != vec1.end()) {
std::cout << "不一致: " << *miss.first << " vs " << *miss.second << std::endl; // 出力: 3 vs 4
}1.5 all_of, any_of, none_of
範囲内の要素がすべて、または少なくとも1つ、または1つも満たさないかをチェックします。
std::vector<int> checkVec = {2, 4, 6, 8};
bool allEven = std::all_of(checkVec.begin(), checkVec.end(), [](int x) {
return x % 2 == 0;
}); // true
bool anyOdd = std::any_of(checkVec.begin(), checkVec.end(), [](int x) {
return x % 2 != 0;
}); // false
bool noneNegative = std::none_of(checkVec.begin(), checkVec.end(), [](int x) {
return x < 0;
}); // true2. 変更アルゴリズム
これらのアルゴリズムは、操作対象となるコンテナの要素を変更します。
2.1 copyとcopy_if
copy(first, last, d_first): 範囲[first, last)の要素をd_firstから始まる位置にコピーします。copy_if(first, last, d_first, pred): 条件predを満たす要素のみをコピーします。
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
std::copy(source.begin(), source.end(), destination.begin()); // destination: [1,2,3,4,5]
std::vector<int> evens;
std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
return x % 2 == 0;
}); // evens: [2,4]2.2 transform
範囲内の各要素に対して関数を適用し、結果を別の範囲に格納します。
std::vector<int> values = {1, 2, 3};
std::vector<int> squared(values.size());
std::transform(values.begin(), values.end(), squared.begin(), [](int x) {
return x * x;
}); // squared: [1,4,9]
std::vector<int> vecA = {1, 2, 3};
std::vector<int> vecB = {4, 5, 6};
std::vector<int> sumAB(vecA.size());
std::transform(vecA.begin(), vecA.end(), vecB.begin(), sumAB.begin(), [](int x, int y) {
return x + y;
}); // sumAB: [5,7,9]2.3 replace, replace_if, replace_copy
replace(first, last, old_value, new_value):old_valueをnew_valueに置き換えます。replace_if(first, last, pred, new_value): 条件predを満たす要素を置き換えます。replace_copy(first, last, d_first, old_value, new_value): コピー中に要素を置き換えます（元のコンテナは変更されません）。
std::vector<int> replaceVec = {1, 2, 3, 2, 5};
std::replace(replaceVec.begin(), replaceVec.end(), 2, 20); // replaceVec: [1,20,3,20,5]
std::replace_if(replaceVec.begin(), replaceVec.end(), [](int x) {
return x > 10;
}, 0); // replaceVec: [1,0,3,0,5]
std::vector<int> result;
std::replace_copy(replaceVec.begin(), replaceVec.end(), std::back_inserter(result), 3, 300); // result: [1,0,300,0,5]2.4 remove, remove_if, erase
remove(first, last, value):valueと一致する要素を「移動」し、新しい論理的終端イテレータを返します（実際には削除されませんが、eraseと組み合わせて使用します）。remove_if(first, last, pred): 条件predを満たす要素を移動します。
std::vector<int> rmVec = {1, 2, 3, 2, 4};
auto newEnd = std::remove(rmVec.begin(), rmVec.end(), 2); // rmVec: [1,3,4,2,2]
rmVec.erase(newEnd, rmVec.end()); // rmVec: [1,3,4]
rmVec = {1, 2, 3, 4, 5};
rmVec.erase(std::remove_if(rmVec.begin(), rmVec.end(), [](int x) {
return x % 2 == 0;
}), rmVec.end()); // rmVec: [1,3,5]2.5 unique
範囲内の連続する重複要素を削除し、新しい論理的終端イテレータを返します。通常、eraseと共に使用されます。
std::vector<int> uniqVec = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = std::unique(uniqVec.begin(), uniqVec.end());
uniqVec.erase(last, uniqVec.end()); // uniqVecは{1, 2, 3, 4, 5}になる2.6 reverse
範囲内の要素の順序を逆転させます。
std::vector<int> revVec = {1, 2, 3, 4, 5};
std::reverse(revVec.begin(), revVec.end()); // revVecは{5, 4, 3, 2, 1}になる2.7 rotate
範囲内の要素を回転させ、指定した要素を新たな先頭にします。
std::vector<int> rotVec = {1, 2, 3, 4, 5};
std::rotate(rotVec.begin(), rotVec.begin() + 2, rotVec.end()); // 3を起点に回転させるとrotVecは{3, 4, 5, 1, 2}になる2.8 shuffle
範囲内の要素をランダムな順序に並べ替えます（C++11以降が必要です）。
#include <random>
#include <algorithm>
std::vector<int> shufVec = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(shufVec.begin(), shufVec.end(), gen); // shufVecの要素がランダムに並び変わる3. ソートと関連アルゴリズム
3.1 sort, stable_sort, partial_sort
sort(first, last): 要素をクイックソート（実際にはintrosort）で並べ替えます（安定性なし、平均的な時間複雑度はO(n log n)）。stable_sort(first, last): 要素を安定ソート（等しい要素の相対的な順序を保ちます）で並べ替えます。partial_sort(first, middle, last):[first, middle)の範囲を全体の中で最小の要素として並べ替えます。
std::vector<int> sortVec = {5, 3, 1, 4, 2};
std::sort(sortVec.begin(), sortVec.end()); // 既定の昇順、sortVecは{1, 2, 3, 4, 5}になる
std::sort(sortVec.begin(), sortVec.end(), std::greater<int>()); // 降順、sortVecは{5, 4, 3, 2, 1}になる
std::sort(sortVec.begin(), sortVec.end(), [](int a, int b) {
return a < b;
}); // 昇順、比較関数を自定義
std::vector<std::pair<int, int>> pairVec = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pairVec.begin(), pairVec.end(), [](const auto& a, const auto& b) {
return a.first < b.first; // firstを基準にソートし、等しい要素の相対的な順序を保持
});
std::vector<int> partSortVec = {5, 3, 1, 4, 2, 6};
// 最小の3つの要素を前に取り出し並べ替える
std::partial_sort(partSortVec.begin(), partSortVec.begin() + 3, partSortVec.end());
// 現在partSortVecの最初の3つの要素は1, 2, 3で、残りは未ソートの4, 5, 63.2 nth_element
範囲を再配置し、指定された位置の要素がソート後の要素と等しくなり、その左側の要素はそれよりも小さく、右側の要素はそれよりも大きくなるようにします。
std::vector<int> nthVec = {5, 3, 1, 4, 2, 6};
// 第3番目に小さい要素（インデックス2）を見つける
std::nth_element(nthVec.begin(), nthVec.begin() + 2, nthVec.end());
// 現在nthVec[2]は3で、それより左の要素は3以下で、それより右の要素は3以上3.3 binary_search, lower_bound, upper_bound
これらのアルゴリズムは、既にソートされているコンテナ上で動作します。
binary_search(first, last, value):valueが存在するかどうかを判定します（戻り値はbool）。lower_bound(first, last, value): 最初のvalue以上の要素へのイテレータを返します。upper_bound(first, last, value): 最初のvalueより大きい要素へのイテレータを返します。
std::vector<int> sortedVec = {1, 3, 3, 5, 7}; // 事前にソートしておく必要がある
// 3が存在するかどうかを確認
bool found = std::binary_search(sortedVec.begin(), sortedVec.end(), 3); // true
// 最初の3以上の要素を見つける
auto lowerBoundItr = std::lower_bound(sortedVec.begin(), sortedVec.end(), 3);
std::cout << "lower_boundのインデックス: " << std::distance(sortedVec.begin(), lowerBoundItr) << std::endl; // 出力: 1
// 最初の3より大きい要素を見つける
auto upperBoundItr = std::upper_bound(sortedVec.begin(), sortedVec.end(), 3);
std::cout << "upper_boundのインデックス: " << std::distance(sortedVec.begin(), upperBoundItr) << std::endl; // 出力: 33.4 merge
2つの既にソートされている範囲を新しいコンテナにマージします（ソートを維持）。
std::vector<int> mergeVecA = {1, 3, 5};
std::vector<int> mergeVecB = {2, 4, 6};
std::vector<int> mergedVec(mergeVecA.size() + mergeVecB.size());
// mergeVecAとmergeVecBをマージする（両方ともソートされている必要がある）
std::merge(mergeVecA.begin(), mergeVecA.end(), mergeVecB.begin(), mergeVecB.end(), mergedVec.begin()); // mergedVec: [1,2,3,4,5,6]4. ヒープアルゴリズム
STLは範囲をヒープとして操作するためのアルゴリズムを提供しています。これにはmake_heap, push_heap, pop_heap, sort_heapなどが含まれます。
std::vector<int> heapVec = {4, 1, 3, 2, 5};
std::make_heap(heapVec.begin(), heapVec.end()); // 最大ヒープを作る、heapVecは{5, 4, 3, 2, 1}になる
heapVec.push_back(6);
std::push_heap(heapVec.begin(), heapVec.end()); // 新しい要素をヒープに追加する、heapVecは{6, 4, 5, 2, 1, 3}になる
std::pop_heap(heapVec.begin(), heapVec.end()); // 最大要素を末尾に移動させる、heapVecは{5, 4, 3, 2, 1, 6}になる
int maxValue = heapVec.back(); // 最大値6を取得
heapVec.pop_back(); // 最大値を削除
std::sort_heap(heapVec.begin(), heapVec.end()); // ヒープを昇順のシーケンスにソートする、heapVecは{1, 2, 3, 4, 5}になる5. 最小値/最大値アルゴリズム
5.1 minとmax
2つの値や初期化リストの中から最小値や最大値を返します。
int x = 5, y = 3;
int minValue = std::min(x, y); // 3
int maxValue = std::max(x, y); // 5
auto minListValue = std::min({4, 2, 8, 5, 1}); // 1
auto maxListValue = std::max({4, 2, 8, 5, 1}); // 85.2 min_elementとmax_element
範囲内の最小値や最大値へのイテレータを返します。
std::vector<int> elemVec = {3, 1, 4, 2, 5};
auto minElementItr = std::min_element(elemVec.begin(), elemVec.end()); // 1を指すイテレータ
auto maxElementItr = std::max_element(elemVec.begin(), elemVec.end()); // 5を指すイテレータ5.3 minmax_element (C++11)
範囲内の最小値と最大値へのイテレータを同時に返します。
std::vector<int> minmaxVec = {3, 1, 4, 2, 5};
auto minmaxPair = std::minmax_element(minmaxVec.begin(), minmaxVec.end());
// minmaxPair.firstは1を、minmaxPair.secondは5を指すイテレータ6. 数値アルゴリズム (<numeric>ヘッダ)
6.1 accumulate
範囲内の要素の累積和（またはカスタマイズされた操作）を計算します。
#include <numeric>
std::vector<int> accVec = {1, 2, 3, 4, 5};
int sumAcc = std::accumulate(accVec.begin(), accVec.end(), 0); // 和、初期値は0、結果は15
int productAcc = std::accumulate(accVec.begin(), accVec.end(), 1, std::multiplies<int>()); // 積、初期値は1、結果は1206.2 inner_product
2つの範囲の内積（またはカスタマイズされた操作）を計算します。
std::vector<int> ipVecA = {1, 2, 3};
std::vector<int> ipVecB = {4, 5, 6};
int dotProduct = std::inner_product(ipVecA.begin(), ipVecA.end(), ipVecB.begin(), 0); // 1*4 + 2*5 + 3*6 = 326.3 iota
範囲を連続する増加値で埋めます。
std::vector<int> iotaVec(5);
std::iota(iotaVec.begin(), iotaVec.end(), 10); // 10, 11, 12, 13, 14で埋める6.4 partial_sum
部分和を計算し、結果を目的の範囲に格納します。
std::vector<int> psSrc = {1, 2, 3, 4, 5};
std::vector<int> psDst(psSrc.size());
std::partial_sum(psSrc.begin(), psSrc.end(), psDst.begin()); // psDstは{1, 3, 6, 10, 15}になる6.5 adjacent_difference
隣接する要素の差を計算し、結果を目的の範囲に格納します。
std::vector<int> adSrc = {1, 2, 3, 4, 5};
std::vector<int> adDst(adSrc.size());
std::adjacent_difference(adSrc.begin(), adSrc.end(), adDst.begin()); // adDstは{1, 1, 1, 1, 1}になる7. その他のアルゴリズム
7.1 generate
生成関数を使って範囲を埋めます。
std::vector<int> genVec(5);
int counter = 0;
std::generate(genVec.begin(), genVec.end(), [&counter]() {
return counter++;
}); // 0, 1, 2, 3, 4で埋める7.2 generate_n
生成関数を使って範囲の最初のn個の要素を埋めます。
std::vector<int> genNVec(5);
int startNum = 10;
std::generate_n(genNVec.begin(), 3, [&startNum]() {
return startNum++;
}); // 最初の3つの要素が10, 11, 12になり、残りは未変更7.3 includes
1つのソートされた範囲が別のソートされた範囲のすべての要素を含んでいるかどうかをチェックします。
std::vector<int> incVec1 = {1, 2, 3, 4, 5};
std::vector<int> incVec2 = {2, 4};
bool isIncluded = std::includes(incVec1.begin(), incVec1.end(), incVec2.begin(), incVec2.end()); // true7.4 set_union, set_intersection, set_difference, set_symmetric_difference
集合操作（和集合、積集合、差集合、対称差集合）を実行します。
std::vector<int> setVec1 = {1, 2, 3, 4, 5};
std::vector<int> setVec2 = {3, 4, 5, 6, 7};
std::vector<int> setResult;
// 和集合
std::set_union(setVec1.begin(), setVec1.end(), setVec2.begin(), setVec2.end(), std::back_inserter(setResult));
// setResultは{1, 2, 3, 4, 5, 6, 7}になる
// 積集合
setResult.clear();
std::set_intersection(setVec1.begin(), setVec1.end(), setVec2.begin(), setVec2.end(), std::back_inserter(setResult));
// setResultは{3, 4, 5}になる
// 差集合 (setVec1 - setVec2)
setResult.clear();
std::set_difference(setVec1.begin(), setVec1.end(), setVec2.begin(), setVec2.end(), std::back_inserter(setResult));
// setResultは{1, 2}になる
// 対称差集合 (setVec1 ∪ setVec2 - setVec1 ∩ setVec2)
setResult.clear();
std::set_symmetric_difference(setVec1.begin(), setVec1.end(), setVec2.begin(), setVec2.end(), std::back_inserter(setResult));
// setResultは{1, 2, 6, 7}になる