readonly な STLアルゴリズム | Programming Place Plus C++編【標準ライブラリ】 第19章

トップページC++編

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

この章の概要

この章の概要です。


readonly な STLアルゴリズム

この章では、STLアルゴリズムの中から、対象の要素の値や、並び順を変更しないものを取り上げます。このような分類にそれほど大きな意味はありませんが、数が膨大なので、この章以降も同様に、ある程度のグループ分けを行って説明していきます。

count

count関数は、指定した範囲内に、指定の値と一致する要素が何個あるかを調べます。通常の一致 (==演算子による比較)ではなく、もっと複雑な条件一致が必要であれば、count_if関数を検討してください。

namespace std {
    template <typename InputIterator, typename T>
    typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value);
}

一致する要素の個数が戻り値で返されますが、型が少々複雑になっています。std::iterator_traits<InputIterator>::difference_type は、2つのイテレータ間の距離の差を表現するために定義されている型ですが、単なる整数型であると考えて問題ありません。

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

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

    std::cout << std::count(v.begin(), v.end(), 0) << std::endl;
}

実行結果

2

なお、対象が STLコンテナの場合、countメンバ関数があるのなら、そちらを使った方が効率的です。たとえば、set/multiset(第8章)や map/multimap(第9章)には countメンバ関数があります。

また、指定の値と一致する要素があるかどうかだけに興味がある場面では、count関数を使うと非効率です。count関数は個数を調べることが目的なので、一致する要素が1つ見つかっても、必ず末尾まで処理を続けてしまうからです。このような目的の場合には、以下のように検討してください。

  1. 対象の STLコンテナが findメンバ関数を持っているなら、そちらを使う。
  2. 対象の STLコンテナが countメンバ関数を持っているなら、そちらを使う。
  3. 対象がソート済みであれば、binary_search関数(第22章)を使う。
  4. 対象がソート済みでなければ、find関数を使う。

count_if

count_if関数は、指定した範囲内に、指定の条件と一致する要素が何個あるかを調べます。

namespace std {
    template <typename InputIterator, typename T>
    typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);
}

第3引数が単項叙述関数になっているので、ここに条件を記述した関数や関数オブジェクトを渡せます。たとえば、値が偶数の要素の個数を調べるには、次のようにします。

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

namespace {
    bool isEven(int elem)
    {
        return elem % 2 == 0;
    }
}

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

    std::cout << std::count_if(v.begin(), v.end(), isEven) << std::endl;
}

実行結果

3

find

find関数は、指定した範囲内で、指定の値と一致する最初の要素の位置を返します。 一致する要素が無ければ、末尾の次を指すイテレータが返されます。

特定の値との一致ではなく、もっと複雑な条件一致が必要であれば、find_if関数を検討してください。

namespace std {
    template <typename InputIterator, typename T>
    InputIterator find(InputIterator first, InputIterator last, const T& value);
}

使い方は次のようになります。

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

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

    std::vector<int>::iterator it = std::find(v.begin(), v.end(), 1);
    if (it == v.end()) {
        std::cout << "not found." << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
}

実行結果

1

count関数と違い、一致する要素が見つかった時点で処理が打ち切られるため、一致する要素の有無を確かめることが目的であれば、count関数よりも効率的です。ただし、対象が STLコンテナであり、countメンバ関数があるのなら、そちらを使った方がより効率的です。

find_if

find_if関数は、指定した範囲内で、指定の条件と一致する最初の要素の位置を返します。一致する要素が無ければ、末尾の次を指すイテレータが返されます。

namespace std {
    template <typename InputIterator, typename Predicate>
    InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
}

第3引数が単項叙述関数になっているので、ここに条件を記述した関数や関数オブジェクトを渡せます。たとえば、値が偶数の要素を探すには、次のようにします。

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

namespace {
    bool isEven(int elem)
    {
        return elem % 2 == 0;
    }
}

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

    std::vector<int>::iterator it = std::find_if(v.begin(), v.end(), isEven);
    if (it == v.end()) {
        std::cout << "not found." << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
}

実行結果

0


find_end

find_end関数は、範囲を2つ指定し、1つ目の範囲の中から、2つ目の範囲と同じ内容になっている部分を探します。最後に見つかった、条件に合う範囲の先頭の要素を指すイテレータを返し、見つからなければ第2引数と同じイテレータを返します。

この関数は、search関数の「最後」に見つかった範囲を返すバージョンであり、find関数との関連性はありません。本来なら、search_end関数という名称であるべきものと思われますが、標準化の際のミスで、このような分かりづらい命名になってしまったようです。

namespace std {
    template<typename ForwardIterator1, typename ForwardIterator2>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

    template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
    ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
}

使い方は search関数と同じと考えて問題ありません。一致する範囲が見つかったときに返される結果が異なるだけです。

find_first_of

