Warum gibt es keine Hashtabellen in der C-Standardbibliothek?

Warum gibt es keine Hashtable-Unterstützung als Teil der Standard-C-Bibliothek? Gibt es dafür einen bestimmten Grund?

C erscheint nach heutigen Maßstäben ungewöhnlich, da keine nützlichen Datenstrukturen definiert sind. Keiner. Nicht einmal Strings – und wenn Sie denken, dass ein C-String eine Datenstruktur ist, müssen wir uns darüber einigen, was eine „Datenstruktur“ ist.

Wenn Sie C mögen, dann stellen Sie es sich als “leeres Blatt” vor … Ihre gesamte Anwendung besteht aus Code, der von Ihnen geschrieben wurde, und Bibliotheken, die Sie abrufen möchten, plus ein paar ziemlich primitiven Standardbibliotheksfunktionen, mit vielleicht ein oder zwei Ausnahmen wie qsort. Heutzutage verwenden die Leute C, um Dinge wie Python, Ruby, Apache oder den Linux-Kernel zu implementieren. Dies sind Projekte, die sowieso alle ihre eigenen Datenstrukturen verwenden, und sie würden wahrscheinlich nicht so etwas wie die STL verwenden.

Viele C-Bibliotheken implementieren generische Hash-Tabellen. Es gibt Kompromisse, und Sie können Ihren Favoriten auswählen. Einige von ihnen sind über Callbacks konfigurierbar.

• Glib hat ein Hash-Tabellenobjekt (Dokumentation)
• Apache Portable Runtime hat eine Hash-Tabelle (Dokumentation)
• Die Core Foundation-Bibliothek von Apple hat eine Hash-Tabelle (Dokumentation) Hinweis: Ja, Sie können jedes Objekt als Schlüssel oder Wert einfügen.
• UTHash ist eine Hash-Tabellenbibliothek (Dokumentation)
• Eine weitere Hash-Tabellenbibliothek (Verknüpfung)

Bei all diesen Bibliotheken, die tun, was Sie wollen, was bringt es dann, dem C-Standard eine Hash-Tabelle hinzuzufügen?

Es gibt keine Hashtabelle in der Standard-C-Bibliothek, weil entweder:

• niemand hat der Arbeitsgruppe einen Vorschlag unterbreitet; oder
• die Arbeitsgruppe hält dies für unnötig.

So funktioniert ISO. Vorschläge werden eingebracht und angenommen oder abgelehnt.

Sie müssen vorsichtig sein, was Sie der Standardbibliothek hinzufügen, da Sie zwei widersprüchliche Gruppen haben. Als ein Benutzer, Sie möchten vielleicht, dass jede Datenstruktur unter der Sonne zum Standard hinzugefügt wird, um die Sprache nützlicher zu machen.

Aber als Sprache Implementierer (Nebenbei gesagt, das sind wahrscheinlich die Leute, die die meisten der verschiedenen Arbeitsgruppen bilden, so dass ihre Ansicht wahrscheinlich mehr Einfluss hat), Sie wollen nicht wirklich den Aufwand haben, Dinge implementieren zu müssen, die möglicherweise nicht verwendet werden von allen. Alles, was es gab, als C89 erschien, hatte mit der Tatsache zu tun, dass der Hauptzweck darin bestand, bestehende Praktiken zu kodifizieren, anstatt neue Praktiken einzuführen. Alle Iterationen der Standards waren seitdem etwas freier in dem, was sie tun können, aber die Abwärtskompatibilität ist immer noch ein wichtiges Thema.

Ich selbst habe auch Konflikte. Ich würde gerne alle Funktionen der Java-, C++- oder Python-Bibliotheken in C zur Verfügung haben. Das würde es natürlich für Neulinge so viel schwieriger machen, alles zu lernen, und, wie ein Kommentator sagte, wahrscheinlich machen Code Monkey kann nützlichen Code auspumpen und dabei meinen Wert mindern 🙂

