STL implementation ohne dynamische speicher-allokation
-
hi,
bei der entwicklung zb. für embedded systeme steht man häufig vor dem problem, dass dynamische speicher-allokation ein absolutes no-go ist, da man sich ruckzuck den heap fragmentiert.
damit fallen natürlich große teile der STL wie listen aber auch strings flach. umschifft wird das problem gern mit C style code, als zb. c-strings mit fixer größe, die zu einem klar definierten zeitpunkt allokiert werden und wenn möglich verzicht auf dynamische datenstrukturen (arrays mit fixer größe statt listen etc.), wobei eben darauf geachtet wird, ein einziges mal genug speicher für den worst case an objekten etc. zu allokieren.
ich dachte doch, dass es dafür längst irgendwo ein lösung geben müsste, zb. STL-kompatible (oder zumindest ähnliche) container, die man auf einem festen speicherblock arbeiten lassen kann um dynamische allokation vollständig zu umgehen.
allerdings hab ich da wirklich nichts gefunden - kann das sein? vielleicht überseh ich ja auch ein grundlegendes problem, dass einer solchen lib im wege steht?
-
im prinzip ist C++ in dieser hinsicht sehr erweiterbar.
in deinem fall würde vielleicht einboost::arrayreichen, aber im prinzip kannst du dir für die standardcontainer (vector, string, ...) auch einen eigenen allocator schreiben.
-
boost::arrays sind schön und gut aber eben nur arrays. wenn man strings, listen, maps etc. braucht siehts schonwieder düster aus.
die allokatoren hatte ich mir auch schon angesehen. soweit ich das verstanden habe, werden die aber nur zum allokieren der eigentlichen objekte benutzt (also bei list<MyClass> nur für die eigentlichen MyClass instanzen), nicht aber für die internen strukturen des containers (zb. next/prev pointer etc. einer liste).
-
maximAL schrieb:
hi,
bei der entwicklung zb. für embedded systeme steht man häufig vor dem problem, dass dynamische speicher-allokation ein absolutes no-go ist, da man sich ruckzuck den heap fragmentiert.Da ich keine Ahnung von embedded Systemen habe: Ist jegliches new/delete auszuschließen, oder nur häufiges?
Der Hintergrund ist der: Sofern man von vorne hinein die Größe mit angibt wird beim std::vector nur einmalig Speicher alloziert (Sofern man innerhalb der Größe bleibt, und ansonsten wird nur beim vergrößern umkopiert).
Grundsätzlich ist es aber nicht möglich dynamische Datenstrukturen ohne Allozierungen zu bewerkstelligen. Daher...
maximAL schrieb:
boost::arrays sind schön und gut aber eben nur arrays. wenn man strings, listen, maps etc. braucht siehts schonwieder düster aus.
...wirst du hier auch nicht um new/delete kommen. Listen sind dabei Problematischer als Maps, da sie ja an sich pro Element eine Allozierung durchführen.
Grundsätzlich kann man natürlich einmalig einen Speicherbereich der Größe n allozieren, und dann per replace new innerhalb des Speicherbereiches arbeiten. Dann ist der Aufwand der Verwaltung aber ggf. schon wieder so hoch das ich nicht denke das man ohne weiteres Bibliotheken dazu findet. Und eine Fragmentierung des Speichers wird man auch hier nicht ausschließen können.
cu André
-
Immerhin funktioniert ja alles aus <algorithm> auch auf normalen Arrays.
Eine Liste kannst du ja auch selbst erstellen: Ein Array mit dem Elementen drin und ein Array gleicher Größe mit Pointern auf jene Elemente. So kannst du die Elemente schnell verschieben indem du die Pointer umkopierst.
"Fertiges" kenne ich da auch nicht.
-
maximAL schrieb:
boost::arrays sind schön und gut aber eben nur arrays. wenn man strings, listen, maps etc. braucht siehts schonwieder düster aus.
die allokatoren hatte ich mir auch schon angesehen. soweit ich das verstanden habe, werden die aber nur zum allokieren der eigentlichen objekte benutzt (also bei list<MyClass> nur für die eigentlichen MyClass instanzen), nicht aber für die internen strukturen des containers (zb. next/prev pointer etc. einer liste).