std::is_permutation

Definiert in Header `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2 );	(1)	(seit C++11) (constexpr seit C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, BinaryPredicate p );	(2)	(seit C++11) (constexpr seit C++20)
template< class ForwardIt1, class ForwardIt2 > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(seit C++14) (constexpr seit C++20)
template< class ForwardIt1, class ForwardIt2, class BinaryPredicate > bool is_permutation( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPredicate p );	(4)	(seit C++14) (constexpr seit C++20)

Prüft, ob [first1, last1) eine Permutation eines von first2 ausgehenden Bereichs ist.

Für Überladungen (1,2) hat der zweite Bereich std::distance(first1, last1) Elemente.
Für Überladungen (3,4) ist der zweite Bereich [first2, last2).

1,3) Elemente werden mit operator== verglichen.

2,4) Elemente werden mit der angegebenen binären Prädikatfunktion p verglichen.

Wenn ForwardIt1 und ForwardIt2 unterschiedliche Werttypen haben, ist das Programm ill-formed.

Wenn die Vergleichsfunktion keine Äquivalenzrelation ist, ist das Verhalten undefiniert.

[edit] Parameter

first1, last1	-	das Iteratorenpaar, das den ersten Bereich der zu vergleichenden Elemente definiert.
first2, last2	-	das Iteratorenpaar, das den zweiten Bereich der zu vergleichenden Elemente definiert.
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 Objekte der Typen InputIt1 und InputIt2 dereferenziert und dann implizit in Type1 bzw. Type2 konvertiert werden können.
Typanforderungen
- `ForwardIt1, ForwardIt2` müssen die Anforderungen an LegacyForwardIterator erfüllen.

[edit] Rückgabewert

true, wenn der Bereich [first1, last1) eine Permutation des Bereichs [first2, last2) ist, andernfalls false.

[edit] Komplexität

Sei $\scriptsize N$ $N$ als std::distance(first1, last1)

1) Genau

N

Vergleiche mit operator==, wenn die beiden Bereiche gleich sind, andernfalls

O(N 2)

Vergleiche im Worst Case.

2) Genau

N

Aufrufe des Prädikats p, wenn die beiden Bereiche gleich sind, andernfalls

O(N 2)

Aufrufe im Worst Case.

3,4) Wenn ForwardIt1 und ForwardIt2 beide LegacyRandomAccessIterator sind und last1 - first1 != last2 - first2 true ist, werden keine Vergleiche durchgeführt.

Andernfalls

3) Genau

N

Vergleiche mit operator==, wenn die beiden Bereiche gleich sind, andernfalls

O(N 2)

Vergleiche im Worst Case.

4) Genau

N

Aufrufe des Prädikats p, wenn die beiden Bereiche gleich sind, andernfalls

O(N 2)

Aufrufe im Worst Case.

[edit] Mögliche Implementierung

template<class ForwardIt1, class ForwardIt2>
bool is_permutation(ForwardIt1 first, ForwardIt1 last,
                    ForwardIt2 d_first)
{
    // skip common prefix
    std::tie(first, d_first) = std::mismatch(first, last, d_first);
 
    // iterate over the rest, counting how many times each element
    // from [first, last) appears in [d_first, d_last)
    if (first != last)
    {
        ForwardIt2 d_last = std::next(d_first, std::distance(first, last));
        for (ForwardIt1 i = first; i != last; ++i)
        {
            if (i != std::find(first, i, *i))
                continue; // this *i has been checked
 
            auto m = std::count(d_first, d_last, *i);
            if (m == 0 || std::count(i, last, *i) != m)
                return false;
        }
    }
    return true;
}

[edit] Hinweis

std::is_permutation kann im Testing verwendet werden, insbesondere um die Korrektheit von neu arrangierenden Algorithmen (z. B. Sortieren, Mischen, Partitionieren) zu überprüfen. Wenn x ein ursprünglicher Bereich und y ein permutierter Bereich ist, dann bedeutet std::is_permutation(x, y) == true, dass y aus "denselben" Elementen besteht, möglicherweise an anderen Positionen.

[edit] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
 
template<typename Os, typename V>
Os& operator<<(Os& os, const V& v)
{
    os << "{ ";
    for (const auto& e : v)
        os << e << ' ';
    return os << '}';
}
 
int main()
{
    static constexpr auto v1 = {1, 2, 3, 4, 5};
    static constexpr auto v2 = {3, 5, 4, 1, 2};
    static constexpr auto v3 = {3, 5, 4, 1, 1};
 
    std::cout << v2 << " is a permutation of " << v1 << ": " << std::boolalpha
              << std::is_permutation(v1.begin(), v1.end(), v2.begin()) << '\n'
              << v3 << " is a permutation of " << v1 << ": "
              << std::is_permutation(v1.begin(), v1.end(), v3.begin()) << '\n';
}

Ausgabe

{ 3 5 4 1 2 } is a permutation of { 1 2 3 4 5 }: true
{ 3 5 4 1 1 } is a permutation of { 1 2 3 4 5 }: false

[edit] Siehe auch

next_permutation	erzeugt die nächstgrößere lexikographische Permutation eines Bereichs von Elementen (Funktionsvorlage) [editieren]
prev_permutation	erzeugt die nächstkleinere lexikographische Permutation eines Bereichs von Elementen (Funktionsvorlage) [editieren]
equivalence_relation (C++20)	gibt an, dass eine `Relation` eine Äquivalenzrelation darstellt (Konzept) [bearbeiten]
ranges::is_permutation (C++20)	bestimmt, ob eine Sequenz eine Permutation einer anderen Sequenz ist (Algorithmus-Funktionsobjekt)[bearbeiten]

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