3. vector verketten

vector verketten

  • D

    Hi,

    ich hab hier ein Programm, bei dem ich einen vector an einen anderen hängen muss

    Gibt es da eine bestimmte Funktion (ich hab bisher nichts gefunden) oder muss man das wirklich elementweise machen. Also so:

    vector<int>::const_iterator it;
for (it = v2.begin(); it != v2.end(); ++it)
  v1.push_back(*it);

    Geht das nicht irgendwie besser. Mir kommt es da vor allem auf Geschwindigkeit an. Oder ist es vielleicht noch besser, sich selber ne Klasse für verkettete Listen zu schreiben, wenn man so Sachen wie den Indexzugriff nicht braucht??

    Wie gesagt, es geht natürlich auch so, wie ich es oben geschrieben habe, nur ist mir die Geschwindigkeit wichtig...

    Vielen Dank im Voraus

    0
  • .

    Deinen Code kannst du auf jeden Fall noch beschleunigen:

    #include <algorithm>
#include <iterator>
//...
v1.reserve (v1.size () + v2.size ());
std::copy (v2.begin (), v2.end (), std::inserter (v1, v1.end ()));

    Außerdem kann dein Code u.U. kaputt gehen, wenn der vector neuen Speicherplatz reservieren muss, dann werden nämlich sämtliche Iteratoren ungültig!

    P.S.: verkettete Listen sind im Header <list> (list ist doppelt, slist einfach verkettet)

    0
  • ?

    Ich kenne nur:

    vInt1.insert(vInt1.end(), vInt2.begin(), vInt2.end());

    Keine Ahnung ob der das vielleicht auch nur elementweise macht??

    0
  • ?

    .filmor schrieb:

    dann werden nämlich sämtliche Iteratoren ungültig

    Aber doch nicht die von einem anderen vector, oder?

    0
  • .

    Jaja, hatte mich vertan 🙄

    0
  • D

    also ich hab insert mal ausprobiert, scheint aber ein bischen langsamer zu sein.
    Wenn ich list statt vector nehme, ist mein Programm ein ganzen Stück langsamer, was aber nicht an diesem anhängen liegt, sondern an anderer Stelle...

    @filmor: slist kennt mein Compiler nicht. Und es sagt mir ehrlich gesagt auch nichts...

    0
  • .

    Is auch in <slist> und nicht in <list> (siehe http://www.sgi.com/tech/stl/Slist.html).
    insert ist bei vector immer lahm gegenüber push_back (auch wenn es afaik am Ende ~gleich sein sollte).
    Wichtig ist auf jeden Fall, dass du, wenn du vector verwendest, das Vergrößern vorher durchführst, da diese Operation sonst möglicherweise mehrmals erfolgen muss.

    0
  • F

    Im Grunde ist ne Liste da perfekt.

    int array[] = {1,2,3,4,5,6,7,8,9,0};

std::list<int> a(array, array + sizeof(array)), b;
b.splice(b.end(), a);

    Gruß

    0
  • D

    wenn ich

    #include <slist>

    schreibe, bekomm ich aber einen Fehler, da er die Datei nicht kennt... Naja, ich bleib sowieso beim vector...

    das mit dem reserve hab ich jetzt gemacht, scheint auch ein wenig zu helfen...

    Vielen Dank erstmal für die Antworten

    0
  • D

    @FireFlow: kann es denn sein, dass ne Liste etwas langsamer als ein vector ist?? Im Prinzip könnte ich ja auch ne Liste nehmen, da ich ja nicht auf spezielle Elemente per Index zugreifen muss, aber irgendwie war mein Programm immer ein ganzes Stück langsamer, wenn ich list benutzt habe

    0
  • .

    Was machst du denn sonst so mit dem Ding?
    Der Vektor ist eigentlich immer schneller, es sei denn, er muss neuen Speicher alloziieren (was du ja mit reserve machst).

    0
  • D

    eigentlich häng ich immer nur was an der vector dran und er wird ziemlich oft durchlaufen, um zu gucken, ob sich ein bestimmtes Element in der Liste befindet.

    Deshalb hab ich ja auch überlegt, mir selber schnell ne verkette Liste zu programmieren, da sie ja nicht wirklich viele Funktionen braucht...

    0
  • .

    Vielleicht ein bisschen genauer? Es gibt noch einige Container mehr in der STL ;), da ist bestimmt ein passender dabei. Ich glaube nicht, dass es Sinn macht, selber eine Liste zu bauen (die mögliche Performance rechtfertigt die zusätzliche Arbeit nicht). Und wie gesagt, vector ist (wenn du seine Endgröße weißt) deutlich schneller als alles andere.

    0
  • F

    Autor unbekannt, ich finds aber ganz praktisch: http://quicix.de/A5.img Sry für den Referrer check...

    An welchen Stellen genau ist der Code denn langsam?

    Gruß

    0
  • D

    ich denke vector ist schon richtig, wahrscheinlich muss ich mir nur noch ein bischen Gedanken über die Speicherverwaltung machen.

    In den Vektoren sind eigentlich nur Zeiger gespeichert. Ich hab einen Baum, in dem jeder Knoten beliebig viele Kinder haben kann, deshalb der Vektor...
    Für die Knoten selber muss ich aber trotzdem immer einzeln Speicher anfordern. Ich hab mir jetzt überlegt, hier auch ziemlich viele Objekte auf einmal zu erstellen und dann bei Bedarf einfach nen Zeiger auf noch "freie" Objekte zu übergeben. Das müsste doch auch einen Geschwindigkeitsvorteil bringen, oder??

    0
  • D

    @FireFlow: Bisher hab ich immer gedacht, dass das Durchsuchen der Listen soviel Zeit beansprucht, vielleicht ist es aber auch das Reservieren von Speicher...

    0
  • .

    Also wenn ich das richtig verstehe, werden in deinem vector die Zeiger auf Unterknoten gespeichert. Wenn dem so ist, solltest du auf jeden Fall ptr_vector verwenden, sonst geht das mit den Pointern irgendwann schief. Dann könntest du noch soetwas wie den SmallObjectAllocator aus der Loki lib bauen oder verwenden.
    Möglicherweise ist es auch sinnvoll, ein ptr_set statt eines vectors zu benutzen, da du ja sicherlich durch diesen Baum durchgehst und dann ist ein sortierter Container angebrachter (du sagtest ja, dass Indexzugriff unwichtig ist).

    0
  • D

    Erstmal vielen Dank für die Hilfe.

    Ich hab vorhin mal versucht, so eine kleine "Speicherverwaltung" zu bauen:
    In der Funktion, die neue Knoten erstellt, hab ich ein statisches Array und einen Zähler erstellt. Dann hab ich immer noch freie Adressen aus dem Array an die neuen Zeiger übergeben. Allerdings wurde das Programm dann immer mit der Fehlermeldung "_CrtIsValidHeapPointer(pUserData)" abgebrochen.
    Wie ich inzwischen rausgefunden hab, ist das Problem wohl das Freigeben vom Speicher...

    Ich werd mir mal diesen SmallObjectAllocator angucken, der scheint ja genau das zu regeln

    0
Anmelden zum Antworten