std::includes

Definiert in Header `<algorithm>`
template< class InputIt1, class InputIt2 > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );	(1)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool includes( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(2)	(seit C++17)
template< class InputIt1, class InputIt2, class Compare > bool includes( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );	(3)	(constexpr seit 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)	(seit C++17)

Gibt true zurück, wenn der sortierte Bereich [first2, last2) eine Teilsequenz des sortierten Bereichs [first1, last1) ist (eine Teilsequenz muss nicht zusammenhängend sein).

1) Wenn [first1, last1) oder [first2, last2) nicht sortiert bezüglich operator<(bis C++20)std::less{}(seit C++20) ist, ist das Verhalten undefiniert.

3) Wenn [first1, last1) oder [first2, last2) nicht sortiert bezüglich comp ist, ist das Verhalten undefiniert.

2,4) Wie (1,3), aber ausgeführt gemäß policy.

Diese Überladungen nehmen nur an der Überladungsauflösung teil, wenn der Wert des folgenden Ausdrucks true ist:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(bis C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(seit C++20)

Parameter

first1, last1	-	das Paar von Iteratoren, das den sortierten Bereich der zu untersuchenden Elemente definiert
first2, last2	-	das Paar von Iteratoren, das den sortierten Bereich der zu suchenden Elemente definiert
policy	-	die Ausführungsrichtlinie zur Verwendung
comp	-	Vergleichsfunktionsobjekt (d.h. ein Objekt, das die Anforderungen von Compare erfüllt), das `true` zurückgibt, wenn das erste Argument kleiner als das zweite ist (d.h. es wird vor dem zweiten geordnet). Die Signatur der Vergleichsfunktion sollte wie folgt sein: `bool cmp(const Type1& a, const Type2& b);` Obwohl die Signatur kein `const&` haben muss, darf die Funktion die ihr übergebenen Objekte nicht verändern und muss alle Werte des Typs (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie akzeptieren können (daher ist `Type1&` nicht erlaubt, ebenso wenig `Type1`, es sei denn, für `Type1` ist eine Verschiebung äquivalent zu einer Kopie(seit C++11)). Die Typen `Type1` und `Type2` müssen so sein, dass ein Objekt vom Typ `InputIt` dereferenziert und dann implizit in beide konvertiert werden kann.
Typanforderungen
- `InputIt1, InputIt2` muss die Anforderungen von LegacyInputIterator erfüllen.
- `ForwardIt1, ForwardIt2` muss die Anforderungen von LegacyForwardIterator erfüllen.
- `Compare` muss die Anforderungen von Compare erfüllen.

Rückgabewert

true wenn [first2, last2) eine Teilsequenz von [first1, last1) ist; andernfalls false.

Eine leere Sequenz ist eine Teilsequenz jeder Sequenz, daher wird true zurückgegeben, wenn [first2, last2) leer ist.

Komplexität

Gegeben $\scriptsize N_1$ $N 1$ als std::distance(first1, last1) und $\scriptsize N_2$ $N 2$ als std::distance(first2, last2):

1,2) Höchstens

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

Vergleiche unter Verwendung von operator<(bis C++20)std::less{}(seit C++20).

3,4) Höchstens

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

Anwendungen der Vergleichsfunktion comp.

Ausnahmen

Die Überladungen mit einem Vorlagenparameter namens ExecutionPolicy melden Fehler wie folgt:

Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und ExecutionPolicy eine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jedes andere ExecutionPolicy ist das Verhalten implementationsdefiniert.
Wenn der Algorithmus keinen Speicher zuweisen kann, wird std::bad_alloc ausgelöst.

Mögliche Implementierung

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

Beispiel

Diesen Code ausführen

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

Ausgabe:

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)

Fehlerberichte

Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR	Angewendet auf	Verhalten wie veröffentlicht	Korrektes Verhalten
LWG 1205	C++98	der Rückgabewert war unklar, wenn `[first2,` `last2)` leer ist	gibt `true` in diesem Fall zurück

Siehe auch

set_difference	berechnet die Differenz zwischen zwei Mengen (Funktionsvorlage & Algorithmusfunktionsobjekt)
ranges::set_difference (C++20)
search	durchsucht nach dem ersten Vorkommen eines Bereichs von Elementen (Funktionsvorlage & Algorithmusfunktionsobjekt)
ranges::search (C++20)
ranges::includes (C++20)	bestimmt, ob eine Sequenz eine Teilsequenz einer anderen ist (Algorithmusfunktionsobjekt)

Compiler-Unterstützung
Freistehend und gehostet
Sprache
Standardbibliothek
Standardbibliothek-Header
Benannte Anforderungen
Feature-Test-Makros (C++20)
Sprachunterstützungsbibliothek
Konzeptbibliothek (C++20)
Diagnosebibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogrammbibliothek
Containerbibliothek
Iteratorenbibliothek
Bereichsbibliothek (C++20)
Algorithmenbibliothek
Zeichenkettenbibliothek
Textverarbeitungsbibliothek
Numerikbibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabebibliothek
Dateisystembibliothek (C++17)
Nebenläufigkeitsunterstützungsbibliothek (C++11)
Ausführungskontrollbibliothek (C++26)
Technische Spezifikationen
Symbolindex
Externe Bibliotheken

de.cppreference.net

Namespaces

Variants