std::adjacent_find

Definiert in Header `<algorithm>`
template< class ForwardIt > ForwardIt adjacent_find( ForwardIt first, ForwardIt last );	(1)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last );	(2)	(seit C++17)
template< class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ForwardIt first, ForwardIt last, BinaryPred p );	(3)	(constexpr seit C++20)
template< class ExecutionPolicy, class ForwardIt, class BinaryPred > ForwardIt adjacent_find( ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, BinaryPred p );	(4)	(seit C++17)

Durchsucht den Bereich [first, last) nach zwei aufeinanderfolgenden gleichen Elementen.

1) Elemente werden mit operator== verglichen.

3) Elemente werden mit dem gegebenen binären Prädikat p verglichen.

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

Diese Überladungen nehmen an der Auflösungsauflösung teil, nur wenn alle folgenden Bedingungen erfüllt sind

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true.	(bis C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true.	(seit C++20)

[bearbeiten] Parameter

first, last	-	das Iteratorenpaar, das den Bereich der zu untersuchenden Elemente definiert
policy	-	die Ausführungsrichtlinie, die verwendet werden soll
p	-	binäre Prädikatfunktion, die true zurückgibt, wenn die Elemente als gleich behandelt werden sollen. Die Signatur der Prädikatfunktion sollte äquivalent zur folgenden sein: bool pred(const Type1 &a, const Type2 &b); Obwohl die Signatur nicht zwingend const & haben muss, darf die Funktion die ihr übergebenen Objekte nicht modifizieren und muss alle Werte vom Typ (möglicherweise const) `Type1` und `Type2` unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt, ebenso wenig wie Type1, es sei denn, für `Type1` ist eine Verschiebung gleichbedeutend mit einer Kopie(seit C++11)). Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt des Typs ForwardIt dereferenziert und dann implizit in beide konvertiert werden kann.
Typanforderungen
- `ForwardIt` muss die Anforderungen von LegacyForwardIterator erfüllen.
- `BinaryPred` muss die Anforderungen an BinaryPredicate erfüllen.

[bearbeiten] Rückgabewert

Ein Iterator auf das erste des ersten Paares identischer Elemente, d.h. der erste Iterator it, für den *it == *(it + 1) für (1,2) oder p(*it, *(it + 1)) != false für (3,4) gilt.

Wenn keine solchen Elemente gefunden werden, wird last zurückgegeben.

[bearbeiten] Komplexität

Gegeben result als Rückgabewert von adjacent_find, $\scriptsize M$ $M$ als std::distance(first, result) und $\scriptsize N$ $N$ als std::distance(first, last)

1) Genau

min(M+1,N-1)

Vergleiche mit operator==.

2)

O(N)

Vergleiche mit operator==.

3) Genau

min(M+1,N-1)

Aufrufe des Prädikats p.

4)

O(N)

Aufrufe des Prädikats p.

[bearbeiten] Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten 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 jede andere ExecutionPolicy ist das Verhalten implementierungsabhängig.
Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.

[bearbeiten] Mögliche Implementierung

adjacent_find (1)

template<class ForwardIt>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return last;
 
    ForwardIt next = first;
    ++next;
 
    for (; next != last; ++next, ++first)
        if (*first == *next)
            return first;
 
    return last;
}

adjacent_find (3)

template<class ForwardIt, class BinaryPred>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last, BinaryPred p)
{
    if (first == last)
        return last;
 
    ForwardIt next = first;
    ++next;
 
    for (; next != last; ++next, ++first)
        if (p(*first, *next))
            return first;
 
    return last;
}

[bearbeiten] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};
 
    auto i1 = std::adjacent_find(v1.begin(), v1.end());
 
    if (i1 == v1.end())
        std::cout << "No matching adjacent elements\n";
    else
        std::cout << "The first adjacent pair of equal elements is at "
                  << std::distance(v1.begin(), i1) << ", *i1 = "
                  << *i1 << '\n';
 
    auto i2 = std::adjacent_find(v1.begin(), v1.end(), std::greater<int>());
    if (i2 == v1.end())
        std::cout << "The entire vector is sorted in ascending order\n";
    else
        std::cout << "The last element in the non-decreasing subsequence is at "
                  << std::distance(v1.begin(), i2) << ", *i2 = " << *i2 << '\n';
}

Ausgabe

The first adjacent pair of equal elements is at 4, *i1 = 40
The last element in the non-decreasing subsequence is at 7, *i2 = 41

[bearbeiten] Fehlerberichte

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

DR	angewendet auf	Verhalten wie veröffentlicht	Korrigiertes Verhalten
LWG 240	C++98	das Prädikat wurde std::find (first, last, value) - first mal angewendet für (1,3), wobei value niemals definiert wurde	angewendet std::min( (result - first) + 1, (last - first) - 1) mal

[bearbeiten] Siehe auch

unique	Entfernt aufeinanderfolgende doppelte Elemente in einem Bereich (Funktionstemplate) [edit]
ranges::adjacent_find (C++20)	Findet die ersten beiden benachbarten Elemente, die gleich sind (oder eine gegebene Bedingung erfüllen) (Algorithmus-Funktionsobjekt)[edit]

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Header der Standardbibliothek
Benannte Anforderungen
Feature-Test-Makros (C++20)
Bibliothek für Sprachunterstützung
Konzepte-Bibliothek (C++20)
Diagnostik-Bibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogramme-Bibliothek
Container-Bibliothek
Iterator-Bibliothek
Ranges-Bibliothek (C++20)
Algorithmen-Bibliothek
Bibliothek für Zeichenketten
Textverarbeitungsbibliothek
Numerik-Bibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabe-Bibliothek
Dateisystembibliothek (C++17)
Unterstützung für nebenläufige Programmierung (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolverzeichnis
Externe Bibliotheken

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen