C++におけるアルゴリズムの効率的な活用と実装例

1. 要素を変更しないシーケンス操作

これらの関数は元データを改変せず、検索・集計・条件評価などの処理を行います。

1.1 検索系：find, find_if, find_end
std::vector<int> data = {10, 20, 30, 40, 50};

// 値30を検索
auto pos = std::find(data.cbegin(), data.cend(), 30);
if (pos != data.cend()) {
    std::cout << "見つかった値: " << *pos << "\n"; // 出力: 30
}

// 条件付き検索（35より大きい最初の要素）
auto cond_pos = std::find_if(data.cbegin(), data.cend(),
    [](int v) { return v > 35; });
std::cout << "条件該当: " << *cond_pos << "\n"; // 出力: 40

// サブシーケンスの最終出現位置
std::vector<int> pattern = {20, 30};
auto sub_pos = std::find_end(data.cbegin(), data.cend(),
    pattern.cbegin(), pattern.cend());
if (sub_pos != data.cend()) {
    std::cout << "パターン開始位置: " << (sub_pos - data.cbegin()) << "\n"; // 出力: 1
}
1.2 集計系：count, count_if
std::vector<int> values = {2, 4, 6, 4, 8, 4};
int fours = std::count(values.cbegin(), values.cend(), 4); // 4の出現回数 → 3
int odds = std::count_if(values.cbegin(), values.cend(),
    [](int n) { return n % 2 == 1; }); // 奇数の個数 → 0
1.3 各要素への関数適用：for_each
std::vector<int> items = {1, 3, 5, 7};
std::for_each(items.begin(), items.end(),
    [](int& elem) { elem += 10; }); // 各要素に10を加算
// 結果: {11, 13, 15, 17}
1.4 比較系：equal, mismatch
std::vector<int> seqA = {1, 2, 3};
std::vector<int> seqB = {1, 2, 5};

bool same = std::equal(seqA.cbegin(), seqA.cend(), seqB.cbegin());
std::cout << "一致？ " << std::boolalpha << same << "\n"; // false

auto diff = std::mismatch(seqA.cbegin(), seqA.cend(), seqB.cbegin());
if (diff.first != seqA.cend()) {
    std::cout << "差異: " << *diff.first << " vs " << *diff.second << "\n"; // 3 vs 5
}
1.5 条件チェック：all_of, any_of, none_of
std::vector<int> numbers = {2, 4, 6, 8};
bool all_even = std::all_of(numbers.cbegin(), numbers.cend(),
    [](int x) { return x % 2 == 0; }); // true
bool has_odd = std::any_of(numbers.cbegin(), numbers.cend(),
    [](int x) { return x % 2 == 1; }); // false
bool no_negative = std::none_of(numbers.cbegin(), numbers.cend(),
    [](int x) { return x < 0; });      // true

2. 要素を変更するシーケンス操作

2.1 コピー系：copy, copy_if
std::vector<int> source = {5, 10, 15, 20};
std::vector<int> target(source.size());
std::copy(source.cbegin(), source.cend(), target.begin()); // 完全コピー

std::vector<int> filtered;
std::copy_if(source.cbegin(), source.cend(), std::back_inserter(filtered),
    [](int val) { return val >= 10; }); // 10以上のみ抽出 → {10,15,20}
2.2 変換：transform
std::vector<int> base = {1, 2, 3};
std::vector<int> squared(base.size());
std::transform(base.cbegin(), base.cend(), squared.begin(),
    [](int x) { return x * x; }); // 平方 → {1,4,9}

std::vector<int> left = {1, 2, 3}, right = {10, 20, 30};
std::vector<int> combined(left.size());
std::transform(left.cbegin(), left.cend(), right.cbegin(), combined.begin(),
    std::plus<int>{}); // 足し算 → {11,22,33}
2.3 置換：replace, replace_if, replace_copy
std::vector<int> dataset = {1, 2, 1, 3, 1};
std::replace(dataset.begin(), dataset.end(), 1, 99); // 1→99 → {99,2,99,3,99}

