interne struktur von vector



  • hi
    wie ist der stdvector eigendlich intern aufgebaut?
    ist es eine liste mit extraeigenschaften oder einfach ein reservierter speicherblock, der gegebenenfalls vergrößert wird?
    (mir geht es darum, ob pro eintrag zusätzlich zu dem speicher für meine daten auchnoch speicher für irgendwelche pointer reserviert wird)

    schonmal danke



  • der vector ist ein einfaches array. Es wird nichts zusätzlich allokiert, da garantiert ist, dass die Elemente im Speicher hintereinander vorkommen.



  • Das ist üblicherweise ein Speicherblock, der ggf. vergrössert wird.

    Der Speicherblock ist aber meistens grösser, als der, den du in Wirklichkeit belegst, damit günstig weitere Elemente eingefügt werden können.



  • also wäre es,wenn ich eine virtuelle datei speichern will, sinnvoller einen vektor zum speichern zu nehmen, als selber die speicherverwaltung zu machen?



  • Im Allgemeinen schon.

    Ausnahmen: Die Elemente müssen sortiert sein, es gibt eine bestimmte Maximalgrösse, du fügst die Elemente meistens irgendwo in der Mitte ein, ... dann gibt es geeignetere Container, aber die sind auch in der STL (bis auf boost-Container wie boost::array und boost::ptr_vector)



  • Es ist immer günstiger einen vector zu nehmen, als Felder mit new zu allokieren. Ein vector bietet dir alle Vorteile eines Feldes und zusätzlich die Vorteile der Objektorientierung. Auch kannst du damit deinen Code absichern, was aber selbstverständlich wieder etwas Geschwindigkeit kostet.



  • Nick Unbekannt schrieb:

    Es ist immer günstiger einen vector zu nehmen, als Felder mit new zu allokieren.

    Nein, nicht immer. Im Allgemeinen.
    `

    sizeof(std::vector)` ist bei mir 12 (unabhängig vom Typ) und allein das bringt einen Memory overhead mit sich. Dazu kommen noch die Geschwindigkeitskosten und dann ist dein immer nicht mehr so absolut.



  • Allgemeinheit schrieb:

    sizeof(std::vector)[/c] ist bei mir 12 (unabhängig vom Typ) und allein das bringt einen Memory overhead mit sich.

    Auf Systemen wo so etwas interessant werden könnte, habe ich noch nicht mal einen C++ Compiler. Wenn ich den Luxus hätte, würde ich mir ihn aber auf jeden Fall gönnen. Wenn man wirklich so wenig Speicher hat, dass die paar Bytes ins Gewicht fallen, dann spart man sich auch die RT-Lib und baut sich selber einen Speicherpool, wo der Speicher schon sinnvoll angeordnet ist.
    Stell dir einfach vor du hättest ein 96Bit-System 😉

    Allgemeinheit schrieb:

    Dazu kommen noch die Geschwindigkeitskosten und dann ist dein immer nicht mehr so absolut.

    Welche Geschwindigkeitskosten? Unterschiede treten nur auf wenn du die Größe änderst, was auch bei eigenen Allokationen langsam ist. Der vector könnte hier sogar etwas schneller sein, weil er dafür Spezialisiert ist.



  • Angenommen, du hast einen std::vector<std::vector> mit sehr vielen sehr kleinen vectoren. Dann wird das interessant, auch bei deinem Computer.
    Und stärker optimiert als ein Array wird der hundert prozentig nicht sein, maximal gleich gut. Aber ich spielte da eher auf boost::array an (was manchmal wirklich besser ist als ein Vektor), als auf ein normales C-Array.

    Geschwindigkeitskosten sind z.Bsp. die Überprüfung bei at(), ob der Index im Bereich ist.



  • Welche Geschwindigkeitskosten?

    Noch nicht mitbekommen? Zunächst war ja im Gespräch, ein absolutes Tempolimit für std::vector einzuführen. Man ist letztlich aber doch von dem Gedanken abgekommen und erhebt nun Abgaben auf dessen Geschwindigkeit.



  • Allgemeinheit schrieb:

    Angenommen, du hast einen std::vector<std::vector> mit sehr vielen sehr kleinen vectoren. Dann wird das interessant, auch bei deinem Computer.

    Deswegen hatte ich den Beisatz "als Felder mit new zu allokieren" geschrieben. Ohne diese Einschränkung ändert sich das Verhalten, dass ist klar.

    Allgemeinheit schrieb:

    Und stärker optimiert als ein Array wird der hundert prozentig nicht sein, maximal gleich gut.

    Die Optimierungen betreffen ja auch den Code, wie du die Speichergröße änderst und gegebenenfalls die Daten kopierst. Das dürfte recht effizient ausgelegt sein.

    Allgemeinheit schrieb:

    Aber ich spielte da eher auf boost::array an (was manchmal wirklich besser ist als ein Vektor), als auf ein normales C-Array.

    Ein vector verhält sich äquivalent zu einem C-Array.

    Allgemeinheit schrieb:

    Geschwindigkeitskosten sind z.Bsp. die Überprüfung bei at(), ob der Index im Bereich ist.

    Als Programmierer sollte man den Unterschied von [] und at() kennen.

    Ich sehe keinen Vorteil in einem per new allokierten Feld. Dass es meines Wissens nach kein shared_ptr für Felder gibt unterstreicht den Einsatz.


  • Mod

    Allgemeinheit schrieb:

    Geschwindigkeitskosten sind z.Bsp. die Überprüfung bei at(), ob der Index im Bereich ist.

    Das ist ein optionales feature, welchen man nutzen kann, aber nicht muss. Bei einfachen Objekten ist vector 100% gleich schnell wie ein vergleichbares dynamisches Array - es ist ja auch der gleiche Code. Erst wenn's verschachtelt wird, wird es durch die vielen Indirektionen langsamer als ein Array.



  • Man kann mit einem modernen Compiler schon davon ausgehen, dass std::vector mit operator[] genau so schnell wie ein Array bzw. dynamisch angeforderter Speicherbereich ist oder zumindest so schnell gemacht werden kann (Stichwort _SECURE_SCL unter MSVC). Der Vergleich von .at zu Array-Adressierung ist unfair; .at macht mehr als das. Wenn man bei einem flachen Array vor der Adressierung prüft, ob der Index noch im Array liegt, kommt genau das selbe raus.

    Aber: std::vector ist nicht äquivalent zu new[], auch wenn man ihn als Ersatz dafür benutzen kann und damit die Vorteile von RAII (und dadurch Exceptionsicherheit) genießt.

    Anders als new[] fordert std::vector von seinem Allokator stumpf Speicher an und konstruiert Objekte später nach Bedarf dort hinein. Das hat, wenn man zur Laufzeit Größenänderungen benötigt, den Vorteil, dass std::vector sich mehr Speicher vorhalten kann, als zur Zeit benutzt wird, so dass weniger hin- und herkopiert werden muss, und auch den, dass die in ihm gespeicherte Klasse keinen Default-Konstruktor benötigt. Auch ist es in Eckfällen gelegentlich nützlich, eigene Allokatoren angeben zu können; etwa kann es in stark nebenläufigen Systemen helfen, Heap-Contention zu vermeiden.

    std::tr1::array ist wieder anders, indem es stumpf etwas Zusatzfunktionalität an ein Array kleistert. Das ist zweifelsohne nützlich, aber mit new[] und std::vector nur bedingt vergleichbar - die Größe muss hier zur Compilezeit feststehen, und der Heap wird nicht bemüht.

    Was wann sinnvoll ist, ist im Einzelfall zu beurteilen. Allerdings ist die nackte Verwendung von new[] aus dem oben genannten Grund der Exceptionsicherheit wohl eher selten sinnvoll - man sollte schon einen kleinen RAII-Wrapper drumherum setzen.

    P.S.: Als Ersatz für std::vector<std::vector<foo> > sei noch boost::multi_array erwähnt.



  • Nick Unbekannt schrieb:

    Ein vector bietet dir alle Vorteile eines Feldes und zusätzlich die Vorteile der Objektorientierung.

    Ein std::vector ist nu' wirklich nicht objektorientiert.
    Nachher kommt noch einer und sagt dass Strings objektorientiert sind, dann sind wir auch schon bald bei Integers und bei einzelnen Bits.

    int oo_ftw = 0; // <-- objektorientiert, yeah!!!
    

    😉



  • Nick Unbekannt schrieb:

    Dass es meines Wissens nach kein shared_ptr für Felder gibt unterstreicht den Einsatz.

    Äh.
    Lies mal da: http://www.boost.org/doc/libs/1_45_0/libs/smart_ptr/shared_array.htm


Log in to reply