Und ich ziemlich haben alle Datenstrukturen, die ich jemals brauchen werde, aus meiner langen und (größtenteils) illustren Karriere. Sie sind für diese Art von Dingen nicht auf die Standardbibliothek beschränkt. Es gibt viele Tools von Drittanbietern, mit denen Sie die Arbeit erledigen können, und (wie ich) können Sie auch Ihre eigenen erstellen.

Wenn Sie wissen möchten, warum bestimmte Entscheidungen in jeder Iteration getroffen wurden, veröffentlicht ISO (und ursprünglich ANSI, bevor ISO übernahm) normalerweise Begründungsdokumente. Der C89 von ANSI ist zu finden hier. Es enthält diese kleine Schönheit im Umfang:

Diese Begründung konzentriert sich in erster Linie auf Ergänzungen, Klarstellungen und Änderungen, die an der in den Basisdokumenten beschriebenen Sprache vorgenommen wurden. Es ist keine Begründung für die C-Sprache als Ganzes: Das Komitee wurde damit beauftragt, eine bestehende Sprache zu kodifizieren, nicht eine neue zu entwerfen. In dieser Begründung wird kein Versuch unternommen, die bereits vorhandene Syntax der Sprache zu verteidigen, wie etwa die Syntax von Deklarationen oder die Bindung von Operatoren.

Ich genieße besonders das Eingeständnis, dass sie nicht für irgendein unheiliges Durcheinander verantwortlich sind, das ihren Standardisierungsversuchen vorausgegangen sein könnte.

Aber vielleicht liegt die wahre Antwort auf Ihre Frage in diesem Teil, einem der Leitprinzipien:

Bewahre den Geist von C. Das Komitee hat sich zum Ziel gesetzt, den traditionellen Geist von C zu bewahren. Es gibt viele Facetten des Geistes von C, aber die Essenz ist ein Gemeinschaftsgefühl der zugrunde liegenden Prinzipien, auf denen die C-Sprache basiert. Einige der Facetten des Geistes von C können in Sätzen zusammengefasst werden wie:

• Vertrauen Sie dem Programmierer.
• Verhindern Sie nicht, dass der Programmierer das tut, was getan werden muss.
• Halten Sie die Sprache klein und einfach.
• Geben Sie nur eine Möglichkeit an, eine Operation durchzuführen.
• Machen Sie es schnell, auch wenn es nicht garantiert tragbar ist.

Dieser dritte ist wahrscheinlich der Hauptgrund, warum die Bibliothek nicht mit den anfänglichen Standardisierungsbemühungen massiv erweitert wurde – das, und die Tatsache, dass eine solche Erweiterung von einem Komitee wahrscheinlich dazu geführt hätte, dass ANSI C die Bezeichnung C2038 statt C89 erhalten hätte.

Die Standard-C-Bibliothek enthält nicht irgendein große, persistente Datenstrukturen – weder Listen, noch Bäume, noch Stacks, noch Hashtables.

Es ist nicht wirklich möglich, eine endgültige Antwort zu geben, ohne die Autoren der ursprünglichen C-Bibliothek zu fragen. Eine plausible Erklärung ist jedoch, dass die Implementierung solcher Datenstrukturen verschiedene Kompromisse beinhaltet und nur der Autor der Anwendung in der richtigen Position ist, diese Kompromisse einzugehen.

Beachten Sie, dass die POSIX-Standard-C-Bibliothek generische Hashtable-Funktionen spezifiziert: hcreate(), hsearch() und hdestroy(); und beachten Sie auch, dass ihre “eine Grösse passt allen” Die Natur neigt dazu, sie für die meisten Anwendungsfälle in der realen Welt unangemessen zu machen, was das obige Argument unterstützt.

Aufgrund fehlender Vorlagen

Dies ist eine Vermutung, aber ohne Vorlagen in der Sprache wie C++ ist die Implementierung von Containern sehr unelegant, da Sie Dutzende von Definitionen benötigen würden, um alle möglichen Typen abzudecken, ganz zu schweigen von benutzerdefinierten Typen.

Es gibt C-Strategien, um dies zu mildern, wie z. B. herumspielen void *aber sie verlieren Typüberprüfungen zur Kompilierzeit.

GLib und gnulib sind im Moment meine empfohlenen Implementierungen: Quick Way to Implement Dictionary in C