std::replace_if(dataset.begin(), dataset.end(),
    [](int x) { return x > 50; }, 0); // 50超→0 → {0,2,0,3,0}

std::vector<int> preserved;
std::replace_copy(dataset.cbegin(), dataset.cend(), std::back_inserter(preserved),
    3, 333); // 3→333（元は不変）→ preserved: {0,2,0,333,0}
2.4 削除系：remove + eraseイディオム
std::vector<int> collection = {1, 2, 3, 2, 4};
auto boundary = std::remove(collection.begin(), collection.end(), 2);
collection.erase(boundary, collection.end()); // 実削除 → {1,3,4}

// 条件削除（偶数を除去）
collection = {1, 2, 3, 4, 5};
collection.erase(
    std::remove_if(collection.begin(), collection.end(),
        [](int x) { return x % 2 == 0; }),
    collection.end()
); // → {1,3,5}
2.5 重複除去：unique
std::vector<int> duplicates = {1, 1, 2, 2, 2, 3, 4, 4};
auto unique_end = std::unique(duplicates.begin(), duplicates.end());
duplicates.erase(unique_end, duplicates.end()); // → {1,2,3,4}
2.6 反転：reverse
std::vector<int> order = {1, 2, 3, 4, 5};
std::reverse(order.begin(), order.end()); // → {5,4,3,2,1}
2.7 回転：rotate
std::vector<int> sequence = {1, 2, 3, 4, 5};
std::rotate(sequence.begin(), sequence.begin() + 2, sequence.end());
// 先頭を3番目の要素に → {3,4,5,1,2}
2.8 シャッフル：shuffle
#include <random>
std::vector<int> deck = {1, 2, 3, 4, 5};
std::shuffle(deck.begin(), deck.end(), std::mt19937{std::random_device{}()});
// ランダムに再配置

3. ソートと関連操作

3.1 ソート：sort, stable_sort, partial_sort
std::vector<int> unsorted = {5, 2, 8, 1, 9};
std::sort(unsorted.begin(), unsorted.end()); // 昇順 → {1,2,5,8,9}
std::sort(unsorted.begin(), unsorted.end(), std::greater<>{}); // 降順

// 安定ソート（キーが同じ場合の順序保持）
std::vector<std::pair<char, int>> pairs = {{'a',2}, {'b',1}, {'a',1}};
std::stable_sort(pairs.begin(), pairs.end(),
    [](const auto& lhs, const auto& rhs) { return lhs.first < rhs.first; });

// 部分ソート（先頭3要素だけ最小値でソート）
std::vector<int> partial = {9, 3, 7, 1, 5, 2};
std::partial_sort(partial.begin(), partial.begin() + 3, partial.end());
// → {1,2,3, 7,5,9} （後半は未ソート）
3.2 nth_element
std::vector<int> elements = {5, 3, 1, 4, 2};
std::nth_element(elements.begin(), elements.begin() + 2, elements.end());
// インデックス2の位置に3番目に小さい値が来る（前後は大小保証あり）
3.3 二分探索：binary_search, lower_bound, upper_bound
std::vector<int> sorted_data = {1, 3, 3, 5, 7}; // ソート済み必須

bool found = std::binary_search(sorted_data.cbegin(), sorted_data.cend(), 3); // true

auto lb = std::lower_bound(sorted_data.cbegin(), sorted_data.cend(), 3);
std::cout << "下限位置: " << std::distance(sorted_data.cbegin(), lb) << "\n"; // 1

auto ub = std::upper_bound(sorted_data.cbegin(), sorted_data.cend(), 3);
std::cout << "上限位置: " << std::distance(sorted_data.cbegin(), ub) << "\n"; // 3
3.4 マージ：merge
std::vector<int> listA = {1, 3, 5}, listB = {2, 4, 6};
std::vector<int> merged(listA.size() + listB.size());
std::merge(listA.cbegin(), listA.cend(), listB.cbegin(), listB.cend(), merged.begin());
// → {1,2,3,4,5,6}

4. ヒープ操作

std::vector<int> heap_data = {3, 1, 4, 1, 5};
std::make_heap(heap_data.begin(), heap_data.end()); // 最大ヒープ構築

