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) |
Überprüft, ob [first1, last1) eine Permutation eines Bereichs ist, der bei first2 beginnt:
- Für die Überladungen (1,2) hat der zweite Bereich
std::distance(first1, last1)Elemente. - Für die Überladungen (3,4) ist der zweite Bereich
[first2,last2).
operator== verglichen.p verglichen.Wenn ForwardIt1 und ForwardIt2 unterschiedliche Werttypen haben, ist das Programm fehlerhaft.
Wenn die Vergleichsfunktion keine Äquivalenzrelation ist, ist das Verhalten undefiniert.
Parameter
| first1, last1 | - | das Paar der Iteratoren, das den ersten Bereich der zu vergleichenden Elemente definiert |
| first2, last2 | - | das Paar der Iteratoren, das den zweiten Bereich der zu vergleichenden Elemente definiert |
| p | - | binäres Prädikat, das true zurückgibt, wenn die Elemente als gleich behandelt werden sollen. Die Signatur der Prädikatfunktion sollte der folgenden entsprechen:
Während die Signatur nicht |
| Typanforderungen | ||
-ForwardIt1, ForwardIt2 muss die Anforderungen von LegacyForwardIterator erfüllen.
| ||
Rückgabewert
true wenn der Bereich [first1, last1) eine Permutation des Bereichs [first2, last2) ist, false andernfalls.
Komplexität
Gegeben N als std::distance(first1, last1):
operator== wenn die beiden Bereiche gleich sind, andernfalls O(N2) Vergleiche im schlechtesten Fall.
p wenn die beiden Bereiche gleich sind, andernfalls O(N2) Anwendungen im schlechtesten Fall.
ForwardIt1 und ForwardIt2 beide LegacyRandomAccessIterator sind und last1 - first1 != last2 - first2 ist true, werden keine Vergleiche durchgeführt.operator== wenn die beiden Bereiche gleich sind, andernfalls O(N2) Vergleiche im schlechtesten Fall.
p wenn die beiden Bereiche gleich sind, andernfalls O(N2) Anwendungen im schlechtesten Fall.
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;
}
|
Hinweis
Die std::is_permutation kann beim Testen verwendet werden, nämlich zur Überprüfung der Korrektheit von umordnenden Algorithmen (z. B. Sortieren, Mischen, Partitionieren). Wenn x ein ursprünglicher Bereich ist und y ein permutierter Bereich, dann bedeutet std::is_permutation(x, y) == true, dass y aus "denselben" Elementen besteht, möglicherweise an anderen Positionen.
Beispiel
#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
Siehe auch
| erzeugt die nächstgrößere lexikografische Permutation eines Bereichs von Elementen (Funktionsschablone & Algorithmusfunktionsobjekt) | |
(C++20) |
|
| erzeugt die vorherige kleinere lexikografische Permutation eines Bereichs von Elementen (Funktionsschablone & Algorithmusfunktionsobjekt) | |
(C++20) |
|
(C++20) |
spezifiziert, dass eine Relation eine Äquivalenzrelation auferlegt (Konzept) |
(C++20) |
bestimmt, ob eine Sequenz eine Permutation einer anderen Sequenz ist (Algorithmusfunktionsobjekt) |