find_first_of関数は、範囲を2つ指定し、1つ目の範囲の中から、2つ目の範囲にも含まれている要素を探します。見つけた場合は、1つ目の範囲に含まれている要素を指すイテレータを返し、見つからなかった場合は、第2引数のイテレータを返します。

namespace std {
    template <typename ForwardIterator1, typename ForwardIterator2>
    ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

    template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
    ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);
}

1つ目の形式の場合は、通常の一致比較 (==演算子による比較)が行われます。より複雑な条件が必要であれば、第5引数に二項叙述関数を渡せる2つ目の形式の方を使用できます。

#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;
    lst.push_back(7);
    lst.push_back(3);
    lst.push_back(5);

    std::vector<int>::iterator it = std::find_first_of(v.begin(), v.end(), lst.begin(), lst.end());
    if (it == v.end()) {
        std::cout << "not found." << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
}

実行結果

3


mismatch

mismatch関数は、2つの指定した範囲内の要素を比較し、最初に登場する異なった要素を指すイテレータのペア (std::pair)を返します。すべての要素が一致した場合は、第2引数のイテレータと、2つ目の範囲内の対応する要素を指すイテレータとのペアを返します。

2つの範囲内の要素がすべて一致しているかどうかを調べたければ、equal関数(第18章)を使ってください。

namespace std {
    template <typename InputIterator1, typename InputIterator2>
    pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

    template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
    pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);
}

1つ目の形式の場合は、通常の一致比較 (==演算子による比較)が行われます。より複雑な条件が必要であれば、第4引数に二項叙述関数を渡せる2つ目の形式の方を使用できます。

#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);

    std::list<int> lst;
    lst.push_back(0);
    lst.push_back(1);
    lst.push_back(2);
    lst.push_back(4);

    typedef std::pair<std::vector<int>::iterator, std::list<int>::iterator> IteratorPair;
    IteratorPair itPair = std::mismatch(v.begin(), v.end(), lst.begin());
    if (itPair.first == v.end()) {
        std::cout << "same" << std::endl;
    }
    else {
        std::cout << "[" << (*itPair.first) << "," << (*itPair.second) << "]" << std::endl;
    }
}

実行結果

[3,4]

min_element

min_element関数は、指定した範囲内から一番小さい値を持つ要素を探し、その要素を指すイテレータを返します。一番小さい要素が複数ある場合、先頭に近い方が返されます。指定した範囲が空の場合は、第2引数に指定したイテレータが返されます。

namespace std {
    template<typename ForwardIterator>
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

    template<typename ForwardIterator, typename Compare>
    ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);
}

1つ目の形式の場合は、要素の比較に <演算子が使われます。

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

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

    std::vector<int>::iterator it = std::min_element(v.begin(), v.end());
    if (it == v.end()) {
        std::cout << "empty" << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
}

実行結果

0

対象の範囲が空でないことが分かっているのなら、戻り値を受け取らず、以下のように書けます。

std::cout << *std::min_element(v.begin(), v.end()) << std::endl;

2つ目の形式では、第3引数に指定した関数を使って判定を行います。この関数は、2つの要素が引数で渡されるので、第1引数の方が小さい場合に true を返すように実装します。

以下のサンプルプログラムは、絶対値による比較を行う例です。

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

namespace {
    bool absLess(int elem1, int elem2)
    {
        return std::abs(elem1) < std::abs(elem2);
    }
}

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

    std::cout << *std::min_element(v.begin(), v.end(), absLess) << std::endl;
}

実行結果

3

max_element

max_element関数は、指定した範囲内から一番大きい値を持つ要素を探し、その要素を指すイテレータを返します。一番大きい要素が複数ある場合、先頭に近い方が返されます。指定した範囲が空の場合は、第2引数に指定したイテレータが返されます。

namespace std {
    template<typename ForwardIterator>
    ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

    template<typename ForwardIterator, typename Compare>
    ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);
}

min_element関数と同じことなので、詳しい使い方は省略しますが、少し捕捉しておきます。

1つ目の形式のとき、比較に使用されるのは min_element関数と同じく <演算子です。2つの要素を elem1、elem2 だとすると、min_element関数では「elem1 < elem2」のように比較しますが、max_element関数では「elem2 < elem1」のように比較します。

また、2つ目の形式で比較関数を指定する際も、2つの引数が入れ替えられた状態で渡されてくるようになっているので、min_element関数と同じルールで比較関数を実装してください。


練習問題

問題① find、find_if、search、find_end、find_first_of の各関数について、その関係性を整理してください。


解答ページはこちら

参考リンク


更新履歴

’2017/3/25 VisualC++ 2017 に対応。

’2018/4/5 VisualStudio 2013 の対応終了。

’2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

’2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

’2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

’2017/3/25 VisualC++ 2017 に対応。

’2016/11/20 新規作成。



前の章へ (第18章 STLアルゴリズム)

次の章へ (第20章 変更を行う STLアルゴリズム)

C++編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る