C++のSTLで使えるアルゴリズムについてわかりやすく詳しく解説

2023年6月15日2023年6月19日

C++のSTLには、様々なアルゴリズムが用意されています。

これらのアルゴリズムを使うことで、プログラミングの効率性や可読性を向上させることができます。

本記事では、STLで使える代表的なアルゴリズムについて、わかりやすく詳しく解説していきます。

目次から探す

STLのアルゴリズムの種類

STL(Standard Template Library)は、C++の標準ライブラリの一部であり、多くの便利なアルゴリズムを提供しています。ここでは、STLで使用可能な主要なアルゴリズムについていくつか紹介します。

非変更アルゴリズム

STLのアルゴリズムには、データを変更しないものと、変更するものがあります。まずは、データを変更しない非変更アルゴリズムについて解説します。

find

find関数は、指定された値が最初に現れる位置を探し、そのイテレータを返します。例えば、以下のようなコードで使用することができます。

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "Found at position " << it - v.begin() << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
}

この場合、vの中から3を探し、その位置を表示しています。もし見つからなかった場合は"Not found"と表示されます。

count

count関数は、指定された値が出現する回数をカウントします。例えば、以下のようなコードで使用することができます。

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

int main() {
    std::vector<int> v = {1, 2, 3, 2, 2};
    int count = std::count(v.begin(), v.end(), 2);
    std::cout << "Count: " << count << std::endl;
}

この場合、vの中から2が何回出現するかカウントしています。結果は"Count: 3"と表示されます。

accumulate

accumulate関数は、指定された範囲内の要素を合計した結果を返します。例えば、以下のようなコードで使用することができます。

#include <iostream>
// <algorithm> ではなく <numeric>なので注意
#include <numeric>
#include <vector>

int main() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << std::endl;
}

Sum: 15

この場合、vの全ての要素を加算した結果が表示されます。結果は"Sum:15"と表示されます。

変更アルゴリズム

STLの変更アルゴリズムは、コンテナ内の要素を変更するために使用されます。以下では、copy、fill、transformについて説明します。

copy

copyアルゴリズムは、1つのコンテナから別のコンテナに要素をコピーするために使用されます。例えば、vectorから配列への要素のコピーなどが挙げられます。

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

int main() {
    std::vector<int> v1 = {1, 2, 3, 4, 5};
    int arr[5];

    std::copy(v1.begin(), v1.end(), arr);

    for (int i = 0; i < 5; i++) {
        std::cout << arr[i] << " ";
    }

    return 0;
}

1 2 3 4 5

上記の例では、vector v1から配列arrに要素をコピーしています。copy関数は第一引数にコピー元の開始位置、第二引数に終了位置、第三引数にコピー先の開始位置を指定します。

fill

fillアルゴリズムは、指定した値で範囲内の全ての要素を埋めるために使用されます。例えば、vectorや配列などで初期化する場合などで使用することが多いです。

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

int main() {
    std::vector<int> v1(5);

    std::fill(v1.begin(), v1.end(), 10);

    for (auto x : v1) {
        std::cout << x << " ";
    }

    return 0;
}

10 10 10 10 10

上記の例では、vector v1内の全ての要素を10で埋めています。fill関数は第一引数と第二引数で範囲を指定し、第三引数で埋める値を指定します。

transform

transformアルゴリズムは、与えられた2つ以上のシーケンスから新しいシーケンスを生成するために使用されます。

また同時に各要素も変換することが可能です。

例えば2つ以上のベクトルを演算した結果を新しいベクトルとして取得する場合などが挙げられます。

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

int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {4, 5, 6};
    std::vector<int> result(3);

    auto combine_f = [](int a, int b) -> int { return a + b; };
    
    std::transform(
        v1.begin(), 
        v1.end(),
        v2.begin(),
        result.begin(),
        combine_f
        );

    for (auto x : result) {
        std::cout << x << " ";
    }

    return 0;
}

5 7 9

上記の例では、v1とv2ベクトル間で加算した結果をresultベクトルとして取得しています。

transform関数は第一引数と第二引数で範囲を指定し、第三引数以降で操作内容(ラムダ式)を指定します。

この場合、combine_fの[](int a, int b) -> int { return a + b; }がラムダ式で、2つのvectorの各要素を加算する処理を返す処理を定義しています。

ソートアルゴリズム

ソートアルゴリズムについて解説します。

sort

sortは、指定された範囲の要素を昇順に並べ替えます。以下が使用例です。

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    for (auto x : v) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::sort(v.begin(), v.end());
    
    for (auto x : v) {
        std::cout << x << " ";
    }   
}

3 1 4 1 5 9 2 6 
1 1 2 3 4 5 6 9

このように、コンテナの中身がソートされて、 {1, 1, 2, 3, 4, 5, 6, 9}となります。

stable_sort

stable_sortは、指定された範囲の要素を安定的に昇順に並べ替えます。

安定的というのは、同じ値を持つ要素があった場合、元の順序が保たれることを意味します。以下が使用例です。

#include <algorithm>
#include <vector>

struct Person {
    int age;
    std::string name;
};

bool operator<(const Person& lhs, const Person& rhs) {
    return lhs.age < rhs.age;
}

int main() {
    std::vector<Person> people = {{25, "Alice"}, {20, "Bob"}, {25, "Charlie"}};
    std::stable_sort(people.begin(), people.end());
}

年齢順
Bob(20)
Alice(25)
Charlie(25)

この場合、peopleの中身は {{20,"Bob"},{25,"Alice"},{25,"Charlie"}}となります。年齢が同じ人が複数いる場合でも、元の順序が保たれています(Charlie, Aliceの順番にならない。

partial_sort

partial_sortは、指定された範囲内で最初からN番目までの要素を昇順に並べ替えます。残りの要素はどこにあっても構いません。以下が使用例です。

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

int main() {
    std::vector<int> v = {2, 4, 6, 1, 5, 3, 7};
    std::partial_sort(v.begin(), v.begin() + 3 , v.end());
    
    for (auto i : v) {
        std::cout << i << ' ';
    }
}

1 2 3 6 5 4 7

この場合、最初から3番目までの要素 {1、1、3}だけが昇順に並べられます。出力結果： 1　1　3　4　5

その他のアルゴリズム

unique

uniqueは、連続する重複した要素を削除するアルゴリズムです。このアルゴリズムは、削除された要素の数を返します。以下に例を示します。

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

int main() {
    std::vector<int> v = {1, 2, 2, 3, 3, 3};
    auto last = std::unique(v.begin(), v.end());
    for (auto it = v.begin(); it != last; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
    return 0;
}

1 2 3

reverse

reverseは、範囲内の要素を逆順に並べ替えるアルゴリズムです。以下に例を示します。

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

int main() {
    std::vector<int> v = {1, 2, 3};

    for (auto x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    std::reverse(v.begin(), v.end());

    for (auto x : v) {
        std::cout << x << " ";
    }
    return 0;
}

1 2 3 
3 2 1

rotate

rotateは、範囲内の要素を指定した位置で回転させるアルゴリズムです。以下に例を示します。

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    std::rotate(v.begin(), v.begin() + 2, v.end());
    for (auto x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";
    return 0;
}

3 4 5 6 1 2

これらのようなアルゴリズムは初めからSTLに使いやすい関数が定義されているため、位置から自作する必要がありません。

自作するとしたらソートアルゴリズムで使用する、並び替え条件を指定するためのラムダ式です。

ラムダ式を書けば他のアルゴリズムを実装する必要はほとんどありません。