Warum macht die Boost Graph Library beim Entfernen eines Scheitelpunkts alle Iteratoren ungültig?

-1

In der Boost Graph Library Dokumentation es says, dass, wenn Sie einen Eckpunkt aus einem Graphen entfernen (wenn seine Eckpunkte in einem Vektor mindestens gespeichert sind), alle Iteratoren (und Deskriptoren) ungültig sind.Warum macht die Boost Graph Library beim Entfernen eines Scheitelpunkts alle Iteratoren ungültig?

Dies überraschte mich, da es nicht semantisch notwendig scheint, dies zu tun.

Gibt es eine Möglichkeit, adjacency_list auf eine Weise arbeiten zu lassen, die Iteratoren in einem solchen Fall nicht aggressiv ungültig macht? Kann ich den Vertex nicht einfach "ungültig machen" und ihn zu einem passenden Zeitpunkt sammeln?

Quelle

2016-03-22 einpoklum

Sie wissen, dass das wegen des zugrunde liegenden Vektors passiert? Wenn Sie Elemente aus einem ['std :: vector'] (http://en.cppreference.com/w/cpp/container/vector) hinzufügen oder entfernen, werden möglicherweise alle Iteratoren ungültig gemacht. –

Ehrlich gesagt, liest sich Ihre Frage wie eine unkonstruktive Tirade. Ich kann es für Sie bearbeiten, aber vielleicht möchten Sie dies tun. – sehe

@sehe: Besser? Wenn nicht, können Sie es bearbeiten. – einpoklum

Es ist nur die zugrunde liegenden Container Semantik: Iterator invalidation rules

Es ist auch eindeutig ein Trade-off: Sie O erhalten (1) Vertex Indizierung kostenlos.

Wenn Sie etwas anderes möchten, verwenden Sie einen anderen Container-Selektor (z. B. listS) für den Vertex-Container.

Ist es nicht (im Allgemeinen) besser, nur den Scheitelpunkt im Vektor zu "entwerten" und ihn zu sammeln, wenn die nächste Größenänderung erforderlich ist?

Es ist in der Tat ein gemeinsames Muster, um Vertices als gelöscht zu markieren. boost::filtered_graph<> ist ein praktischer Adapter für solche Fälle.

Quelle

2016-03-22 09:22:01 sehe

1. Eine andere Design-Wahl als nur das Entfernen des Containers an den Container hätte mir den Trade-off erspart. 2. Ich nehme an, dass ein "filtered_graph" eine "gelöschte" boolesche Eigenschaft zu jedem Eckpunkt (oder Kante oder beiden) hinzufügt und die Entfernungsoperationen überschreibt? – einpoklum

Es hätte dir offensichtlich einen weiteren, ebenso willkürlichen, Kompromiss gebracht. Gefilterte Grafik filtert nur. Kein Überschreiben erfolgt. Sie "löschen" logisch Eckpunkte, indem Sie sie zum gefilterten Satz hinzufügen. Ich (und einige andere) haben Antworten auf SO, die das zeigen. – sehe

Warum macht die Boost Graph Library beim Entfernen eines Scheitelpunkts alle Iteratoren ungültig?

Antwort

Verwandte Themen