std::find_end() 算法

自 C++20 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
constexpr ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last,
                     BinaryPredicate p );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );

// (4)
template<
  class ExecutionPolicy,
  class ForwardIt1,
  class ForwardIt2,
  class BinaryPredicate
>
  ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
      ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

自 C++17 起

// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last,
                     BinaryPredicate p );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );

// (4)
template<
  class ExecutionPolicy,
  class ForwardIt1,
  class ForwardIt2,
  class BinaryPredicate
>
  ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
      ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p );

C++17 之前

// (1)
template< class ForwardIt1, class ForwardIt2 >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last );
// (2)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate >
ForwardIt1 find_end( ForwardIt1 first, ForwardIt1 last,
                     ForwardIt2 s_first, ForwardIt2 s_last,
                     BinaryPredicate p );

在范围 [first; last) 中搜索序列 [s_first; s_last) 的最后一次出现。

• (1) 使用 operator== 比较元素。

• (2) 使用给定的二元谓词 p 比较元素。

• (3 - 4) 与 (1 - 2) 相同，但根据 policy 执行。

  重载决议

  这些重载只有在 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  (直到 C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>  (自 C++20 起) 为 true 时才参与重载决议。

参数

first last	要检查的元素范围。
s_first s_last	要搜索的元素范围。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
p	二元谓词，如果元素应被视为相等，则返回 true。 函数的签名应与以下内容等效 bool fun(const Type1& a, const Type2& b); 签名不需要包含 const&。 Type1 和 Type2 的类型必须使得 ForwardIt1 和 ForwardIt2 类型的对象可以被解引用，然后隐式转换为它们。

类型要求

ForwardIt1 ForwardIt2

LegacyForwardIterator

返回值

指向范围 [first; last) 中序列 [s_first; s_last) 的最后一次出现的起始迭代器。

如果 [s_first; s_last) 为空或未找到此类序列，则返回 last。 (自 C++11 起)
如果未找到此类序列，则返回 last。 (直到 C++11)

复杂度

给定 S 为 std::distance(s_first, s_last)，N 为 std::distance(first, last)

• (1, 3) - 最多 S * (N − S + 1) 次比较。
• (2, 4) - 最多 S * (N − S + 1) 次 p 应用。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数抛出异常且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

可能的实现

find_end (1)

template<class ForwardIt1, class ForwardIt2>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last)
{
    if (s_first == s_last)
        return last;
    ForwardIt1 result = last;
    while (true)
    {
        ForwardIt1 new_result = std::search(first, last, s_first, s_last);
        if (new_result == last)
            break;
        else
        {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}

find_end (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPredicate>
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last,
                    BinaryPredicate p)
{
    if (s_first == s_last)
        return last;
    ForwardIt1 result = last;
    while (true)
    {
        ForwardIt1 new_result = std::search(first, last, s_first, s_last, p);
        if (new_result == last)
            break;
        else
        {
            result = new_result;
            first = result;
            ++first;
        }
    }
    return result;
}

示例

Main.cpp

#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 (auto const& 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 (auto const& 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