Warum ist der Code in den meisten STL-Implementierungen so kompliziert?

71

Die STL ist ein kritischer Teil der C ++ - Welt. Die meisten Implementierungen stammen aus den anfänglichen Bemühungen von Stepanov und Musser.

Meine Frage ist angesichts der Kritikalität des Codes gegeben, und es ist eine der Hauptquellen für Menschen, Beispiele für gut geschriebenes C ++ sowohl für Ehrfurcht- als auch für Lernzwecke anzusehen: Warum sind die verschiedenen Implementierungen der STL so ekelhaft anzusehen - verschlungen und Im Allgemeinen gute Beispiele dafür, wie man C ++ - Code aus ästhetischer Sicht nicht schreibt.

Die folgenden Codebeispiele würden die Codeüberprüfung an den Orten, an denen ich gearbeitet habe, aus Gründen nicht bestehen, die von der Benennung der Variablen, dem Layout, den Makros und der Verwendung von Operatoren abweichen, die mehr als einen einfachen Blick erfordern, um herauszufinden, was tatsächlich geschieht.

template<class _BidIt> inline
bool _Next_permutation(_BidIt _First, _BidIt _Last)
{  // permute and test for pure ascending, using operator<
_BidIt _Next = _Last;
if (_First == _Last || _First == --_Next)
   return (false);

for (; ; )
   {  // find rightmost element smaller than successor
   _BidIt _Next1 = _Next;
   if (_DEBUG_LT(*--_Next, *_Next1))
      {  // swap with rightmost element that's smaller, flip suffix
      _BidIt _Mid = _Last;
      for (; !_DEBUG_LT(*_Next, *--_Mid); )
         ;
      _STD iter_swap(_Next, _Mid);
      _STD reverse(_Next1, _Last);
      return (true);
      }

   if (_Next == _First)
      {  // pure descending, flip all
      _STD reverse(_First, _Last);
      return (false);
      }
   }
}


_Ty operator()()
   {  // return next value
   static _Ty _Zero = 0;   // to quiet diagnostics
   _Ty _Divisor = (_Ty)_Mx;

   _Prev = _Mx ? ((_Ity)_Ax * _Prev + (_Ty)_Cx) % _Divisor
      : ((_Ity)_Ax * _Prev + (_Ty)_Cx);
   if (_Prev < _Zero)
      _Prev += (_Ty)_Mx;
   return (_Prev);
   }

Bitte beachten Sie, dass ich die Benutzeroberfläche nicht kritisiere, da sie sehr gut gestaltet und anwendbar ist. Was mich beunruhigt, ist die Lesbarkeit der Implementierungsdetails.

Ähnliche Fragen wurden bereits gestellt:

Gibt es eine lesbare Implementierung der STL?

Warum ist die STL-Implementierung so unlesbar? Wie hätte C ++ hier verbessert werden können?

Hinweis: Der oben dargestellte Code stammt aus dem MSVC 2010-Algorithmus und den Warteschlangenheadern.

Gemeinschaft
quelle
2
STL ist nicht gerade ein Objektmodell, das in anderen Sprachen weit verbreitet ist. Aber darum geht es bei Ihrer Beschwerde nicht. Dies ist die Art von Mist, den Bibliotheksdesigner durchmachen müssen, wenn die Sprache einen Präprozessor hat. Oh, und die gesamte Implementierung in einen Header schreiben zu müssen.
Hans Passant
20
Es war schwer zu schreiben. Es sollte schwer zu lesen sein.
Nur meine richtige Meinung
6
@Hans: Sie hatten zwei Jahrzehnte Zeit zu sagen, ok, dass wir dies von Grund auf neu machen "- angesichts der Tatsache, dass c ++ 0x Änderungen für die Verschiebungs- und Rvalue-Semantik erfordert, wäre es nicht ein guter Zeitpunkt zu sagen, lassen Sie uns einfach re -schreibe das Ganze, benutze nur die Sprache, benutze all die neuen guten Sachen, die hinzugefügt werden usw.
5
... Die Implementierungsdetails der STL müssen einfach und klar sein und als gutes Beispiel für C ++ dienen.
TheUndeadFish
4
@sonicoder: Jemand besitzt zweifellos das Urheberrecht an diesem Code. Bitte geben Sie mindestens an, von wo Sie den Code kopiert haben.
James McNellis

Antworten:

20

In Bezug auf die Variablennamen müssen Bibliotheksimplementierer "verrückte" Namenskonventionen verwenden, z. B. Namen, die mit einem Unterstrich gefolgt von einem Großbuchstaben beginnen, da diese Namen für sie reserviert sind. Sie können keine "normalen" Namen verwenden, da diese möglicherweise von einem Benutzermakro neu definiert wurden.

In Abschnitt 17.6.3.3.2 "Globale Namen" §1 heißt es:

Bestimmte Sätze von Namen und Funktionssignaturen sind immer der Implementierung vorbehalten:

  • Jeder Name, der einen doppelten Unterstrich enthält oder mit einem Unterstrich gefolgt von einem Großbuchstaben beginnt, ist der Implementierung für jede Verwendung vorbehalten.

  • Jeder Name, der mit einem Unterstrich beginnt, ist der Implementierung zur Verwendung als Name im globalen Namespace vorbehalten.

