Algorithmus zum vertauschen von Ranges gesucht
-
ALso, das ist mein Problem:
ich habe einen std::vector, der wie folgt aufgebaut ist:
|start....|range1|........range2......|range3|....end|und ich muss range1 und range3 im vector tauschen, ohne die Reihenfolge der Elemente von range2 zu verändern. Klingt zuerst wie eine Aufgabe für std::swap_ranges. Aber leider haben range1 und range3 eine unterschiedliche Größe.
Ich dachte, dass das eigentlich ein Standardproblem sein muss, finde aber leider keinen Algorithmus in der Standardbibliothek. Ich würde nur ungern auf vector::insert und vector::erase ausweichen, da ich gerne vermeiden würde, dass a) neuallokiert und b) alle Elemente verschoben werden.Mein Ansatz momentan ist, dass ich zuerst swap_ranges verwende um min(range1.size(),range3.size()) elemente von range1 und range3 zu swappen. Dann wäre ich im Folgenden in diesem Spezialfall (angenommen range3.size()<range2.size()):
|start....|range1|range2|....end|Das heißt range 3 ist leer und ich muss die elemente von range1 und range2 austauschen.
auch hier dachte ich, dass das eigentlich ein Standardproblem sein müsste. Hier bin ich nun aber überfragt, wie man das effizient machen könnte. Jemand eine Idee? :). Für den Fall range2.size()>range1.size() hätte ich spontan swap_ranges verwendet und solange range1 nach rechts verschoben, bis ich in dem Fall bin, dass der Rest von range2 kleiner ist als range1. Ich könnte nun anfangen range2 von rechts nach links zu verschieben, und das so lange machen, bis alle Elemente an ihrem Platz sind...aber irgendwie klingt das nicht sonderlich effizient.Irgendwelche Ideen?
-
alle Elemente verschoben werden
Wie soll das denn bei einem std::vector verhindert werden. Benutze std::list oder eben eine Indexmenge.
-
ABBCCCD
jetzt ein swap von B und C führt zu der blöden Situation:
ACCBBCD
wie soll das letzte C nun ohne probleme an die korrekte stelle kommen?Was man in solchen Situationen manchmal macht ist folgendes:
du erstellst einen vector mit alle indices aus dem 1. vector:
1234567
und dann swapst du die ranges mit kopieren und einfügen, wie man es eben normal machen würde - da du aber nur ints hast, ist der aufwand trivial.
dann hast du
1456237
als ergebnis und nun einfach durchswapen im echten vector.alternativ kannst du dir auch ein move_range schreiben, das per swap Elemente verschiebt - bedeutet halt sehr viele swaps, mag aber effizient sein wenn du sehr große vectoren hast.
-
Shade Of Mine schrieb:
ABBCCCD
jetzt ein swap von B und C führt zu der blöden Situation:
ACCBBCD
wie soll das letzte C nun ohne probleme an die korrekte stelle kommen?genau an dem Punkt war ich auch. In dem Fall könntest du C rückwärts tauschen:
ACCBBCD -> ACCBCBD -> ACCCBBD
Aber du hast recht: auch nach diesem Tausch könnte ich wieder in dieselbe Situation kommen. Das heißt irgendwann sollte ich vielleicht doch ein Array auf dem Stack anlegen und den als Zwischenspeicher verwenden.
@knivil: das ich alle Elemente zwischen range und range3 verschieben muss, ist mir klar. Aber der vector ist viel Größer. Das Ding speichert die Einträge einer sparse-matrix im CSR Format und ich muss in dieser Matrix Zeilen tauschen.
-
Verstehe grad das Problem nicht.
Nach dem Tauschen desmin(range1.size(),range3.size())Bereichs bleibt bloss noch ein Bereich übrig der um N Plätze nach links oder rechts rotiert werden muss.
Was sich halbwegs einfach und performant "in place" bewerkstelligen lässt:
http://leetcode.com/2010/04/rotating-array-in-place.html
