std::find_end

Searches for the last occurrence of the sequence [ s_first ,  s_last ) in the range [first, last)

Parameters

Return value

Iterator to the beginning of last occurrence of the sequence [ s_first ,  s_last ) in range [first, last)

If [ s_first ,  s_last ) is empty or if no such sequence is found, last

Complexity

Given \(\scriptsize N\) N as std::distance(first, last) and \(\scriptsize S\) S as std::distance(s_first, s_last)

Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

Possible implementation

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
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;
}

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 s_first, ForwardIt2 s_last,
                    BinaryPred 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;
}

Example

#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

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

See also