C++ vector<forward_list>

[Freezedevil]

Hi,

ich hab heute eine vermutlich einfach zu beantwortende Frage, aber ich stehe nach einem langen Tag irgendwie auf dem Schlauch. Ich möchte einen Vector von forward_lists anlegen. Die Anzahl der Listen ist konstant, die Länge der Listen kann stets zu- oder abnehmen. Die Frage die ich mir gerade stelle ist ob es Sinn ergibt statt vector<forward_list> einen vector<shared_ptr<forward_list>> zu verwenden. Eine Liste "besteht" ja nur aus dem ersten Element, welches auf das nächste zeigt, weshalb der Pointer eigentlich unnötig wäre. Übersehe ich hier irgendwas oder ergibt der Pointer doch Sinn? Das Ziel ist eigentlich lediglich, dass ich mir rumschieben/kopieren von Speicher spare, wie es bei einem vector<vector> der Fall sein könnte.

Vielen Dank für eure Antworten.

 

[antred]

Vor C++11 könntest du damit vielleicht Recht gehabt haben, aber nachdem es nun move constructors gibt und ich erwarte, daß zumindest die von der C++ standard library zur Verfügung gestellten Container diesen auch unterstützen, denke ich, daß du dir deswegen keine Sorgen machen brauchst.

Ich würde also einfach bei vector<forward_list> bleiben.

Ergänzung (3. Dezember 2014)

P.S. Dazu kommt noch, daß das Kopieren von einem shared_ptr - falls die Kopie nicht auch durch einen move contructor oder durch eine Compiler-Optimierung (copy elision) vermieden wird - auch nicht gerade billig ist. Hier kommt ja noch dazu, daß dann der Referenzzähler im control block des Pointers erhöht und wieder dekrementiert werden muß, und zwar unter Synchronisation (das ist nie billig), da shared_ptr zumindest paralleles Lesen desselben shared_ptr-Objekts aus mehreren Threads unterstützt.

Ergänzung (3. Dezember 2014)

P.S. #2 Aber du kannst ja mal beide Lösungen probieren und dann ein paar Profiling-Läufe machen. Vielleicht gibt es ja überraschende Ergebnisse.

P.S. # 3 Dann fällt mir noch ein, daß dein shared_ptr-Ansatz (selbst wenn er das Kopieren billiger machen sollte) den Standardfall - also den normalen Zugriff auf ein Element - teurer macht, da er eine weitere Indirektionsebene einführt (vector-Element holen, Pointer dereferenzieren und erst dann Listen-Element holen).

 

[Freezedevil]

P.S. # 3 Dann fällt mir noch ein, daß dein shared_ptr-Ansatz (selbst wenn er das Kopieren billiger machen sollte) den Standardfall - also den normalen Zugriff auf ein Element - teurer macht, da er eine weitere Indirektionsebene einführt (vector-Element holen, Pointer dereferenzieren und erst dann Listen-Element holen).

Genau deshalb wollte ich ja auch eigentlich darauf verzichten. Ich möchte die Listen ja nichtmal kopieren oder verschieben. Beim erzeugen des Vectors steht bereits fest wie viele Listen er enthält und dort werden sie auch gleich angelegt (leer). Anschließend will ich lediglich erreichen, dass die Einträge im Vector eine konstante Größe haben, sodass dieser nicht vergrößert/verkleinert werden muss, wenn ich in den Listen Elemente einfüge/entferne.

 

[antred]

Genau deshalb wollte ich ja auch eigentlich darauf verzichten. Ich möchte die Listen ja nichtmal kopieren oder verschieben. Beim erzeugen des Vectors steht bereits fest wie viele Listen er enthält und dort werden sie auch gleich angelegt (leer). Anschließend will ich lediglich erreichen, dass die Einträge im Vector eine konstante Größe haben, sodass dieser nicht vergrößert/verkleinert werden muss, wenn ich in den Listen Elemente einfüge/entferne.

Wieso sollte der vector vergrößert/verkleinert werden müssen, wenn du lediglich in den enthaltenen Listen Elemente hinzufügst oder entfernst? Ich behaupte mal, daß diese Assertion ...

forward_list< SomeType > a;
forward_list< SomeType > b;

// ...

assert( sizeof( a ) == sizeof( b ) );

immer wahr ist, egal wieviele Elemente die Listen a und b enthalten.

 

[Freezedevil]

Ok, dann kann ich bedenkenlos auf den Pointer verzichten.

 

[disassembler]

Ich möchte noch ergänzen, das ein Vektor ebenfalls seine Größe nicht verändert, wenn sich die Anzahl der darin enthaltenen Elemente ändert.
Ein Vektor ist im wesentlichen:

template<typename T>
class vector
{
T* data;
std::size_t size;
std::size_t capacity;
}

Wenn nun die Kapazität nun nicht mehr ausreicht, wird ein neuer Speicher angefordert, und der bisherige Inhalt auf den data zeigt, da reinkopiert, der alte Speicher wird gelöscht und data verweist nun auf den neuen Speicher. Der neue wie alte Pointer ist gleich lang, also bleibt das eigentliche Vektorelement unverändert groß - in C++ können Datentypen gar nicht ihre Größe verändern.
Wenn du also vector<vector> hast, wird der äußere Vektor nicht seine Größe verändern, wenn du eines seiner Vector Elemente Dinge hinzufügst oder entfernst.Wenn du so willst, macht der Vector quasi unfreiwillig sowieso schon das, das du überlegtest mit Pointern zu erreichen. Ein Vektor ist nur ein sehr intelligenter Pointer...
Und seit C++11 ist, selbst wenn du den äußeren Vektor in der Größe verändern würdest, das ganze keine Katastrophe, da nur noch bei einer Kapazitätsänderung quasi die data-pointer in den nun größeren Vektor kopiert werden und nicht wie früher auch jeweils noch die Datenbereiche kopiert werden.

 

[Miuwa]

Darf ich fragen, was für einen Datentyp du in den Listen speichern willst (groß oder klein - POD oder nicht) und wie deine Zugriffspattern darauf aussehen (hautpsächlich lesezugriffe oder viele inserts / deletes - sequenziell/ zufällig)? In 99% der Fälle ist ein vector<vector<T>> effizienter als ein vector<forward_list<T>> und wenn du die Anzahl der Listens schon zur Kompilierzeit kennst wäre ein std::array<vector,N> noch einen Tick besser.

 

[Freezedevil]

Ich hab auch schon daran gedacht ein std::array zu nehmen, meine mich aber zu erinnern, dass das kein Punkte bringt. Die Größe kenne ich zur Kompilierzeit nicht, allerdings zur Laufzeit bevor ich den Vector anlege. Die Einträge sind mit 16Byte ziemlich klein und es wird wild eingefügt und gelöscht. Ich möchte da jetzt aber ehrlich gesagt gar nicht weiter ausholen. Meine Ursprungsfrage ist beantwortet und darüber was am besten ist muss ich nochmal nachdenken bzw. durch Profiling ermitteln.
Ich danke soweit euch allen für die hilfreichen Anmerkungen.