# std::ranges::find_end

> C++ Atlas: `cppatlas.com/w/cpp/algorithm/ranges/find_end` | Source: https://en.cppreference.com/w/cpp/algorithm/ranges/find_end | Domain: Algorithms | Standards: C++20, C++23

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

## Official Specification Summary (cppreference)

```cpp
// Defined in header <algorithm>

// Call signature

template< std::forward_iterator I1, std::sentinel_for<I1> S1,
          std::forward_iterator I2, std::sentinel_for<I2> S2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity,
          class Proj2 = std::identity >
requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
constexpr ranges::subrange<I1>
    find_end( I1 first1, S1 last1, I2 first2, S2 last2,
              Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {} ); // (1) (since C++20)

template< ranges::forward_range R1, ranges::forward_range R2,
          class Pred = ranges::equal_to,
          class Proj1 = std::identity,
          class Proj2 = std::identity >
requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                    ranges::iterator_t<R2>,
                                    Pred, Proj1, Proj2>
constexpr ranges::borrowed_subrange_t<R1>
    find_end( R1&& r1, R2&& r2, Pred pred = {},
              Proj1 proj1 = {}, Proj2 proj2 = {} ); // (2) (since C++20)
```

1) Searches for the *last* occurrence of the sequence `[first2,` `last2)` in the range `[first1,` `last1)`, after projection with `proj1` and `proj2` respectively. The projected elements are compared using the binary predicate `pred`.

2) Same as (1), but uses `r1` as the first source range and `r2` as the second source range, as if using `ranges::begin(r1)` as `first1`, `ranges::end(r1)` as `last1`, `ranges::begin(r2)` as `first2`, and `ranges::end(r2)` as `last2`.

The function-like entities described on this page are *algorithm function objects* (informally known as *niebloids*), that is:

- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

### Parameters

- `first1, last1` - the range of elements to examine (aka *haystack*)
- `first2, last2` - the range of elements to search for (aka *needle*)
- `r1` - the range of elements to examine (aka *haystack*)
- `r2` - the range of elements to search for (aka *needle*)
- `pred` - binary predicate to compare the elements
- `proj1` - projection to apply to the elements in the first range
- `proj2` - projection to apply to the elements in the second range

### Return value

1) `ranges::subrange<I1>{}` value initialized with expression `{i, i + (i == last1 ? 0: ranges::distance(first2, last2))}` that denotes the last occurrence of the sequence `[first2,` `last2)` in range `[first1,` `last1)` (after projections with `proj1` and `proj2`). If `[first2,` `last2)` is empty or if no such sequence is found, the return value is effectively initialized with `{last1, last1}`.

2) Same as (1), except that the return type is `ranges::borrowed_subrange_t<R1>`.

### Complexity

At most S·(N-S+1) applications of the corresponding predicate and each projection, where S is `ranges::distance(first2, last2)` and N is `ranges::distance(first1, last1)` for (1), or S is `ranges::distance(r2)` and N is `ranges::distance(r1)` for (2).

### Notes

An implementation can improve efficiency of the search if the input iterators model `std::bidirectional_iterator` by searching from the end towards the begin. Modelling the `std::random_access_iterator` may improve the comparison speed. All this however does not change the theoretical complexity of the worst case.

### Possible implementation

```cpp
struct find_end_fn
{
    template<std::forward_iterator I1, std::sentinel_for<I1> S1,
             std::forward_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity, class Proj2 = std::identity>
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr ranges::subrange<I1>
        operator()(I1 first1, S1 last1,
                   I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        if (first2 == last2)
        {
            auto last_it = ranges::next(first1, last1);
            return {last_it, last_it};
        }
        auto result = ranges::search(
            std::move(first1), last1, first2, last2, pred, proj1, proj2);

        if (result.empty())
            return result;

        for (;;)
        {
            auto new_result = ranges::search(
                std::next(result.begin()), last1, first2, last2, pred, proj1, proj2);
            if (new_result.empty())
                return result;
            else
                result = std::move(new_result);
        }
    }

    template<ranges::forward_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>,
                                        Pred, Proj1, Proj2>
    constexpr ranges::borrowed_subrange_t<R1>
        operator()(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(pred),
                       std::move(proj1), std::move(proj2));
    }
};

inline constexpr find_end_fn find_end {};
```

