Implementierung std::vector in C

Hallo zusammen

Ich möchte in C eine an std::vector aus C++ angelehnte Bibliothek für dynamische Daten schreiben. Die Bibliothek soll (wenn möglich) ANSI-C konform sein und treu dem C++-Pendant für verschiedene Datentypen benutzbar sein.
Nun hab ich von mehreren Konzepten gehört, wie man dies angehen kann. Bevor ich zu viel Zeit in die (möglicherweise falsche) Richtung verschwende, wäre es gut, einige Meinungen dazu gehört zu haben.

Methode 1: Vergrössern des Speicherbereichs per realloc(), die Daten sollen hintereinander in einem einzigen Speicherblock liegen.
Relativ einfach realisierbar, sehe jedoch Probleme, wenn Elemente inmitten des Speicherbereichs gelöscht resp. hinzugefügt werden müssen, da dann u.U. grosse Datenmengen verschoben werden müssten, damit keine Lücken entstehen.

Methode 2: Verkettete Liste, einzelne Einträge bilden ein Element.
Wäre etwas aufwendiger zu implementieren, ein Hinzufügen- und Löschen von Daten wäre aber deutlich "schöner" als bei Methode 1. Hat allerdings einen grösseren Overhead, ausserdem wäre die Speicherverwaltung auch deutlich komplizierter, sofern nicht für jedes einzelne Element ein malloc()/free() Aufruf stattfinden soll.

Was meint ihr zu diesen zwei Methoden? Welche würdet ihr bevorzugen? Würdet ihr einen anderen Ansatz wählen, wenn ja, wie sähe dieser aus?

Danke für eure Antworten,

Der Hubschraubär

SeppJ

Das erste, was du beschreibst, entspricht dem C++ std::vector. Das zweite, was du beschreibst, entspricht der C++ std::list. Deine Analyse der Stärken und Schwächen gilt bei den C++-Umsetzungen genauso.

In C++ gilt: Default sollte stets zuerst einmal std::vector sein, außer man hat einen guten Grund dagegen. Es gibt nur sehr selten Gründe, die dann zu einer std::list führen. Zu krasser Overhead. Die gleiche Argumentation gilt dann natürlich auch in C, dass man selten eine verkettete Liste möchte und stattdessen fast immer Arrays oder dynamische Arrays (Vectoren).

Falls du es noch nicht wusstest: In C++ gibt es noch viel mehr Container in der Standardbibliothek. Die man auch alle in C implementieren kann. Ein Flowchart, was man wann wählen sollte:
https://i.stack.imgur.com/G70oT.png
Die std::list kommt dabei fast nie raus, weil man seltenst die Frage nach "frequent traversals" mit Nein beantworten wird. Und der vector kommt häufig raus, weil man den ganzen Extrakram der anderen Container nicht immer braucht.

Hallo SeppJ

Vielen Dank für deine Antwort.
Die Grafik ist super, vielen Dank dafür. Werde wohl dementsprechend meine Implementierung nach Methode 1 realisieren.

Wünsche einen schönen Tag,

Der Hubschraubär