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

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 は、２つのイテレータ間の距離の差を表現するために定義されている型ですが、単なる整数型^📘であると考えて問題ありません。

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

実行結果：

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

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

対象の STLコンテナが findメンバ関数を持っているなら、そちらを使う。
対象の STLコンテナが countメンバ関数を持っているなら、そちらを使う。
対象がソート済みであれば、binary_search関数（第２２章）を使う。
対象がソート済みでなければ、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);
}

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

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

実行結果：

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;
    }
}

実行結果：

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

find_if 🔗

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

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

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

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

実行結果：

search 🔗

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

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

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

１つ目の形式の場合は、通常の一致比較 (==演算子による比較）が行われます。

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

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

実行結果：

２つ目の形式の場合は、第５引数に与えた二項叙述関数を使って比較を行います。以下の例では、文字列が空（長さが 0）であるべきか否かを bool型配列に入れておき、その指定にしたがっている範囲を探しています。

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

namespace {
    bool checkEmpty(const std::string& s, bool flag)
    {
        return s.empty() == flag;
    }
}

int main()
{
    std::vector<std::string> v;
    v.push_back("abc");
    v.push_back("");
    v.push_back("xxxxx");
    v.push_back("");
    v.push_back("");

    // 「空文字列でない」「空文字列である」「空文字列である」の順で要素が並んでいる部分を探したい
    const bool flags[] = { false, true, true };

    std::vector<std::string>::iterator it = std::search(v.begin(), v.end(), flags, flags + 3, checkEmpty);
    if (it == v.end()) {
        std::cout << "not found." << std::endl;
    }
    else {
        std::cout << *it << std::endl;
    }
}

実行結果：

xxxxx

find_end 🔗

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

この関数は、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関数は、範囲を２つ指定し、１つ目の範囲の中から、２つ目の範囲にも含まれている要素を探します。見つけた場合は、１つ目の範囲に含まれている要素を指すイテレータを返し、見つからなかった場合は、第２引数のイテレータを返します。

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

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

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

実行結果：

mismatch 🔗

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

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

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

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

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

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

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

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

実行結果：

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

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

２つ目の形式では、第３引数に指定した関数を使って判定を行います。この関数は、２つの要素が引数で渡されるので、第１引数の方が小さい場合に 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;
}

実行結果：

max_element 🔗

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

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関数と同じことなので、詳しい使い方は省略しますが、少し捕捉しておきます。

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

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

練習問題 🔗

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

解答ページはこちら。

参考リンク 🔗

Programming Place Plus　C++編　参考書籍
- 当サイトの参考書籍一覧ページ。C++ に関する書籍を多数紹介。
Programming Place Plus　C++編　リンク集
- 当サイトの参考Webサイト集。C++ の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

’2021/9/30
- C++11 に関する記述を削除（C++11 は新C++編で対応する）
’2017/3/25
- VisualC++ 2017 に対応。
’2018/4/5
- Visual Studio 2013 の対応終了。
’2018/4/2
- 「VisualC++」という表現を「Visual Studio」に統一。
’2018/1/5
- コンパイラの対応状況について、対応している場合は明記しない方針にした。
’2017/7/30
- clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。
’2017/3/25
- VisualC++ 2017 に対応。
’2016/11/20
- 新規作成。

前の章へ　（第１８章　STLアルゴリズム）

次の章へ　（第２０章　変更をおこなう STLアルゴリズム）

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

Programming Place Plus のトップページへ

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

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

この章の概要 🔗