### Example

```cpp
#include <algorithm>
#include <array>
#include <cctype>
#include <iostream>
#include <ranges>
#include <string_view>

void print(const auto haystack, const auto needle)
{
    const auto pos = std::distance(haystack.begin(), needle.begin());
    std::cout << "In \"";
    for (const auto c : haystack)
        std::cout << c;
    std::cout << "\" found \"";
    for (const auto c : needle)
        std::cout << c;
    std::cout << "\" at position [" << pos << ".." << pos + needle.size() << ")\n"
        << std::string(4 + pos, ' ') << std::string(needle.size(), '^') << '\n';
}

int main()
{
    using namespace std::literals;
    constexpr auto secret{"password password word..."sv};
    constexpr auto wanted{"password"sv};

    constexpr auto found1 = std::ranges::find_end(
        secret.cbegin(), secret.cend(), wanted.cbegin(), wanted.cend());
    print(secret, found1);

    constexpr auto found2 = std::ranges::find_end(secret, "word"sv);
    print(secret, found2);

    const auto found3 = std::ranges::find_end(secret, "ORD"sv,
        [](const char x, const char y) { // uses a binary predicate
            return std::tolower(x) == std::tolower(y);
        });
    print(secret, found3);

    const auto found4 = std::ranges::find_end(secret, "SWORD"sv, {}, {},
        [](char c) { return std::tolower(c); }); // projects the 2nd range
    print(secret, found4);

    static_assert(std::ranges::find_end(secret, "PASS"sv).empty()); // => not found
}
```

Output:

```text
In "password password word..." found "password" at position [9..17)
             ^^^^^^^^
In "password password word..." found "word" at position [18..22)
                      ^^^^
In "password password word..." found "ord" at position [19..22)
                       ^^^
In "password password word..." found "sword" at position [12..17)
                ^^^^^
```

### See also

- [`ranges::find_last`](https://en.cppreference.com/w/cpp/algorithm/ranges/find_last) (C++23), [`ranges::find_last_if`](https://en.cppreference.com/w/cpp/algorithm/ranges/find_last) (C++23), [`ranges::find_last_if_not`](https://en.cppreference.com/w/cpp/algorithm/ranges/find_last) (C++23): finds the last element satisfying specific criteria (algorithm function object)
- [`ranges::find`](https://en.cppreference.com/w/cpp/algorithm/ranges/find) (C++20), [`ranges::find_if`](https://en.cppreference.com/w/cpp/algorithm/ranges/find) (C++20), [`ranges::find_if_not`](https://en.cppreference.com/w/cpp/algorithm/ranges/find) (C++20): finds the first element satisfying specific criteria (algorithm function object)
- [`ranges::find_first_of`](https://en.cppreference.com/w/cpp/algorithm/ranges/find_first_of) (C++20): searches for any one of a set of elements (algorithm function object)
- [`ranges::adjacent_find`](https://en.cppreference.com/w/cpp/algorithm/ranges/adjacent_find) (C++20): finds the first two adjacent items that are equal (or satisfy a given predicate) (algorithm function object)
- [`ranges::search`](https://en.cppreference.com/w/cpp/algorithm/ranges/search) (C++20): searches for the first occurrence of a range of elements (algorithm function object)
- [`ranges::search_n`](https://en.cppreference.com/w/cpp/algorithm/ranges/search_n) (C++20): searches for the first occurrence of a number consecutive copies of an element in a range (algorithm function object)
- [`find_end`](https://en.cppreference.com/w/cpp/algorithm/find_end): finds the last sequence of elements in a certain range (function template)

---
Attribution: content from https://en.cppreference.com/w/cpp/algorithm/ranges/find_end (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.