Namespaces
Variants

    std::find_end

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围上的算法 (C++20)
    受约束算法，例如 ranges::copy, ranges::sort, ...
    排序和相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分搜索操作
    (在已划分范围上)
    集合操作（在已排序范围上）
    合并操作（在已排序范围上）
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <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。 ​

    策略 - 要使用的执行策略
    类型要求
    -
    ForwardIt1必须满足LegacyForwardIterator的要求。
    -
    ForwardIt2必须满足LegacyForwardIterator的要求。

    返回值

    指向源范围中目标范围最后一次出现的起始位置的迭代器。

    如果目标范围为空或未在源范围中出现，则返回last1。

    复杂度

    给定 N1 作为 std::distance(first1, last1) 和 N2 作为 std::distance(first2, last2):

    1) 最多 N2⋅(N1-N2+1) 次比较，使用 operator==。
    2) 最多 N2⋅(N1-N2+1) 次调用 p。
    3) 𝓞(N2⋅(N1-N2+1)) 次比较，使用 operator==。
    4) 𝓞(N2⋅(N1-N2+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 “出现”的条件不正确 已修正

    另见

    (C++20)
    		 查找特定范围内的最后一组元素
    (算法函数对象)
    		搜索一个元素范围的首次出现
    (函数模板 & 算法函数对象)
    (C++20)
    		判断一个序列是否是另一个的子序列
    (函数模板 & 算法函数对象)
    (C++20)
    		查找第一对相等的相邻元素（或满足给定谓词）
    (函数模板 & 算法函数对象)
    (C++20)
    (C++11)
    		 查找第一个满足特定条件的元素
    (函数模板 & 算法函数对象)
    (C++20)(C++20)(C++20)
    		搜索一组元素中的任何一个
    (函数模板 & 算法函数对象)
    (C++20)
    		在范围中搜索元素的连续出现指定次数
    (函数模板 & 算法函数对象)
    (C++20)