(Beachten Sie, dass diese Regeln Header-Wachen verbieten, wie __MY_FILE_Hich sie schon oft gesehen habe.)

Fredoverflow
quelle
@peoro, Namespaces helfen nicht für Variablen innerhalb einer Klasse.
Winston Ewert
6
@ peoro-Namespaces schützen Sie nicht vor Präprozessor-Makros. _Namessind für die Implementierung reserviert. Wenn Sie also solche Makros haben, ist es auf Ihrem Kopf. Auf der anderen Seite sollten Sie nicht gezwungen sein zu erraten, wie eine STL-Implementierung entscheiden könnte, intern einen Bezeichner zu verwenden, für den Sie kein Makro erstellen sollten, zumal dies von Implementierung zu Implementierung variieren kann.
Logan Capaldo
Du hast recht. Ich habe "Makro" übersprungen und über Benutzervariablen / -funktionen nachgedacht, was keinen Sinn ergab.
Peoro
19

Neil Butterworth, jetzt als "anon" aufgeführt, lieferte einen nützlichen Link in seiner Antwort auf die SO-Frage "Gibt es eine lesbare Implementierung der STL?" . Zitiert dort seine Antwort:

Es gibt ein Buch The C ++ Standard Template Library, das von den ursprünglichen STL-Designern Stepanov & Lee (zusammen mit PJ Plauger und David Musser) gemeinsam verfasst wurde und eine mögliche Implementierung mit Code beschreibt - siehe http://www.amazon. co.uk/C-Standard-Template-Library/dp/0134376331 .

Siehe auch die anderen Antworten in diesem Thread.

Wie auch immer, der größte Teil des STL-Codes (mit STL meine ich hier die STL-ähnliche Teilmenge der C ++ - Standardbibliothek) ist Vorlagencode und muss als solcher nur Header sein, und da er in fast jedem Programm verwendet wird, lohnt es sich, diesen zu haben Code so kurz wie möglich.

Somit ist der natürliche Kompromisspunkt zwischen Prägnanz und Lesbarkeit am Prägnanzende der Skala viel weiter entfernt als bei "normalem" Code.

Darüber hinaus ist in der Standardbibliothek die systemunabhängige Ansicht des Anwendungscodes mit dem zugrunde liegenden System verbunden, wobei alle Arten von compilerspezifischen Dingen verwendet werden, von denen Sie als Anwendungsentwickler am besten Abstand nehmen sollten.

Prost und hth. - Alf
quelle
1
Prägnanz ist ein Aspekt, Leistung ist ein anderer (was auch die Lesbarkeit beeinträchtigen kann): Menschen klagen immer über vermuteten Fettgehalt und Ineffizienzen bei STL-Implementierungen - im Laufe der Jahre wurde fast alles weggeschnitten, aber es gab gelegentlich Kompromisse bei der Lesbarkeit und Eleganz.
Tony Delroy
12

Variablennamen aus dem Grund, dass dies Standardbibliothekscode ist, und es sollten reservierte Namen für Implementierungsdetails in Headern verwendet werden. Folgendes sollte nicht die Standardbibliotheken brechen:

#define mid
#include <algorithm>

Daher können Standardbibliotheksheader daher nicht midals Variablenname verwendet werden _Mid. Die STL war anders - sie war nicht Teil der Sprachspezifikation, sondern wurde definiert als "Hier sind einige Überschriften, verwenden Sie sie wie Sie wollen".

Ihr oder mein Code wäre andererseits ungültig, wenn er _Midals Variablenname verwendet würde, da dies ein reservierter Name ist - die Implementierung darf Folgendes tun:

#define _Mid

wenn es sich so anfühlt.

Layout - meh. Sie haben wahrscheinlich einen Styleguide, sie folgen ihm wahrscheinlich mehr oder weniger. Die Tatsache, dass es nicht zu meinem Styleguide passt (und daher meine Codeüberprüfung nicht bestehen würde), ist nichts für sie.

Operatoren, die schwer zu erarbeiten sind - für wen schwierig? Code sollte für die Leute geschrieben werden, die ihn pflegen, und für GNU / Dinkumware / wer wahrscheinlich nicht will, dass Leute in den Standardbibliotheken loslassen, die nicht rätseln können*--_Next auf einen Blick . Wenn Sie diese Art von Ausdruck verwenden, gewöhnen Sie sich daran, und wenn Sie dies nicht tun, werden Sie es weiterhin schwer finden.

Ich werde Ihnen jedoch sagen, dass operator()Überlastung Kauderwelsch ist. [Bearbeiten: Ich verstehe, es ist ein linearer Kongruenzgenerator, der sehr generisch ausgeführt wird. Wenn der Modul "0" ist, bedeutet dies, dass nur der natürliche Umlauf des arithmetischen Typs verwendet wird.]

