std::includes

Défini dans l'en-tête `<algorithm>`
template< class InputIt1, class InputIt2 > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );	(1)	(constexpr depuis C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(2)	(depuis C++17)
template< class InputIt1, class InputIt2, class Compare > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );	(3)	(constexpr depuis C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, Compare comp );	(4)	(depuis C++17)

Renvoie true si la plage triée [first2, last2) est une sous-séquence de la plage triée [first1, last1) (une sous-séquence n'a pas besoin d'être contiguë).

1) Si [first1, last1) ou [first2, last2) n'est pas trié par rapport à operator<(jusqu'à C++20)std::less{}(depuis C++20), le comportement est indéfini.

3) Si [first1, last1) ou [first2, last2) n'est pas trié par rapport à comp, le comportement est indéfini.

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

Ces surcharges ne participent à la résolution de surcharge que 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 triée d'éléments à examiner
first2, last2	-	la paire d'itérateurs définissant la plage triée d'éléments à rechercher
policy	-	la politique d'exécution à utiliser
comp	-	objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de Compare) qui retourne `true` si le premier argument est inférieur au (c'est-à-dire ordonné avant) le second. La signature de la fonction de comparaison doit être équivalente à : `bool cmp(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` indépendamment de la catégorie de valeur (ainsi, `Type1&` n'est pas autorisé, ni `Type1` sauf si pour `Type1` un déplacement équivaut à une copie(depuis C++11)). Les types `Type1` et `Type2` doivent être tels qu'un objet de type `InputIt` puisse être déréférencé puis implicitement converti vers les deux.
Exigences de type
- `InputIt1, InputIt2` doit satisfaire aux exigences de LegacyInputIterator.
- `ForwardIt1, ForwardIt2` doit satisfaire aux exigences de LegacyForwardIterator.
- `Compare` doit satisfaire aux exigences de Compare.

Valeur de retour

true true si [first2, last2) est une sous-séquence de [first1, last1) ; sinon false.

Une séquence vide est une sous-séquence de toute séquence, donc true est retourné si [first2, last2) est vide.

Complexité

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

1,2) Au plus

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

comparaisons utilisant operator<(jusqu'à C++20)std::less{}(depuis C++20).

3,4) Au plus

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

applications de la fonction de comparaison comp.

Exceptions

Les surcharges avec un paramètre template nommé ExecutionPolicy signalent les erreurs comme suit :

Si l'exécution d'une fonction appelée dans le cadre de l'algorithme lève une exception et que ExecutionPolicy est l'une des politiques standard, std::terminate est appelé. Pour tout autre ExecutionPolicy, le comportement est défini par l'implémentation.
Si l'algorithme ne parvient pas à allouer de la mémoire, std::bad_alloc est levée.

Implémentation possible

include (1)

template<class InputIt1, class InputIt2>
bool includes(InputIt1 first1, InputIt1 last1,
              InputIt2 first2, InputIt2 last2)
{
    for (; first2 != last2; ++first1)
    {
        if (first1 == last1 || *first2 < *first1)
            return false;
        if (!(*first1 < *first2))
            ++first2;
    }
    return true;
}

include (3)

template<class InputIt1, class InputIt2, class Compare>
bool includes(InputIt1 first1, InputIt1 last1,
              InputIt2 first2, InputIt2 last2, Compare comp)
{
    for (; first2 != last2; ++first1)
    {
        if (first1 == last1 || comp(*first2, *first1))
            return false;
        if (!comp(*first1, *first2))
            ++first2;
    }
    return true;
}

Exemple

Exécuter ce code

#include <algorithm>
#include <cctype>
#include <iostream>

template<class Os, class Co>
Os& operator<<(Os& os, const Co& v)
{
    for (const auto& i : v)
        os << i << ' ';
    return os << '\t';
}

int main()
{
    const auto
        v1 = {'a', 'b', 'c', 'f', 'h', 'x'},
        v2 = {'a', 'b', 'c'},
        v3 = {'a', 'c'},
        v4 = {'a', 'a', 'b'},
        v5 = {'g'},
        v6 = {'a', 'c', 'g'},
        v7 = {'A', 'B', 'C'};

    auto no_case = [](char a, char b) { return std::tolower(a) < std::tolower(b); };

    std::cout
    << v1 << "\nincludes:\n" << std::boolalpha
    << v2 << ": " << std::includes(v1.begin(), v1.end(), v2.begin(), v2.end()) << '\n'
    << v3 << ": " << std::includes(v1.begin(), v1.end(), v3.begin(), v3.end()) << '\n'
    << v4 << ": " << std::includes(v1.begin(), v1.end(), v4.begin(), v4.end()) << '\n'
    << v5 << ": " << std::includes(v1.begin(), v1.end(), v5.begin(), v5.end()) << '\n'
    << v6 << ": " << std::includes(v1.begin(), v1.end(), v6.begin(), v6.end()) << '\n'
    << v7 << ": " << std::includes(v1.begin(), v1.end(), v7.begin(), v7.end(), no_case)
          << " (case-insensitive)\n";
}

Sortie :

a b c f h x
includes:
a b c   : true
a c     : true
a a b   : false
g       : false
a c g   : false
A B C   : true (case-insensitive)

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants 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 `[first2,` `last2)` est vide	retourne `true` dans ce cas

Voir aussi

set_difference	calcule la différence entre deux ensembles (gabarit de fonction & objet fonction algorithme)
ranges::set_difference (C++20)
search	recherche la première occurrence d'une plage d'éléments (gabarit de fonction & objet fonction algorithme)
ranges::search (C++20)
ranges::includes (C++20)	détermine si une séquence est une sous-séquence d'une autre (objet fonction algorithme)

Prise en charge 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 linguistique
Bibliothèque de concepts (C++20)
Bibliothèque de diagnostics
Bibliothèque de gestion de la mémoire
Bibliothèque de métaprogrammation (C++11)
Bibliothèque d'utilitaires généraux
Bibliothèque de conteneurs
Bibliothèque d'itérateurs
Bibliothèque de 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 de système de fichiers (C++17)
Bibliothèque de support de 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