heap_data.push_back(9);
std::push_heap(heap_data.begin(), heap_data.end()); // ヒープ再構成

std::pop_heap(heap_data.begin(), heap_data.end()); // 最大値を末尾へ移動
int max_elem = heap_data.back(); // 最大値取得
heap_data.pop_back();            // 実削除

std::sort_heap(heap_data.begin(), heap_data.end()); // ヒープ→昇順配列

5. 最小/最大値操作

5.1 min, max
int smaller = std::min(7, 3); // 3
int larger = std::max(7, 3);  // 7
int smallest = std::min({5, 2, 8, 1}); // 1
5.2 min_element, max_element
std::vector<int> dataset = {8, 3, 6, 1, 9};
auto min_iter = std::min_element(dataset.cbegin(), dataset.cend()); // イテレータ
auto max_iter = std::max_element(dataset.cbegin(), dataset.cend());
std::cout << "最小: " << *min_iter << ", 最大: " << *max_iter << "\n"; // 1, 9
5.3 minmax_element (C++11以降)
auto extremes = std::minmax_element(dataset.cbegin(), dataset.cend());
std::cout << "範囲: [" << *extremes.first << ", " << *extremes.second << "]\n";

6. 数値計算アルゴリズム (<numeric>)

6.1 accumulate
#include <numeric>
std::vector<int> nums = {1, 2, 3, 4, 5};
int total = std::accumulate(nums.cbegin(), nums.cend(), 0); // 15
int product = std::accumulate(nums.cbegin(), nums.cend(), 1,
    std::multiplies<int>{}); // 120
6.2 inner_product
std::vector<int> vecX = {1, 2, 3}, vecY = {4, 5, 6};
int dot = std::inner_product(vecX.cbegin(), vecX.cend(), vecY.cbegin(), 0);
// 1*4 + 2*5 + 3*6 = 32
6.3 iota
std::vector<int> series(5);
std::iota(series.begin(), series.end(), 100); // 100,101,102,103,104
6.4 partial_sum
std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> sums(input.size());
std::partial_sum(input.cbegin(), input.cend(), sums.begin());
// → {1,3,6,10,15}
6.5 adjacent_difference
std::vector<int> source = {1, 3, 6, 10, 15};
std::vector<int> diffs(source.size());
std::adjacent_difference(source.cbegin(), source.cend(), diffs.begin());
// → {1,2,3,4,5}

7. その他の有用なアルゴリズム

7.1 generate / generate_n
std::vector<int> buffer(5);
int counter = 0;
std::generate(buffer.begin(), buffer.end(), [&counter]() { return counter++; });
// → {0,1,2,3,4}

std::vector<int> init_vec(5, -1);
std::generate_n(init_vec.begin(), 3, [&counter]() { return counter++; });
// → {5,6,7, -1, -1}
7.2 includes
std::vector<int> superset = {1, 2, 3, 4, 5};
std::vector<int> subset = {2, 4};
bool contained = std::includes(superset.cbegin(), superset.cend(),
    subset.cbegin(), subset.cend()); // true
7.3 集合演算
std::vector<int> setA = {1, 2, 3, 4}, setB = {3, 4, 5, 6};
std::vector<int> result;

// 和集合
std::set_union(setA.cbegin(), setA.cend(), setB.cbegin(), setB.cend(),
    std::back_inserter(result));

// 積集合
result.clear();
std::set_intersection(setA.cbegin(), setA.cend(), setB.cbegin(), setB.cend(),
    std::back_inserter(result));

// 差集合 (A - B)
result.clear();
std::set_difference(setA.cbegin(), setA.cend(), setB.cbegin(), setB.cend(),
    std::back_inserter(result));

// 対称差 (A△B)
result.clear();
std::set_symmetric_difference(setA.cbegin(), setA.cend(), setB.cbegin(), setB.cend(),
    std::back_inserter(result));

タグ: STL C++11 アルゴリズム コンテナ操作 標準ライブラリ

6月15日 23:02 投稿

ホットタグ

©2026 異端開発室