Steve Jessop
quelle
2
Aber das bricht natürlich die Standardbibliotheken. Wie können sie definieren, std::pairwann firstnichts geändert wird?
Peter Alexander
@ Peter: d'oh! Ich werde mir einen besseren vorstellen.
Steve Jessop
2
Aaah, ich verstehe, es ist also eine Art Anti-Piraterie / Anti-Umgehungstechnik ... :)
@sonicoder: Ja, oder wenn Sie "Die Stadt und die Stadt" oder "Neverwhere" oder "Harry Potter" gelesen haben, können Zauberer und Muggel koexistieren, ohne ineinander zu stoßen.
Steve Jessop
1
FWIW, RMS hat den Geist der Open-Source-Software mehr oder weniger erfunden (oder zumindest stark entwickelt), und ich bin mir ziemlich sicher, dass ich die Redewendung in glibc verwendet habe. Wenn GNU *--eine vernünftige Operatorkombination in Betracht zieht und Sie dies nicht tun, werden die meisten Leute GNU folgen und sie daher lesen können. Persönlich stört mich das nicht so sehr: Ich denke natürlich nicht, dass Code absichtlich dunkel sein sollte, aber ich denke auch nicht, dass eine so wichtige Komponente wie die Standardbibliotheken in einer so kniffligen Sprache wie C ++ eingesetzt werden sollte Redewendungen zu erfinden und zu verwenden, nur weil Anfänger sie anfangs schwer finden.
Steve Jessop
4

Implementierungen variieren. libc ++ zum Beispiel ist viel augenschonender. Es gibt immer noch ein bisschen Unterstrich. Wie andere angemerkt haben, sind die führenden Unterstriche leider erforderlich. Hier ist die gleiche Funktion in libc ++:

template <class _Compare, class _BidirectionalIterator>
bool
__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
{
    _BidirectionalIterator __i = __last;
    if (__first == __last || __first == --__i)
        return false;
    while (true)
    {
        _BidirectionalIterator __ip1 = __i;
        if (__comp(*--__i, *__ip1))
        {
            _BidirectionalIterator __j = __last;
            while (!__comp(*__i, *--__j))
                ;
            swap(*__i, *__j);
            _STD::reverse(__ip1, __last);
            return true;
        }
        if (__i == __first)
        {
            _STD::reverse(__first, __last);
            return false;
        }
    }
}
Ergosys
quelle
3
Sie werden nur für compilerspezifische Schlüsselwörter und Makros benötigt, nicht für Klassen- / Strukturelemente. obwohl die Konvention darin bestand, ein anderes Präfix und "M_" oder "m_" oder ein "_" anzuhängen, um ein Klassenmitglied im Gegensatz zu einer lokalen oder globalen Variablen zu bezeichnen.
Nun, ich denke, es gibt Raum für Verbesserungen :)
Ergosys
1
Dieser Code unterscheidet sich jedoch nicht wesentlich von dem Code in der ursprünglichen Frage. Es formatiert nur den Einzug neu, verwendet whileanstelle forder Schleifen und schneidet die Debug-Unterstützungsmakros aus. Alle diese Probleme fallen in die Kategorie "Trivial Coding Standard Issues", und keines ist besonders wichtig (mit Ausnahme der Debug-Support-Makros. Wenn Sie jedoch Debugging-Unterstützung wünschen, müssen Sie entweder zwei Implementierungen schreiben oder Makros zum bedingten Kompilieren verwenden es in).
James McNellis
1
Ich behaupte nur, dass es einfacher zu lesen ist, und ein Beispiel für meinen Punkt, dass es besser lesbare Implementierungen gibt. Ich bekomme Kopfschmerzen, wenn ich mir das Beispiel des OP ansehe, aber dieses ist nicht so schlimm.
Ergosys
6
@sonicoder: Nein, die Unterstriche sind für alles erforderlich , aus den Gründen, die @Steve Jessop und andere erwähnt haben: Jeder nicht reservierte Name könnte theoretisch vom Bibliotheksbenutzer als Makro neu definiert werden, wodurch der Standardbibliothekscode beschädigt würde. Sie müssen daher führende Unterstriche verwenden, da dies die Namen sind, die für die Verwendung durch die Implementierung reserviert sind.
Jalf
2

Ich vermute, ein Teil des Grundes ist, dass der Code in der STL stark optimiert ist. Bei der Art des implementierten Codes ist die Leistung viel wichtiger als die Lesbarkeit. Weil sie so weit verbreitet sind, ist es sinnvoll, sie so schnell wie möglich zu machen.

Winston Ewert
quelle
6
Sie können wirklich optimalen Code schreiben und ihn nicht verworren. Die STLs sind nur Variationen der Bibliothek, die vor zwei Jahrzehnten gestartet wurde.
0

Um das hinzuzufügen, was die Leute bereits gesagt haben, ist der Stil, den Sie sehen, der GNU-Stil. Hässlich? Vielleicht liegt das im Auge des Betrachters. Aber es ist ein streng definierter Stil, der den gesamten Code ähnlich aussehen lässt, anstatt sich daran zu gewöhnen.

wilhelmtell
quelle
Nein, das ist kein GNU-Stil. Wie eine spätere Bearbeitung der Frage zeigt, stammt der Code aus der Microsoft std :: lib.
Jonathan Wakely