Ich implementiere eine Reihe von gemeinsamen, aber nicht so trivialen (oder fehleranfälligen) Datenstrukturen für C ( hier ) und kam nur mit einer Idee, die mich zum Nachdenken brachte.
Die Frage ist, wie lassen sich am besten zwei Strukturen implementieren, die ähnliche Algorithmen verwenden, aber unterschiedliche Schnittstellen haben, ohne den Algorithmus kopieren / einfügen / neu schreiben zu müssen? Am besten, meine ich Meist wartbar und Debug-fähig.
Ich denke, es ist offensichtlich, warum Sie nicht zwei Kopien desselben Algorithmus haben wollen.
Angenommen, Sie haben eine Struktur (nennen Sie sie map ) mit einer Menge zugehöriger Funktionen ( map_*() ). Da die Karte alles zu irgendwas zuordnen muss, würden wir sie normalerweise mit void *key und void *data implementieren. Denken Sie jedoch an eine Karte von int bis int . In diesem Fall müssten Sie alle Schlüssel und Daten in einem anderen Array speichern und ihre Adressen dem map geben, was nicht so praktisch ist.
Stellen Sie sich nun vor, es gäbe eine ähnliche Struktur (nennen Sie mapc , c für "Kopien"), die bei der Initialisierung sizeof(your_key_type) und sizeof(your_data_type) und void *key und void *data beim Einfügen benötigt memcpy , um die Schlüssel und Daten in der Map zu kopieren, anstatt nur die Zeiger beizubehalten. Ein Anwendungsbeispiel:
was ziemlich nett ist, weil ich kein weiteres Array von i s und j s behalten muss.
Im obigen Beispiel sind map und mapc sehr eng verwandt. Wenn Sie darüber nachdenken, sind auch map und set Strukturen und Funktionen sehr ähnlich. Ich habe über die folgenden Möglichkeiten nachgedacht, ihren Algorithmus nur einmal zu implementieren und für alle von ihnen zu verwenden. Keiner von ihnen ist mir jedoch recht befriedigend.
Verwenden Sie Makros. Schreiben Sie den Funktionscode in eine Headerdatei und belassen Sie die strukturabhängigen Einträge als Makros. Definieren Sie für jede Struktur die richtigen Makros und schließen Sie die Datei ein:
%Vor%Diese Methode ist nicht halb so schlimm, aber sie ist nicht so elegant.
Verwenden Sie Funktionszeiger. Übergeben Sie für jeden Teil, der von der Struktur abhängig ist, einen Funktionszeiger.
%Vor% Diese Methode erfordert das Schreiben von mehr Funktionen, die in der Makro-Methode hätten vermieden werden können (wie Sie sehen, ist der Code hier länger) und ermöglicht es den Optimizern nicht, die Funktionen inline zu integrieren (da sie nicht sichtbar sind map_generic.c Datei).
Also, wie würden Sie so etwas umsetzen?
Hinweis: Ich habe den Code in das Stapel-Überlauf-Frageformular geschrieben, also entschuldige mich, wenn es kleinere Fehler gibt.
Nebenfrage: Jeder hat eine bessere Idee für ein Suffix, dass "diese Struktur kopiert die Daten anstelle des Zeigers"? Ich benutze c , das sagt "Kopien", aber es könnte ein viel besseres Wort dafür auf Englisch geben, von dem ich nichts weiß.
Ich habe eine dritte Lösung gefunden. In dieser Lösung wird nur eine Version von map geschrieben, die eine Kopie von Daten enthält ( mapc ). Diese Version würde memcpy verwenden, um Daten zu kopieren. Die andere map ist eine Schnittstelle dazu, indem sie die Zeiger void *key und void *data übernimmt und &key und &data an mapc sendet, so dass die darin enthaltene Adresse kopiert wird (mit memcpy ).
Diese Lösung hat den Nachteil, dass eine normale Zeigerzuweisung von memcpy ausgeführt wird, aber das Problem wird vollständig gelöst und ist sehr sauber.
Alternativ kann man nur das map implementieren und ein zusätzliches vectorc mit mapc verwenden, das zuerst die Daten in Vektor kopiert und dann die Adresse in map gibt. Dies hat den Nebeneffekt, dass das Löschen von mapc entweder wesentlich langsamer ist oder Müll zurücklässt (oder andere Strukturen benötigt, um den Müll wiederzuverwenden).
Ich kam zu dem Schluss, dass unvorsichtige Benutzer meine Bibliothek so verwenden könnten, wie sie C ++ schreiben, Kopie nach Kopie nach Kopie. Deshalb verzichte ich auf diese Idee und akzeptiere nur Hinweise.
Es gibt auch eine dritte Option, die Sie nicht berücksichtigt haben: Sie können ein externes Skript (in einer anderen Sprache geschrieben) erstellen, um Ihren Code aus einer Reihe von Vorlagen zu generieren. Dies ähnelt der Makromethode, Sie können jedoch eine Sprache wie Perl oder Python verwenden, um den Code zu generieren. Da diese Sprachen leistungsfähiger als der C-Preprozessor sind, können Sie einige der potenziellen Probleme vermeiden, die mit der Erstellung von Vorlagen über Makros verbunden sind. Ich habe diese Methode in Fällen verwendet, in denen ich versucht war, komplexe Makros wie in Beispiel 1 zu verwenden. Am Ende erwies es sich als weniger fehleranfällig als mit dem C-Präprozessor. Der Nachteil ist, dass es zwischen dem Schreiben des Generator-Skripts und dem Aktualisieren der Makefiles etwas schwieriger ist, anfänglich eingerichtet zu werden (aber IMO ist es am Ende wert).
Sie haben grob beide möglichen Lösungen abgedeckt.
Die Präprozessormakros entsprechen in etwa C ++ - Templates und haben die gleichen Vor- und Nachteile:
Die Funktionszeiger entsprechen in etwa dem C ++ Polymorphismus und sie sind IMHO sauberer und in der Regel einfacher zu bedienende Lösung, aber sie bringen einige Kosten zur Laufzeit (für enge Schleifen können einige zusätzliche Funktionsaufrufe teuer sein).
Im Allgemeinen bevorzuge ich die Funktionsaufrufe, außer die Leistung ist wirklich kritisch.
Tags und Links c data-structures interface abstract-data-type