Divide & Conquer mittels Vectoren/Iteratoren
-
Hallo allerseits!
Ich schlage mich hier gerade mit einem kleinen Problem herrum, vielleicht kann mir ja jemand helfen...
(Ich verzichte mal auf großartigen Quellcode, eine verbale Beschreibung ist wahrscheinlich verständlicher.)
Ich habe eine Klasse "MyVariable" geschrieben, und diese hat als Attribut unter anderem eine "ID" (int-Wert). Nun möchte ich mehrere Instanzen dieser Klasse in einem vector<MyVariable*> unterbringen, und zwar sortiert nach den IDs.
Angenommen ich habe schon einen Vektor mit einigen Elementen und möchte ein neues einsortieren. Mittels "Divide&Conquer" wäre das ja eine flotte Sache mit log. Laufzeit, also immer mit dem mittleren Element vergleichen usw.
Prima, dachte ich mir, mittels []-Operator komme ich ans mittlere Element, aber oh Schreck, zum Einfügen brauche ich ja einen Iterator! Ok, kein Problem, an einen Iterator ist ja ranzukommen... obwohl, wie erhalte ich denn nun einen Iterator auf das mittlere Vektor-Element?
Ich bin da gerade etwas verwirrt und komme nicht so recht weiter (habe das Ganze nun vorerst mit linearer Suche implementiert).
Für jegliche Hilfe wäre ich sehr dankbar! Ich komme eher so aus der Java-Ecke, daher habe ich mit den C++-Klassen noch nicht so viel Erfahrung.
Viele Grüße,
Baumbart
-
wenn man ein element n haben will haben will, kann man auch begin()+n schreiben
-
wenn du die IDs selber vergeben darfst, mach sie doch so, daß sie gute array-indizes sind.
wenn nicht, dann haste zwei aufdringliche möglichkeiten:
a) es gibt selten änderungen am datenbestand aber viele suchen: nimm ein sortiertes array, suche aber erst gar nicht mit binary search, denn für das einfügen brauchste eh durchschnittliche n/2 schiebungen, sondern setzt dein neues elemet hinen dran und tausche es so lange nach vorne, bis es nicht mehr größer als sein vorgänger ist oder bis es das erste ist.
b) änderungen sind nicht selten: nimm gleich nen baum. also std::map.
(hashtables schlage ich nicht vor.)
-
Hallo nochmal!
Danke für die rasche und gute Hilfe! Der Hinweis mit "begin()+n" war genau das, was ich gesucht habe, aber ich werde auch noch mal die anderen Tipps überdenken und durcharbeiten.
Viele Grüße,
Baumbart