std::find_end

Défini dans l'en-tête `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(1)	(constexpr depuis C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(2)	(constexpr depuis C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(depuis 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)	(depuis C++17)

Recherche la dernière occurrence de la plage cible [first2, last2) dans la plage source [first1, last1).

1) Les éléments sont comparés à l'aide de operator==.

2) Les éléments sont comparés à l'aide du prédicat binaire donné p.

3,4) Identique à (1,2), mais exécuté selon policy.

Ces surcharges participent à la résolution de surcharge uniquement si la valeur de l'expression suivante est true :

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(jusqu'à C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(depuis C++20)

Paramètres

first1, last1	-	la paire d'itérateurs définissant la plage source
first2, last2	-	la paire d'itérateurs définissant la plage cible
p	-	prédicat binaire qui renvoie `true` si les éléments doivent être considérés comme égaux. La signature de la fonction prédicat doit être équivalente à la suivante : `bool pred(const Type1 &a, const Type2 &b);` Bien que la signature n'ait pas besoin d'avoir `const &`, la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs de type (éventuellement const) `Type1` et `Type2` quelle que soit la catégorie de valeur (ainsi, `Type1 &` n'est pas autorisé, ni `Type1` sauf si pour `Type1` un déplacement est équivalent à une copie(depuis C++11)). Les types `Type1` et `Type2` doivent être tels que les objets de types `ForwardIt1` et `ForwardIt2` puissent être déréférencés puis implicitement convertis respectivement en `Type1` et `Type2`.
policy	-	la politique d'exécution à utiliser
Exigences de type
- `ForwardIt1` doit satisfaire aux exigences de LegacyForwardIterator.
- `ForwardIt2` doit satisfaire aux exigences de LegacyForwardIterator.

Valeur de retour

Itérateur vers le début de la dernière occurrence de la plage cible dans la plage source.

Si la plage cible est vide ou qu'elle n'apparaît pas dans la plage source, last1 est renvoyé.

Complexité

Étant donné $\scriptsize N_1$ $N 1$ comme std::distance(first1, last1) et $\scriptsize N_2$ $N 2$ comme std::distance(first2, last2) :

1) Au plus

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

comparaisons à l'aide de operator==.

2) Au plus

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

applications de p.

3)

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

comparaisons à l'aide de operator==.

4)

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

applications de p.

Exceptions

3,4) Pendant le processus d'exécution :

Si les ressources mémoire temporaires nécessaires à la parallélisation ne sont pas disponibles, std::bad_alloc est levée.
Si une exception non interceptée est levée lors de l'accès aux objets via un argument d'algorithme, le comportement est déterminé par la politique d'exécution (pour les politiques standard, std::terminate est invoquée).

Implémentation possible

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;
}

Exemple

Exécuter ce code

#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);
    }
}

Sortie :

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

Rapports de défauts

Les rapports de défauts suivants modifiant le comportement ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR	Appliqué à	Comportement tel que publié	Comportement correct
LWG 1205	C++98	la valeur de retour n'était pas claire si la plage cible est vide	renvoie `last1` dans ce cas
LWG 2150	C++98	la condition d'« occurrence » était incorrecte	corrigée

Voir aussi

ranges::find_end (C++20)	trouve la dernière séquence d'éléments dans une certaine plage (objet fonction algorithme)
search	recherche la première occurrence d'une plage d'éléments (modèle de fonction & objet fonction algorithme)
ranges::search (C++20)
includes	détermine si une séquence est une sous-séquence d'une autre (modèle de fonction & objet fonction algorithme)
ranges::includes (C++20)
adjacent_find	trouve les deux premiers éléments adjacents égaux (ou satisfaisant un prédicat donné) (modèle de fonction & objet fonction algorithme)
ranges::adjacent_find (C++20)
findfind_iffind_if_not (C++11)	trouve le premier élément satisfaisant des critères spécifiques (modèle de fonction & objet fonction algorithme)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)
find_first_of	recherche l'un quelconque d'un ensemble d'éléments (modèle de fonction & objet fonction algorithme)
ranges::find_first_of (C++20)
search_n	recherche la première occurrence d'un nombre de copies consécutives d'un élément dans une plage (modèle de fonction & objet fonction algorithme)
ranges::search_n (C++20)

Support du compilateur
Autonome et hébergé
Langage
Bibliothèque standard
En-têtes de la bibliothèque standard
Exigences nommées
Macros de test de fonctionnalités (C++20)
Bibliothèque de support du langage
Bibliothèque des concepts (C++20)
Bibliothèque de diagnostics
Bibliothèque de gestion de la mémoire
Bibliothèque de métaprogrammation (C++11)
Bibliothèque de services généraux
Bibliothèque de conteneurs
Bibliothèque d'itérateurs
Bibliothèque des plages (C++20)
Bibliothèque d'algorithmes
Bibliothèque de chaînes
Bibliothèque de traitement de texte
Bibliothèque numérique
Bibliothèque de date et heure
Bibliothèque d'entrée/sortie
Bibliothèque du système de fichiers (C++17)
Bibliothèque de support de la concurrence (C++11)
Bibliothèque de contrôle d'exécution (C++26)
Spécifications techniques
Index des symboles
Bibliothèques externes

fr.cppreference.net

Namespaces

Variants