std::ranges:: unique

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:

• Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
• Keiner von ihnen ist sichtbar für argument-dependent lookup .
• Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup unterdrückt.

Parameter

Rückgabewert

Gibt { ret, last } zurück, wobei ret ein Past-the-End-Iterator für das neue Ende des Bereichs ist.

Komplexität

Für nichtleere Bereiche genau ranges:: distance ( first, last ) - 1 Anwendungen des entsprechenden Prädikats comp und nicht mehr als doppelt so viele Anwendungen jeglicher Projektion proj .

Hinweise

Das Entfernen erfolgt durch Verschieben (mittels Verschiebezuweisung) der Elemente im Bereich in einer Weise, 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 bleibt unverändert. Iteratoren im Bereich [ ret , last ) (falls vorhanden) sind weiterhin dereferenzierbar, aber die Elemente selbst haben unspezifizierte Werte (gemäß der MoveAssignable Nachbedingung).

Ein Aufruf von ranges::unique wird manchmal gefolgt von einem Aufruf der erase -Memberfunktion eines Containers, welche die unspezifizierten Werte löscht und die physische Größe des Containers reduziert, um seiner neuen logischen Größe zu entsprechen. Diese beiden Aufrufe modellieren zusammen das Erase–remove Idiom .

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

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()
{
    // ein Vektor mit mehreren duplizierten Elementen
    std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
    print(id {1}, v);
    // entferne aufeinanderfolgende (benachbarte) Duplikate
    const auto ret = std::ranges::unique(v);
    // v enthält nun {1 2 1 3 4 5 4 x x x}, wobei 'x' undefiniert ist
    v.erase(ret.begin(), ret.end());
    print(id {2}, v);
    // sortieren gefolgt von unique, um alle Duplikate zu entfernen
    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 enthält nun {1 2 3 4 5 x x}, wobei 'x' undefiniert ist
    v.erase(first, last);
    print(id {4}, v);
    // unique mit benutzerdefiniertem Vergleich und Projektion
    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,
        // betrachte zwei komplexe Zahlen als gleich, wenn ihre Realteile im Modul gleich sind:
        [](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);
}

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)

Siehe auch