dynamische Container in C
-
Hallo zusammen,
ich habe eine Frage bezüglich dynamischer Container in C. Angenommen ich habe eine Schleife, die pro Iteration eine Zahl berechnet. Ich weiß im Voraus nicht, wie lange die Schleife laufen wird, sodass ich kein Array fester Größe zum Auffangen der Ergebnisse erstellen kann.
In C++ würde ich jetzt einfach zu einem std::vector<int> greifen. Doch wie handhabt man solch einen Fall in C?
Die einzigen beiden Möglichkeiten, die mir auf die schnelle einfallen, sind die folgenden:
1.) Schreibe eine Klasse, die ein Array verwaltet. Sobald dieses voll ist und ein neues Element eingefügt werden soll, generiere ein neues (dynamisches) Array, das größer ist und kopiere das alte Array vollständig hinein. Das stelle ich mir jedoch extrem ineffizient vor.
2.) Schreibe deine eigene lineare Liste. Wahrscheinlich bekomme ich es aber auch nicht recht effizient hin.
Vielen Dank
LG, freakC++
-
freakC++ schrieb:
1.) Schreibe eine Klasse, die ein Array verwaltet. Sobald dieses voll ist und ein neues Element eingefügt werden soll, generiere ein neues (dynamisches) Array, das größer ist und kopiere das alte Array vollständig hinein. Das stelle ich mir jedoch extrem ineffizient vor.
Doch, das ist sogar extrem effizient, wenn man es richtig macht. Genau das macht nämlich auch std::vector. Die effiziente Strategie ist, dass das vergrößerte Array nicht 1 Element größer ist, sondern um einen bestimmten Faktor (2 hat sich bewährt). Dann ist die amortisierte Laufzeit O(1), anstatt O(N).
Denk auch an realloc, welches dir das Kopieren übernimmt. Und eventuell sogar Kopien ganz einspart, da es auch den schon vorhandenen Bereich gegebenenfalls vergrößern kann.
Im Zusammenhang mit deiner anderen Frage zur Objektkapselung geht natürlich ein einfaches realloc nicht so wirklich, denn da musst du gegebenenfalls die Kopier/Movemethode der Objekte aufrufen.
2.) Schreibe deine eigene lineare Liste. Wahrscheinlich bekomme ich es aber auch nicht recht effizient hin.
Möglich, aber Listen sind tatsächlich selten eine effiziente Lösung. Nur wenn man ein Problem hat, welches die wenigen Sachen oft benutzt, die eine Liste schnell kann.
Denk auch dran, dass du nicht der einzige C-Programmierer auf der Welt bist. Man muss nicht immer alles selber neu erfinden.
-
SeppJ schrieb:
Die effiziente Strategie ist, dass das vergrößerte Array nicht 1 Element größer ist, sondern um einen bestimmten Faktor (2 hat sich bewährt). Dann ist die amortisierte Laufzeit O(1), anstatt O(N).
2 hat sich nicht bewährt. https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
ich habe eine Frage bezüglich dynamischer Container in C. Angenommen ich habe eine Schleife, die pro Iteration eine Zahl berechnet. Ich weiß im Voraus nicht, wie lange die Schleife laufen wird, sodass ich kein Array fester Größe zum Auffangen der Ergebnisse erstellen kann.
Wenn es um dein bigint.tostring geht kannst du die Grösse doch ziemlich genau abschätzen. Nimm einfach ein Array, das sicher gross genug ist.
-
fgdxcydxcfgb schrieb:
SeppJ schrieb:
Die effiziente Strategie ist, dass das vergrößerte Array nicht 1 Element größer ist, sondern um einen bestimmten Faktor (2 hat sich bewährt). Dann ist die amortisierte Laufzeit O(1), anstatt O(N).
2 hat sich nicht bewährt. https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
Interessant. Unterstützt den Punkt, dass man nicht alles selber machen sollte. Andere Leute hatten viel mehr Zeit, sich genauer mit dem Thema zu beschäftigen.
(Wobei ich hier aber unbedingt nochmal selber testen würde. Die Argumentation kommt mir doch eher selbstdarstellerisch vor. Aber sie hat auch ein paar gute Argumente drin.)
