std::find_end

ヘッダ `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	で定義 (1)	(C++20 から constexpr)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(2)	(C++20 から constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(C++17 から)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(4)	(C++17 から)

対象範囲 [first2, last2) の最後の出現をソース範囲 [first1, last1) 内で検索します。

1) 要素の比較には operator== を使用します。

2) 要素の比較には指定された二項述語 p を使用します。

3,4) (1,2) と同じですが、policy に従って実行されます。

これらのオーバーロードは、以下の式の値が true である場合にのみオーバーロード解決に参加します:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20 まで)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(C++20 から)

引数

first1, last1	-	ソース範囲
を定義するイテレータのペアfirst2, last2	-	ターゲット範囲
を定義するイテレータのペアp	-	要素を等しいと扱う場合に `true` を返す二項述語。述語関数のシグネチャは以下と同等である必要があります: `bool pred(const Type1 &a, const Type2 &b);` シグネチャに `const &` が含まれている必要はありませんが、関数は渡されたオブジェクトを変更してはならず、型 (const の可能性がある) `Type1` および `Type2` のすべての値を値カテゴリに関係なく受け入れられる必要があります (したがって、`Type1 &` は許可されません。また、`Type1` は、`Type1` ムーブがコピーと同等である場合を除き、許可されません(C++11 から))。型 `Type1` および `Type2` は、型 `ForwardIt1` および `ForwardIt2` のオブジェクトを逆参照し、それぞれ `Type1` および `Type2` に暗黙的に変換できるようにする必要があります。
policy	-	使用する実行ポリシー
型要件
- `ForwardIt1` は LegacyForwardIterator の要件を満たす必要があります。
- `ForwardIt2` は LegacyForwardIterator の要件を満たす必要があります。

戻り値

ソース範囲内のターゲット範囲の最後の出現の先頭を指すイテレータ。

ターゲット範囲が空であるか、ソース範囲内に出現しない場合、last1 が返されます。

計算量

$\scriptsize N_1$ $N 1$ を std::distance(first1, last1) とし、$\scriptsize N_2$ $N 2$ を std::distance(first2, last2) とすると:

1) 最大

N 2 \cdot(N 1 -N 2 +1)

回の operator== による比較。

2) 最大

N 2 \cdot(N 1 -N 2 +1)

回の p の適用。

3)

𝓞(N 2 \cdot(N 1 -N 2 +1))

回の operator== による比較。

4)

𝓞(N 2 \cdot(N 1 -N 2 +1))

回の p の適用。

例外

3,4) 実行中:

並列化に必要な一時メモリリソースが利用できない場合、std::bad_alloc がスローされます。
アルゴリズムの引数を介してオブジェクトにアクセスしているときにキャッチされない例外がスローされた場合、動作は実行ポリシーによって決まります (標準ポリシーの場合、std::terminate が呼び出されます)。

実装例

find_end (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2)
{
    if (first2 == last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, last2);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

find_end (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2, BinaryPred p)
{
    if (first2== last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, first2, p);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

例

このコードを実行する

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>

auto print_result = [](auto result, const auto& v)
{
    result == v.end()
        ? std::cout << "Sequence not found\n"
        : std::cout << "Last occurrence is at: " << std::distance(v.begin(), result)
                    << '\n';
};

int main()
{
    const auto v = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    
    for (const auto& x : {std::array{1, 2, 3}, {4, 5, 6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end()); // overload (1)
        print_result(iter, v);
    }
    
    for (const auto& x : {std::array{-1, -2, -3}, {-4, -5, -6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end(), // overload (3)
                                  [](int x, int y)
                                  {
                                      return std::abs(x) == std::abs(y);
                                  });
        print_result(iter, v);
    }
}

出力:

Last occurrence is at: 8
Sequence not found
Last occurrence is at: 8
Sequence not found

欠陥報告

以下の動作を変更する欠陥報告は、以前に公開された C++ 標準に遡って適用されました。

DR	適用先	公開時の動作	正しい動作
LWG 1205	C++98	ターゲット範囲が空の場合の戻り値が不明確でした	この場合は `last1` を返す
LWG 2150	C++98	「出現」の条件が正しくありませんでした	修正されました

関連項目

ranges::find_end (C++20)	指定された範囲内の要素の最後のシーケンスを見つける (アルゴリズム関数オブジェクト)
search	要素の範囲の最初の出現を検索する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::search (C++20)	要素の範囲の最初の出現を検索する (関数テンプレート & アルゴリズム関数オブジェクト)
includes	あるシーケンスが別のシーケンスの部分列であるかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::includes (C++20)	あるシーケンスが別のシーケンスの部分列であるかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト)
adjacent_find	等しい (または指定された述語を満たす) 最初の隣接する 2 つの項目を見つける (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::adjacent_find (C++20)
findfind_iffind_if_not (C++11)	特定の基準を満たす最初の要素を見つける (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)	特定の基準を満たす最初の要素を見つける (関数テンプレート & アルゴリズム関数オブジェクト)
find_first_of	要素の集合のいずれか 1 つを検索する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::find_first_of (C++20)	要素の集合のいずれか 1 つを検索する (関数テンプレート & アルゴリズム関数オブジェクト)
search_n	範囲内の要素の連続したコピーの最初の出現を検索する (関数テンプレート & アルゴリズム関数オブジェクト)
ranges::search_n (C++20)	範囲内の要素の連続したコピーの最初の出現を検索する (関数テンプレート & アルゴリズム関数オブジェクト)

コンパイラサポート
フリースタンディングとホステッド
言語
標準ライブラリ
標準ライブラリヘッダ
名前付き要件
機能テストマクロ (C++20)
言語サポートライブラリ
コンセプトライブラリ (C++20)
診断ライブラリ
メモリ管理ライブラリ
メタプログラミングライブラリ (C++11)
汎用ユーティリティライブラリ
コンテナライブラリ
イテレータライブラリ
レンジライブラリ (C++20)
アルゴリズムライブラリ
文字列ライブラリ
テキスト処理ライブラリ
数値ライブラリ
日付と時刻ライブラリ
入出力ライブラリ
ファイルシステムライブラリ (C++17)
並行処理サポートライブラリ (C++11)
実行制御ライブラリ (C++26)
技術仕様書
シンボルインデックス
外部ライブラリ

ja.cppreference.net

Namespaces

Variants

std::find_end

目次

引数

戻り値

計算量

例外

実装例

例

欠陥報告

関連項目