std::set mit Benutzer-definierter Typ, wie um sicherzustellen, dass keine Duplikate

operator== ist nicht std::set. Elemente a und b als gleich betrachtet werden, iff !(a < b) && !(b < a)

InformationsquelleAutor Paul

rlbond der Komparator nicht verhindern, dass die Einfügung der Elemente, die im Vergleich gleich. Anscheinend ist es schwer zu beweisen, dies in den Kommentaren, angesichts der Zeichenbegrenzung, weil rlbond scheint denkt, dass std::set garantiert, dass es nie enthalten zwei Elemente mit !compare(a,b) && !compare(b,a) für seine Komparator. Allerdings rlbond der Komparator definiert nicht eine strenge Ordnung, und daher ist kein Gültiger parameter an std::set.

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

struct BrokenOrder {
    int order;
    int equality;

    public:
    BrokenOrder(int o, int e) : order(o), equality(e) {}

    bool operator<(const BrokenOrder &rhs) const {
        return order < rhs.order;
    }
    bool operator==(const BrokenOrder &rhs) const {
        return equality == rhs.equality;
    }
};

std::ostream &operator<<(std::ostream &stream, const BrokenOrder &b) {
    return stream << b.equality;
}

//rlbond's magic comparator
struct LessThan : public std::binary_function<BrokenOrder, BrokenOrder, bool> {
    bool operator()(const BrokenOrder& lhs, const BrokenOrder& rhs) const
    {
        return !(lhs == rhs) && (lhs < rhs);
    }
};

int main() {
    std::set<BrokenOrder,LessThan> s;
    for (int i = 0; i < 5; ++i) {
        s.insert(BrokenOrder(i,i));
    }
    for (int i = 0; i < 5; ++i) {
        s.insert(BrokenOrder(10-i,i));
    }
    std::copy(s.begin(), s.end(), 
        std::ostream_iterator<BrokenOrder>(std::cout, "\n"));
}

Ausgabe:

0
1
2
3
4
3
2
1
0

Duplikate. Die Magie Komparator ist fehlgeschlagen. Verschiedene Elemente im set haben den gleichen Wert equality, und damit zu vergleichen, das gleiche mit operator==, weil beim einführen der Satz nie Vergleich des neuen Elementes auf seinen duplizieren. Die einzige doppelte, die ausgeschlossen wurde, war 4, da die zwei 4 hatte Sortierreihenfolgen 4 und 6. Diese legte Sie nahe genug zusammen, in der festgelegt werden miteinander verglichen.

Aus der C++ - standard: 25.3:3 "Für die algorithmen korrekt arbeiten, comp hat zu veranlassen, eine strenge schwache Bestellung auf die Werte".

25.3:4 "... die Anforderungen sind, dass comp und equiv beide werden transitive Beziehungen:

comp(a,b) && comp(b,c) implies comp(a,c)"

Betrachten Sie nun die Elemente a = BrokenOrder(1,1), b = BrokenOrder(2,2), und c = BrokenOrder(9,1), und comp natürlich gleich die Magie Komparator. Dann:

• comp(a,b) ist wahr, da 1 != 2 (Gleichheit) und 1 < 2 (um)
• comp(b,c) ist wahr, da 2 != 1 (Gleichheit) und 2 < 9 (Reihenfolge)
• comp(a,c) ist falsch, da 1 == 1 (Gleichheit)

InformationsquelleAutor

Könnten Sie versuchen, etwas wie das folgende:

//! An element used in the route calculation.
struct RouteElem {
    int shortestToHere; //Shortest distance from the start.
    int heuristic;              //The heuristic estimate to the goal.
    Coordinate position;
    bool operator<( const RouteElem& other ) const
    {
      return (heuristic+shortestToHere) < (other.heuristic+other.shortestToHere);
    }
    bool operator==( const RouteElem& other ) const
    {
      return (position.x == other.position.x && position.y == other.position.y);
    }
};

struct CompareByPosition {
    bool operator()(const RouteElem &lhs, const RouteElem &rhs) {
        if (lhs.position.x != rhs.position.x) 
            return lhs.position.x < rhs.position.x;
        return lhs.position.y < rhs.position.y;
    }
};

//first, use std::set to remove duplicates
std::set<RouteElem,CompareByPosition> routeset;
//... add each RouteElem to the set ...

//now copy the RouteElems into a vector
std::vector<RouteElem> routevec(routeset.begin(), routeset.end());

//now sort via operator<
std::sort(routevec.begin(), routevec.end());

Ganz offensichtlich ist die Kopie in der Mitte, die sieht langsam. Aber jede Struktur, welche Indizes die Elemente von zwei verschiedenen Kriterien wird also eine Art extra-overhead pro Element verglichen mit einem Satz. Der ganze code oben ist O(n log n), vorausgesetzt, dass Ihre Implementierung von std::sort verwendet introsort.

Wenn Sie es haben, nach diesem Schema, die Sie nutzen könnten unordered_set statt set zu tun, die ersten uniqueifying. Da der hash würde nur davon abhängen, x und y, es sollte schneller sein als die O(log N) Vergleiche benötigt, um einfügen in eine Gruppe.

Edit: gerade bemerkt, dass Sie sagte, Sie wollte zu "halten" Sortierreihenfolge, nicht, dass Sie wollten Prozess alles in einer batch. Tut mir Leid, dass. Wenn Sie möchten, um effizient die Aufrechterhaltung der Ordnung und Duplikate ausschließen, während das hinzufügen von Elementen, dann würde ich empfehlen, mit der set-oder der ungeordnete, die ich oben definieren, basierend auf der position, und auch eine std::multiset<RouteElem>, die zur Aufrechterhaltung der operator< um. Für jedes neue element haben:

if (routeset.insert(elem).second) {
    routemultiset.insert(elem);
}

Obwohl Bedenken Sie, dass diese Angebote keine Ausnahme-Garantie. Wenn die zweite insert wirft, dann die routeset wurde so verändert, dass der Staat nicht mehr konsistent. Also ich denke wirklich du brauchst:

if (routeset.insert(elem).second) {
    try {
        routemultiset.insert(elem); //I assume strong exception guarantee
    } catch(...) {
        routeset.erase(elem); //I assume nothrow. Maybe should check those.
        throw;
    }
}

Oder ein äquivalent mit RAII, welches Ausführlicher ist, ob es nur eine Stelle im code, die Sie jemals verwenden Sie die RAII-Klasse, aber besser, wenn es viel Wiederholung.

InformationsquelleAutor Steve Jessop