ソートされた範囲を扱う STLアルゴリズム

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 -> C++23 と更新されています。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。当サイトでは、C++14 をベースにした新C++編を作成中です。

この章の概要

この章の概要です。

ソートされた範囲を扱う STLアルゴリズム
binary_search
lower_bound
upper_bound
equal_range
includes
merge
set_union
set_intersection
set_difference
set_symmetric_difference
練習問題
参考リンク
更新履歴

この章では、STLアルゴリズムの中から、ソートされた範囲に対して処理を行うものを取り上げます。

これらのアルゴリズムを、ソートされていない範囲に対して適用した場合の結果は未定義です。

binary_search

binary_search関数は、指定の範囲内から、特定の値を持った要素があるかどうかを調べます。

namespace std {
    template <typename ForwardIterator, typename T>
    bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);

    template <typename ForwardIterator, typename T, typename Compare>
    bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

第１、２引数に、対象の範囲を指定し、第３引数に、探したい値を指定します。第４引数には、要素の大小関係を定義する関数や関数オブジェクトを指定できます。

該当する要素が見つかった場合は true を、見つからなかった場合は false を返します。

binary_search関数は、名前のとおり、二分探索（アルゴリズムとデータ構造編【探索】第４章）によって実装されています。

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

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::cout << std::boolalpha
              << std::binary_search(v.begin(), v.end(), 3)
              << std::endl;
}

実行結果

true

lower_bound

lower_bound関数は、指定の範囲内で、指定の値以上の要素が現れる最初の位置を返します。

namespace std {
    template <typename ForwardIterator, typename T>
    ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

    template <typename ForwardIterator, typename T, typename Compare>
    ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

第１、２引数の範囲から、第３引数の値以上の要素が現れる最初の位置を返します。この関数は、ソートされた状態を崩すことなく、第３引数の値を挿入できる位置はどこかを取得できるということです。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(3);
    v.push_back(4);
    v.push_back(6);
    v.push_back(9);

    const int value = 5;
    v.insert(std::lower_bound(v.begin(), v.end(), value), value);

    std::for_each(v.begin(), v.end(), Println);
}

実行結果

upper_bound

upper_bound関数は、指定の範囲内で、指定の値より大きい要素が現れる最初の位置を返します。

namespace std {
    template <typename ForwardIterator, typename T>
    ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

    template <typename ForwardIterator, typename T, typename Compare>
    ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(3);
    v.push_back(4);
    v.push_back(6);
    v.push_back(9);

    const int value = 5;
    v.insert(std::upper_bound(v.begin(), v.end(), value), value);

    std::for_each(v.begin(), v.end(), Println);
}

実行結果

equal_range

equal_range関数は、指定の範囲内で、指定の値以上の要素が現れる最初の位置と、指定の値より大きい要素が現れる最初の位置を返します。

namespace std {
    template <typename ForwardIterator, typename T>
    pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);

    template <typename ForwardIterator, typename T, typename Compare>
    pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
}

この関数は、lower_bound関数と upper_bound関数の組み合わせです。

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

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(3);
    v.push_back(5);
    v.push_back(5);
    v.push_back(7);

    const int value = 5;

    typedef std::pair<std::vector<int>::iterator, std::vector<int>::iterator> IteratorPair;
    IteratorPair itPair = std::equal_range(v.begin(), v.end(), value);

    std::cout << std::distance(v.begin(), itPair.first)
              << ", "
              << std::distance(v.begin(), itPair.second)
              << std::endl
              ;
}

実行結果

2, 4

includes

includes関数は、指定の範囲内に、別の指定範囲内の要素がすべて含まれているかどうかを調べます。

namespace std {
    template <typename InputIterator1, typename InputIterator2>
    bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

    template <typename InputIterator1, typename InputIterator2, typename Compare>
    bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);
}

第１、２引数で指定した範囲内に、第３、４引数で指定した範囲内の要素がすべて含まれていれば true を返します。そうでなければ false が返されます。第５引数は、要素の比較に用いる関数や関数オブジェクトです。

範囲は２つともソート済みでなければなりません。

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

int main()
{
    std::vector<int> v;
    v.push_back(0);
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);

    std::list<int> lst(v.begin(), v.end());

    std::cout << std::boolalpha
              << std::includes(v.begin(), v.end(), lst.begin(), lst.end())
              << ", "
              << std::includes(lst.begin(), lst.end(), v.begin(), v.end())
              << std::endl;

    lst.push_back(5);
    std::cout << std::boolalpha
              << std::includes(v.begin(), v.end(), lst.begin(), lst.end())
              << ", "
              << std::includes(lst.begin(), lst.end(), v.begin(), v.end())
              << std::endl;
}

