Wie können (einige) Elemente effizient von einer std :: map auf eine andere verschoben werden?

8

Ich habe zwei std::map<>Objekte aund bmöchte einige Elemente (Knoten) basierend auf einem Prädikat von einer Karte zur anderen verschieben ( extract+ insert) p.

for (auto i = a.begin(); i != a.end(); ++i)
    if (p(*i))
        b.insert(a.extract(i))

Dieser Code ist in clang fehlerhaft. Ich gehe davon aus, dass das Problem das Inkrement ist, inachdem sein Knoten aus a extrahiert wurde.

Ist dies der richtige / einzige Weg, um dies mithilfe eines Post-Inkrements zu beheben? ZB:

for (auto i = a.begin(); i != a.end();)
    if (p(*i))
        b.insert(a.extract(i++))
    else
        ++i;

BEARBEITEN : Ich habe den Teil über "Warum funktioniert das in gcc?" Entfernt, da ich dies in meinem aktuellen Setup nicht reproduzieren kann. Ich bin überzeugt, dass es irgendwann einmal war, aber mit gcc 9.2.1 bekomme ich einen Deadlock (anstelle eines Segfault). In beiden Fällen extract()funktioniert das Inkrementieren nach nicht.

Axxel
quelle
3
@Eljay Meiner Meinung nach ist die neue Spleiß-API für Map- Node-Handle in C ++ 17 ausreichend spezialisiert, um eine eigene Frage zu rechtfertigen. Ich hoffe, dass dies nicht als Duplikat geschlossen wird.
NicholasM
Mögliches Duplikat des Löschens von Elementen aus std :: set während der Iteration . std::setund std::mapsind sehr ähnlich, und soweit ich das beurteilen kann, extracthat dies die gleichen Auswirkungen auf die Ungültigmachung wie erase.
François Andrieux
Welche Version von clang und gcc hast du benutzt? Für mich führt die Verwendung von clang 8.0 und gcc 7.4 zu einem Segfault.
Balázs Kovacsics
Ich bin überrascht, dass dieser Code in jedem Compiler funktionieren würde. Sie behandeln nicht die durch Extrakt verursachte Ungültigmachung
Iman Kianrostami

Antworten:

6

Ich gehe davon aus, dass das Problem das Inkrement von i ist, nachdem der Knoten aus a extrahiert wurde.

Tatsächlich. Die Extraktion macht Iteratoren für das extrahierte Element ungültig und iist ein solcher Iterator. Das Verhalten des Inkrementierens oder Indirektierens durch einen ungültigen Iterator ist undefiniert.

Warum funktioniert das scheinbar in gcc, aber nicht in clang?

Weil das Verhalten des Programms undefiniert ist.

Ist der richtige / einzige Weg, dies mit einem Post-Inkrement zu beheben?

Es ist ein richtiger Weg, dies zu beheben. Es ist kein besonders schlechter Weg. Wenn Sie das Inkrement nicht wiederholen möchten, verwenden Sie eine Variable:

for (auto i = a.begin(); i != a.end();) {
    auto current = i++;
    if (p(*current)) {
        // moving is probably unnecessary
        b.insert(a.extract(std::move(current)));
    }
}
Eerorika
quelle
Dies ist eine gute Möglichkeit, (vernünftigerweise) davon auszugehen, dass das Kopieren des Iteratorstatus kostengünstiger ist als das Kopieren des Knotens.
Spencer
@Spencer Das Kopieren eines Iterators ist normalerweise trivial. Aber ich habe für alle Fälle einen Zug hinzugefügt.
Eerorika
@Spencer currentwürde in einem verschobenen Zustand belassen. Was auch immer dieser Zustand ist, spielt keine Rolle, da er danach nicht mehr verwendet wird.
Eerorika
@eeroika Danke, ich habe mir deinen Code etwas genauer angesehen und festgestellt, dass.
Spencer
Ich mag Ihre lokale Variable besser als zwei icrements, aber ich würde eine kleine Verbesserung vorschlagen: Begrenzen Sie den Umfang currentdurch die Verwendung der C ++ 17s- if (auto current = ++i; p(*current))Syntax.
Axxel