最新の C++ でコンテナーをフィルター処理する 12 の異なる方法

C++ でフィルター関数を実装する方法がいくつあるか知っていますか?

問題は比較的簡単に理解できます - コンテナを取得し、述語に一致する要素をコピーし、新しいコンテナを返します - 標準ライブラリで演習を行い、いくつかのアイデアを確認することをお勧めします。また、いくつかの最新の C++ 手法を適用することもできます。

始めましょう!

問題ステートメント

フィルタで正確に 次のインターフェースを持つ関数を意味します:

auto Filter(const Container& cont, UnaryPredicate p) {}

コンテナーと述語を受け取り、述語を満たす要素を含む出力コンテナーを作成します。

次のように使用できます。

const std::vector<std::string> vec{ "Hello", "**txt", "World", "error", "warning", "C++", "****" };

auto filtered = FilterRaw(vec, [](auto& elem) { return !elem.starts_with('*'); });
// filtered should have "Hello", "World", "error", "warning", "C++"

さらに、ウィキペディアと関数型プログラミングの定義を見ることができます:

このような関数を作成することは、標準ライブラリのさまざまなオプションとアルゴリズムを使用する良い練習になります。さらに、関数は反復子などの内部的なものを隠しているため、範囲ベースのバージョンに似ています。

最初のオプションから始めましょう:

古き良き生のループ

生のループを避けるのは良いことですが、特に次のような単純な問題の場合、問題を完全に理解するのに役立つかもしれません:

template <typename T, typename Pred>
auto FilterRaw(const std::vector<T>& vec, Pred p) {
    std::vector<T> out;
    for (auto&& elem : vec)
        if (p(elem))
            out.push_back(elem);
    return out;
}

シンプルですが非常に効果的です。

この単純な実装のいくつかの優れた点に注目してください。

  • コードは auto を使用しています 型推論を返すため、明示的な型を記述する必要はありません。
  • 出力ベクトルを値で返しますが、コンパイラは (ほとんどの場合) コピー省略を利用するか、さらに悪いことにセマンティクスを移動します。

生のループを扱っているので、少し時間を取って、C++11 で得られる範囲ベースの for ループを評価する必要があります。この機能がなければ、コードはさらに悪くなります:

template <typename T, typename Pred>
std::vector<T> FilterRawOld(const std::vector<T>& vec, Pred p) {
  std::vector<T> out;
  for (typename std::vector<T>::const_iterator it = begin(vec); it != end(vec); ++it)
    if (p(*it))
      out.push_back(*it);
  return out;
}

それでは、より良いものに移り、既存の std:: のいくつかを見てみましょう 実装に役立つ可能性のあるアルゴリズム。

std::copy_if でフィルタリング

std::copy_if おそらく最も自然な選択です。 back_inserter を活用できます 次に、一致した要素を出力ベクトルにプッシュします。

template <typename T, typename Pred>
auto FilterCopyIf(const std::vector<T>& vec, Pred p) {
    std::vector<T> out;
    std::copy_if(begin(vec), end(vec), std::back_inserter(out), p);
    return out;
}

std::remove_copy_if

しかし、逆のこともできます:

template <typename T, typename Pred>
auto FilterRemoveCopyIf(const std::vector<T>& vec, Pred p) {
    std::vector<T> out;
    std::remove_copy_if(begin(vec), end(vec), 
                        std::back_inserter(out), std::not_fn(p));
    return out;
}

要件によっては、remove_copy_if も使用できます。 述語を満たさない要素をコピーします。私たちの実装では、 std::not_fn を追加する必要がありました 述語を逆にします。

1 つのコメント:std::not_fn C++17 以降で利用可能です。

有名な消去イディオム

template <typename T, typename Pred>
auto FilterRemoveErase(const std::vector<T>& vec, Pred p) {
    auto out = vec;
    out.erase(std::remove_if(begin(out), end(out), std::not_fn(p)), end(out));
    return out;
}

ここで少し不便です。入力コンテナーを変更したくないため、最初にコピーする必要がありました。これにより、余分な処理が発生する可能性があり、back_inserter を使用するよりも効率的ではありません .

C++20 の追加

いくつかの例を見た後、ようやく C++20 の便利な機能を確認できます。

template <typename T, typename Pred>
auto FilterEraseIf(const std::vector<T>& vec, Pred p) {
    auto out = vec;
    std::erase_if(out, std::not_fn(p));
    return out;
}

ちょっとしたことですが、このアプローチではすべての要素が最初にコピーされます。そのため、copy_if でのアプローチよりも遅くなる可能性があります。 .

いくつかの C++20 範囲の追加

そして最後に、Ranges を使用したソリューション:

template <typename T, typename Pred>
auto FilterRangesCopyIf(const std::vector<T>& vec, Pred p) {
    std::vector<T> out;
    std::ranges::copy_if(vec, std::back_inserter(out), p);
    return out;
}

コードは非常にシンプルで、Filter とさえ言えます。 関数はここでは意味がありません.Ranges インターフェイスはコードで直接使用するのがとても簡単だからです.

より一般的なものにする

これまで、std::vector で動作するコードを示してきました。 .しかし、他のコンテナはどうですか?

Filter を作ってみましょう より一般的に機能します。これは std::erase_if で簡単です 多くの標準コンテナーのオーバーロードがあります:

template <typename TCont, typename Pred>
auto FilterEraseIfGen(const TCont& cont, Pred p) {
    auto out = cont;
    std::erase_if(out, std::not_fn(p));
    return out;
}

範囲の別のバージョン。