実行結果

true, true
false, true

merge

merge関数は、指定した２つのソート済み範囲の要素を併合（マージ）して、ソートされた新たな範囲を生成します。

namespace std {
    template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
    OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

    template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
    OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第１、第２引数で１つのソート済み範囲を、第３、４引数でもう１つのソート済み範囲を指定します。第５引数で指定した位置へ、併合してソートした結果を出力します。第６引数は、要素の比較に用いる関数や関数オブジェクトです。

戻り値は、最後に出力された要素の位置を返します。

なお、対象が std::list の場合には、メンバ関数の merge（第６章）があるので、そちらを使う方が効率的です。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v1, v2;
    v1.push_back(0);
    v1.push_back(3);
    v1.push_back(4);
    v2.push_back(1);
    v2.push_back(2);

    std::vector<int> result(v1.size() + v2.size());

    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    std::for_each(result.begin(), result.end(), Println);
}

実行結果

set_union

set_union関数は、指定した２つのソートされた範囲のどちらか一方（あるいは両方）に含まれている要素からなる新たな集合を生成します。いわゆる「和集合」を作る関数です。

namespace std {
    template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
    OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

    template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
    OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第１、第２引数で１つのソート済み範囲を、第３、４引数でもう１つのソート済み範囲を指定します。第５引数で指定した位置へ、和集合を出力します。第６引数は、要素の比較に用いる関数や関数オブジェクトです。

戻り値は、最後に出力された要素の位置を返します。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v1, v2;
    v1.push_back(0);
    v1.push_back(1);
    v1.push_back(3);
    v2.push_back(1);
    v2.push_back(2);

    std::vector<int> result(v1.size() + v2.size());
    std::vector<int>::iterator it = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

    std::for_each(result.begin(), it, Println);
}

実行結果

set_intersection

set_intersection関数は、指定した２つのソートされた範囲の両方に含まれている要素からなる新たな集合を生成します。いわゆる「積集合」を作る関数です。

namespace std {
    template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
    OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

    template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
    OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第１、第２引数で１つのソート済み範囲を、第３、４引数でもう１つのソート済み範囲を指定します。第５引数で指定した位置へ、積集合を出力します。第６引数は、要素の比較に用いる関数や関数オブジェクトです。

戻り値は、最後に出力された要素の位置を返します。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v1, v2;
    v1.push_back(0);
    v1.push_back(1);
    v1.push_back(3);
    v2.push_back(1);
    v2.push_back(2);

    std::vector<int> result(v1.size() + v2.size());
    std::vector<int>::iterator it = std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

    std::for_each(result.begin(), it, Println);
}

実行結果

set_difference

set_difference関数は、指定した１つ目のソートされた範囲に含まれているが、２つ目のソートされた範囲には含まれていない要素からなる新たな集合を生成します。いわゆる「差集合」を作る関数です。

namespace std {
    template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
    OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

    template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
    OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第１、第２引数で１つのソート済み範囲を、第３、４引数でもう１つのソート済み範囲を指定します。第５引数で指定した位置へ、１つ目の範囲にだけ含まれている要素からなる差集合を出力します。第６引数は、要素の比較に用いる関数や関数オブジェクトです。

戻り値は、最後に出力された要素の位置を返します。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v1, v2;
    v1.push_back(0);
    v1.push_back(1);
    v1.push_back(3);
    v2.push_back(1);
    v2.push_back(2);

    std::vector<int> result(v1.size() + v2.size());
    std::vector<int>::iterator it = std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

    std::for_each(result.begin(), it, Println);
}

実行結果

0
3

set_symmetric_difference

set_symmetric_difference関数は、指定した２つのソートされた範囲の一方にだけ含まれている要素からなる新たな集合を生成します。いわゆる「互いに素な集合」を作る関数です。

namespace std {
    template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
    OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

    template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
    OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
}

第１、第２引数で１つのソート済み範囲を、第３、４引数でもう１つのソート済み範囲を指定します。第５引数で指定した位置へ、一方の範囲にだけ含まれている要素からなる集合を出力します。第６引数は、要素の比較に用いる関数や関数オブジェクトです。

戻り値は、最後に出力された要素の位置を返します。

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

namespace {
    void Println(int elem)
    {
        std::cout << elem << std::endl;
    }
}

int main()
{
    std::vector<int> v1, v2;
    v1.push_back(0);
    v1.push_back(1);
    v1.push_back(3);
    v2.push_back(1);
    v2.push_back(2);

    std::vector<int> result(v1.size() + v2.size());
    std::vector<int>::iterator it = std::set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

    std::for_each(result.begin(), it, Println);
}

実行結果

0
2
3

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

この章の概要