std::ranges::unique
| Definiert in Header <algorithm> |
||
| Aufruf-Signatur |
||
| template< std::permutable I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_equivalence_relation<std::projected<I, Proj>> |
(1) | (seit C++20) |
| template< ranges::forward_range R, class Proj = std::identity, std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>> |
(2) | (seit C++20) |
[first, last) und gibt einen Unterbereich [ret, last) zurück, wobei ret ein past-the-end Iterator für das neue Ende des Bereichs ist.*(i - 1) und *i werden als äquivalent betrachtet, wenn std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true, wobei i ein Iterator im Bereich [first + 1, last) ist.r als Bereich, so als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.
- Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
- Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
- Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.
Inhalt |
[bearbeiten] Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der zu verarbeitenden Elemente definiert |
| r | - | der Bereich der zu verarbeitenden Elemente |
| comp | - | das binäre Prädikat zum Vergleichen der projizierten Elemente |
| proj | - | die Projektion, die auf die Elemente angewendet werden soll |
[bearbeiten] Rückgabewert
Gibt {ret, last} zurück, wobei ret ein past-the-end Iterator für das neue Ende des Bereichs ist.
[bearbeiten] Komplexität
Für nicht-leere Bereiche, genau ranges::distance(first, last) - 1 Anwendungen des entsprechenden Prädikats comp und nicht mehr als doppelt so viele Anwendungen einer Projektion proj.
[bearbeiten] Anmerkungen
Die Entfernung erfolgt durch Verschieben (mittels Zuweisung durch Verschieben) der Elemente im Bereich so, dass die nicht zu entfernenden Elemente am Anfang des Bereichs erscheinen. Die relative Reihenfolge der verbleibenden Elemente bleibt erhalten und die *physische* Größe des Containers ändert sich nicht. Iteratoren in [ret, last) (falls vorhanden) sind immer noch dereferenzierbar, aber die Elemente selbst haben unspezifizierte Werte (gemäß den Post-Bedingungen von MoveAssignable).
Ein Aufruf von ranges::unique wird manchmal von einem Aufruf der erase-Memberfunktion eines Containers gefolgt, der die unspezifizierten Werte löscht und die *physische* Größe des Containers auf seine neue *logische* Größe reduziert. Diese beiden Aufrufe zusammen modellieren das Erase–remove-Idiom.
[bearbeiten] Mögliche Implementierung
struct unique_fn { template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity, std::indirect_equivalence_relation<std::projected<I, Proj>> C = ranges::equal_to> constexpr ranges::subrange<I> operator()(I first, S last, C comp = {}, Proj proj = {}) const { first = ranges::adjacent_find(first, last, comp, proj); if (first == last) return {first, first}; auto i {first}; ++first; while (++first != last) if (!std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *first))) *++i = ranges::iter_move(first); return {++i, first}; } template<ranges::forward_range R, class Proj = std::identity, std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>> C = ranges::equal_to> requires std::permutable<ranges::iterator_t<R>> constexpr ranges::borrowed_subrange_t<R> operator()(R&& r, C comp = {}, Proj proj = {}) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr unique_fn unique {}; |
[bearbeiten] Beispiel
#include <algorithm> #include <cmath> #include <complex> #include <iostream> #include <vector> struct id { int i; explicit id(int i) : i {i} {} }; void print(id i, const auto& v) { std::cout << i.i << ") "; std::ranges::for_each(v, [](auto const& e) { std::cout << e << ' '; }); std::cout << '\n'; } int main() { // a vector containing several duplicated elements std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4}; print(id {1}, v); // remove consecutive (adjacent) duplicates const auto ret = std::ranges::unique(v); // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate v.erase(ret.begin(), ret.end()); print(id {2}, v); // sort followed by unique, to remove all duplicates std::ranges::sort(v); // {1 1 2 3 4 4 5} print(id {3}, v); const auto [first, last] = std::ranges::unique(v.begin(), v.end()); // v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate v.erase(first, last); print(id {4}, v); // unique with custom comparison and projection std::vector<std::complex<int>> vc { {1, 1}, {-1, 2}, {-2, 3}, {2, 4}, {-3, 5} }; print(id {5}, vc); const auto ret2 = std::ranges::unique(vc, // consider two complex nums equal if their real parts are equal by module: [](int x, int y) { return std::abs(x) == std::abs(y); }, // comp [](std::complex<int> z) { return z.real(); } // proj ); vc.erase(ret2.begin(), ret2.end()); print(id {6}, vc); }
Ausgabe
1) 1 2 1 1 3 3 3 4 5 4 2) 1 2 1 3 4 5 4 3) 1 1 2 3 4 4 5 4) 1 2 3 4 5 5) (1,1) (-1,2) (-2,3) (2,4) (-3,5) 6) (1,1) (-2,3) (-3,5)
[bearbeiten] Siehe auch
| (C++20) |
Erstellt eine Kopie eines Bereichs von Elementen, die keine aufeinanderfolgenden Duplikate enthält (Algorithmus-Funktionsobjekt) |
| (C++20) |
Findet die ersten beiden benachbarten Elemente, die gleich sind (oder eine gegebene Bedingung erfüllen) (Algorithmus-Funktionsobjekt) |
| (C++20)(C++20) |
entfernt Elemente, die bestimmte Kriterien erfüllen (Algorithmus-Funktionsobjekt) |
| Entfernt aufeinanderfolgende doppelte Elemente in einem Bereich (Funktionstemplate) | |
| entfernt aufeinanderfolgende doppelte Elemente (öffentliche Memberfunktion von std::list<T,Allocator>) | |
| entfernt aufeinanderfolgende doppelte Elemente (öffentliche Memberfunktion von std::forward_list<T,Allocator>) |