template <typename TCont, typename Pred>
auto FilterRangesCopyIfGen(const TCont& vec, Pred p) {
    TCont out;
    std::ranges::copy_if(vec, std::back_inserter(out), p);
    return out;
}

現在、std::vector だけでなく、他のコンテナーでも動作します。 :

std::set<std::string> mySet{ 
    "Hello", "**txt", "World", "error", "warning", "C++", "****" 
};
auto filtered = FilterEraseIfGen(mySet, [](auto& elem) { 
    return !elem.starts_with('*'); 
});

一方、事前にすべての要素をコピーしたくない場合は、さらに作業が必要になる場合があります。

アプローチの場合の一般的なコピー

主な問題は、back_inserter を使用できないことです。 連想コンテナ、または push_back() をサポートしていないコンテナ メンバー関数。その場合、std::inserter にフォールバックできます

そのため、考えられる解決策の 1 つは、特定のコンテナーが push_back をサポートしているかどうかを検出することです。 :

template <typename T, typename = void>
struct has_push_back : std::false_type {};

template <typename T>
struct has_push_back<T,
  std::void_t<
    decltype(std::declval<T>().push_back(std::declval<typename T::value_type>()))
    >
  > : std::true_type {};

template <typename TCont, typename Pred>
auto FilterCopyIfGen(const TCont& cont, Pred p) {
    TCont out;
    if constexpr(has_push_back<TCont>::value)
        std::copy_if(begin(cont), end(cont), std::back_inserter(out), p);
    else
        std::copy_if(begin(cont), end(cont), std::inserter(out, out.begin()), p);

    return out;
}

これはうまくいくようです!しかしもちろん、私はより良いコードやアイデアを受け入れています :)

私は、C++17 で関数のオーバーロードを検出する方法、std::from_chars の例 - C++ ストーリーからアプローチしました。

2021 年 6 月の更新:

概念を活用して、コードをはるかに単純にすることができます。ご覧ください (danesh110 のコメントによる)

template <typename T> 
concept has_push_back = requires(T container, typename T::value_type v) { 
    container.push_back(v);
};

詳細については、if constexpr を使用したコードの簡素化と C++17/C++20 の概念 - C++ ストーリーを参照してください。

その他の C++20 の概念

さらにコンセプトを追加し、他のテンプレート パラメータを制限できます。

たとえば、次のように記述します:

auto filtered = FilterCopyIf(vec, [](auto& elem, int a) { 
    return !elem.starts_with('*'); 
});

したがって、これは単項述語への 2 つの入力引数であり、Visual Studio では次のようになります。

C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.28.29333\include\algorithm(1713,13): error C2672: 'operator __surrogate_func': no matching overloaded function found
1>  C:\Users\Admin\Documents\GitHub\articles\filterElements\filters.cpp(38): message : see reference to function template instantiation '_OutIt std::copy_if<std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>,std::back_insert_iterator<std::vector<_Ty,std::allocator<_Ty>>>,Pred>(_InIt,_InIt,_OutIt,_Pr)' being compiled
1>          with

しかし、数行後、

error C2780: 'auto main::<lambda_4>::operator ()(_T1 &,int) const': expects 2 arguments - 1 provided

概念を試して、述語を std::predicate に制限することができます 、標準ライブラリの既存の概念。この場合、1 つの引数を取り、bool に変換可能な型を返す関数が必要です。 .

template <typename T, std::predicate<const T&> Pred>   // <<
auto FilterCopyIfConcepts(const std::vector<T>& vec, Pred p) {
    std::vector<T> out;
    std::copy_if(begin(vec), end(vec), std::back_inserter(out), p);
    return out;
}

そして、問題のあるコード:

auto filtered = FilterCopyIfConcepts(vec, [](auto& elem, int a) { 
    return !elem.starts_with('*'); 
});

次のように述べています:

1>  filters.cpp(143,19): error C2672: 'FilterCopyIfConcepts': no matching overloaded function found
1>  filters.cpp(143,101): error C7602: 'FilterCopyIfConcepts': the associated constraints are not satisfied

一部の内部ではなくトップレベルの関数に関するメッセージがあるので、少しは良いのですが、なぜ、どの制約が満たされていないのかを確認することは素晴らしいことです.

パラレルにする?

C++17 以降、並列アルゴリズムも用意されているので、それをリストに追加してみませんか?

見た目通り std::copy_if par は Visual Studio ではサポートされておらず、この問題はもう少し複雑です。この話題はひとまず置いておいて、次回解決しようと思います。

手動バージョンを作成できます:

std::mutex mut;
    std::for_each(std::execution::par, begin(vec), end(vec),
        [&out, &mut, p](auto&& elem) {
            if (p(elem))
            {
                std::unique_lock lock(mut);
                out.push_back(elem);
            }
        });

しかし、これはブロックされることが多く、おそらく最善の方法ではありません。このトピックに関する今後の実験にご期待ください。

これが最新の更新と実験です:C++ での Parallel copy_If の実装 - C++ ストーリー

まとめ

この記事では、さまざまなコンテナーから要素をフィルター処理する少なくとも 12 の可能な方法を示しました。 std::vector で動作するコードから始めました 、また、より一般的で他のコンテナー タイプに適用できるようにする複数の方法を見てきました。たとえば、std::erase_if を使用しました C++20、概念、さらにはカスタム型特性から。

別の Github リポジトリで私のコードを参照してください:

https://github.com/fenbf/articles/blob/master/filterElements/filters.cpp

バック トゥ ユー

  • 他にどのような選択肢がありますか?
  • どのテクニックが好きですか?

記事の下のコメントでお知らせいただくか、この @r/cpp スレッドのディスカッションに参加してください。