Warum nicht Vektor ein STL-Container?

Lesezeit: 9 Minuten

Warum nicht Vektor ein STL Container
P0W

Punkt 18 von Scott Meyers Buch Effektive STL: 50 spezifische Möglichkeiten zur Verbesserung Ihrer Nutzung der Standardvorlagenbibliothek sagt zu vermeiden vector <bool> da es kein STL-Container ist und nicht wirklich hält boolS.

Der folgende Code:

vector <bool> v; 
bool *pb =&v[0];

wird nicht kompiliert, was gegen eine Anforderung von STL-Containern verstößt.

Fehler:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

vector<T>::operator [] Rückgabetyp soll sein T&aber warum ist es ein Sonderfall für vector<bool>?

Was macht vector<bool> wirklich bestehen?

Der Artikel sagt weiter:

deque<bool> v; // is a STL container and it really contains bools

Kann man das alternativ verwenden vector<bool>?

Kann das bitte jemand erklären?

  • Es war ein Designfehler in C++98, der jetzt aus Kompatibilitätsgründen beibehalten wird.

    – Oktalist

    22. Juli 2013 um 18:21 Uhr

  • @g-makulik, Es ist nicht so, dass die Verwendung nicht kompiliert wird, nur dass Sie die Adresse eines Elements nicht in einem Zeiger auf speichern können boolda das Element keine eigene Adresse hat.

    – Chris

    22. Juli 2013 um 18:22 Uhr

  • Vielleicht hilft das: stackoverflow.com/questions/670308/alternative-to-vectorbool

    – Chris

    22. Juli 2013 um 18:24 Uhr

  • @g-makulik std::vector<bool> v; wird kompilieren. &v[0] wird nicht (wobei Adresse eines temporären).

    – Oktalist

    22. Juli 2013 um 18:24 Uhr

  • vector<bool> hat einen schlechten Ruf, aber nicht ganz zu Recht: isocpp.org/blog/2012/11/on-vectorbool

    – TemplateRex

    22. Juli 2013 um 21:01 Uhr

Warum nicht Vektor ein STL Container
Markus B

Aus Gründen der Platzoptimierung ruft der C++-Standard (bis zurück zu C++98) explizit auf vector<bool> als spezieller Standard-Container, bei dem jeder Bool nur ein Bit Platz benötigt und nicht ein Byte, wie es ein normaler Bool tun würde (Implementierung einer Art “dynamischen Bitsets”). Im Gegenzug für diese Optimierung bietet er nicht alle Möglichkeiten und Schnittstellen eines normalen Standardcontainers.

Da Sie in diesem Fall die Adresse eines Bits nicht innerhalb eines Bytes nehmen können, werden Dinge wie operator[] kann a nicht zurückgeben bool& sondern geben stattdessen ein Proxy-Objekt zurück, das es ermöglicht, das bestimmte fragliche Bit zu manipulieren. Da dieses Proxy-Objekt kein bool&Sie können seine Adresse nicht a zuweisen bool* wie Sie es mit dem Ergebnis eines solchen Operator-Aufrufs auf einen “normalen” Container tun könnten. Das wiederum bedeutet das bool *pb =&v[0]; ist kein gültiger Code.

Andererseits deque hat keine solche Spezialisierung aufgerufen, so dass jeder bool ein Byte benötigt und Sie die Adresse des zurückgegebenen Werts nehmen können operator[].

Beachten Sie schließlich, dass die Implementierung der MS-Standardbibliothek (wohl) suboptimal ist, da sie eine kleine Chunk-Größe für deques verwendet, was bedeutet, dass die Verwendung von deque als Ersatz nicht immer die richtige Antwort ist.

  • Haben wir einen anderen Datentyp, für den ein anderer STL-Container spezialisiert oder explizit aufgerufen wird?

    – P0W

    22. Juli 2013 um 18:45 Uhr


  • Gilt dies für C++11 std::array ?

    – Sergio Basurco

    4. Dezember 2015 um 8:06 Uhr

  • @chuckleplant nein, std::array ist lediglich ein Template-Wrapper um ein rohes Array von T[n] mit einigen Hilfsfunktionen wie size()Copy/Move-Semantik und hinzugefügte Iteratoren, um es STL-kompatibel zu machen – und (glücklicherweise) verstößt es nicht gegen seine eigenen Prinzipien (beachte meine Skepsis gegenüber diesen:) ‘Spezialisierung’ für ‘bool‘.

    – Unterstrich_d

    19. Dezember 2015 um 13:53 Uhr


  • Nur eine Kleinigkeit – die Größe von (bool) ist nicht unbedingt ein Byte. stackoverflow.com/questions/4897844/…

    – Uri Raz

    28. Dezember 2019 um 11:38 Uhr

vector<bool> enthält boolesche Werte in komprimierter Form, wobei nur ein Bit für den Wert verwendet wird (und nicht 8, wie bool[] Arrays tun). Es ist nicht möglich, in C++ eine Referenz auf ein Bit zurückzugeben, daher gibt es einen speziellen Hilfstyp, “Bit-Referenz”, der Ihnen eine Schnittstelle zu einem Bit im Speicher bietet und es Ihnen ermöglicht, Standardoperatoren und Umwandlungen zu verwenden.

  • @PrashantSrivastava deque<bool> ist nicht spezialisiert, also ist es buchstäblich nur eine Deque, die Bools enthält.

    – Konrad Rudolf

    22. Juli 2013 um 18:32 Uhr

  • @PrashantSrivastava vector<bool> hat eine spezifische Template-Implementierung. Ich denke, andere STL-Container, wie z deque<bool>nicht, also enthalten sie bool-s wie alle anderen Typen.

    – Iwan Smirnow

    22. Juli 2013 um 18:33 Uhr

  • Hier ist eine Frage, die eine ähnliche Frage in Rust stellt, wo sie Single-Bit-Booleans untersagt haben. stackoverflow.com/questions/48875251/…

    – Andy Boot

    21. Februar 2018 um 15:37 Uhr

1646954412 609 Warum nicht Vektor ein STL Container
TemplateRex

Die Probleme sind das vector<bool> gibt a zurück Proxy-Referenzobjekt anstelle einer echten Referenz, sodass Code im C++98-Stil bool * p = &v[0]; wird nicht kompilieren. Modernes C++11 mit auto p = &v[0]; kann gemacht werden, um zu kompilieren, wenn operator& Auch gibt ein Proxy-Zeigerobjekt zurück. Howard Hinnant hat geschrieben ein Blogbeitrag Einzelheiten zu den algorithmischen Verbesserungen bei der Verwendung solcher Proxy-Referenzen und -Zeiger.

Scott Meyers hat einen langen Gegenstand von 30 Zoll Effektiveres C++ über Proxy-Klassen. Sie können weit kommen schon fast die eingebauten Typen imitieren: für jeden gegebenen Typ Tein Paar Proxys (zB reference_proxy<T> und iterator_proxy<T>) können in dem Sinne miteinander konsistent gemacht werden, dass reference_proxy<T>::operator&() und iterator_proxy<T>::operator*() sind zueinander invers.

Irgendwann muss man jedoch die Proxy-Objekte wieder so abbilden, dass sie sich wie verhalten T* oder T&. Für Iterator-Proxys kann man überladen operator->() und auf die Vorlage zugreifen T‘s-Schnittstelle, ohne die gesamte Funktionalität neu zu implementieren. Für Referenzproxys müssten Sie jedoch überladen operator.()und das ist in aktuellem C++ nicht erlaubt (obwohl Sebastian Redl einen solchen Vorschlag vorgelegt auf der BoostCon 2013). Sie können eine ausführliche Problemumgehung wie a vornehmen .get() Mitglied innerhalb des Referenzproxys oder implementieren Sie alle T‘s-Schnittstelle innerhalb der Referenz (dafür wird getan vector<bool>::bit_reference), aber dies wird entweder die integrierte Syntax verlieren oder benutzerdefinierte Konvertierungen einführen, die keine integrierte Semantik für Typkonvertierungen haben (Sie können höchstens eine benutzerdefinierte Konvertierung pro Argument haben).

TL;DR: Nein vector<bool> ist kein Container, da der Standard eine echte Referenz erfordert, aber es kann dazu gebracht werden, sich fast wie ein Container zu verhalten, zumindest viel näher mit C++11 (auto) als mit C++98.

Viele betrachten die vector<bool> Spezialisierung als Fehler.

In einem Papier „Veraltete Restbibliotheksteile in C++17“

Dazu gibt es einen Vorschlag
Überdenken Sie die teilweise Spezialisierung des Vektors.

Es gibt eine lange Geschichte der bool-Teilspezialisierung von std::vector, die die Containeranforderungen nicht erfüllt, und insbesondere ihre Iteratoren, die nicht die Anforderungen eines Iterators mit wahlfreiem Zugriff erfüllen. Ein früherer Versuch, diesen Container zu verwerfen, wurde für C++11 abgelehnt, N2204.


Einer der Gründe für die Ablehnung ist, dass nicht klar ist, was es bedeuten würde, eine bestimmte Spezialisierung einer Vorlage abzulehnen. Dem könnte mit vorsichtigen Formulierungen begegnet werden. Das größere Problem ist, dass die (gepackte) Spezialisierung von Vektor eine wichtige Optimierung bietet, die Kunden der Standardbibliothek wirklich suchen, aber nicht mehr verfügbar wären. Es ist unwahrscheinlich, dass wir diesen Teil des Standards verwerfen können, bis eine Ersatzeinrichtung vorgeschlagen und akzeptiert wird, wie z N2050. Leider werden der Bibliotheksentwicklungs-Arbeitsgruppe derzeit keine derartigen überarbeiteten Vorschläge unterbreitet.

Sehen Sie sich an, wie es implementiert wird. Die STL baut weitgehend auf Vorlagen auf und daher enthalten die Header den Code, den sie enthalten.

Schauen Sie sich zum Beispiel die an stdc++ Implementierung Hier.

auch interessant obwohl das kein stl konformer bitvektor ist llvm::BitVector von Hier.

die Essenz der llvm::BitVector ist eine verschachtelte Klasse namens reference und geeignetes Überladen des Operators, um das zu machen BitVector verhält sich ähnlich vector mit einigen Einschränkungen. Der folgende Code ist eine vereinfachte Schnittstelle, um zu zeigen, wie BitVector eine aufgerufene Klasse verbirgt reference damit sich die reale Implementierung fast wie ein echtes Array von bool verhält, ohne 1 Byte für jeden Wert zu verwenden.

class BitVector {
public:
  class reference {
    reference &operator=(reference t);
    reference& operator=(bool t);
    operator bool() const;
  };
  reference operator[](unsigned Idx);
  bool operator[](unsigned Idx) const;      
};

dieser Code hier hat die netten Eigenschaften:

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool 
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

Dieser Code hat tatsächlich einen Fehler, versuchen Sie Folgendes auszuführen:

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

wird nicht funktionieren, weil assert( (&b[5] - &b[3]) == (5 - 3) ); wird scheitern (innerhalb llvm::BitVector)

dies ist die sehr einfache llvm-version. std::vector<bool> enthält auch funktionierende Iteratoren. daher der Aufruf for(auto i = b.begin(), e = b.end(); i != e; ++i) wird funktionieren. und auch std::vector<bool>::const_iterator.

Es gibt jedoch immer noch Einschränkungen std::vector<bool> dadurch verhält es sich anders etwas Fälle.

Das kommt von http://www.cplusplus.com/reference/vector/vector-bool/

Vektor von bool Dies ist eine spezialisierte Version von Vektor, die für Elemente vom Typ bool verwendet wird und den Platz optimiert.

Es verhält sich wie die nicht spezialisierte Version von vector, mit den folgenden Änderungen:

  • Der Speicher ist nicht unbedingt ein Array von Bool-Werten, aber die Bibliotheksimplementierung kann den Speicher so optimieren, dass jeder Wert vorhanden ist
    in einem einzigen Bit gespeichert.
  • Elemente werden nicht unter Verwendung des Zuweisungsobjekts konstruiert, sondern ihr Wert wird direkt auf das richtige Bit im internen Speicher gesetzt.
  • Mitgliederfunktion Flip und eine neue Signatur für Mitgliedertausch.
  • Ein spezieller Mitgliedstyp, Referenz, eine Klasse, die auf einzelne Bits im internen Speicher des Containers mit einer Schnittstelle zugreift, die
    emuliert eine Bool-Referenz. Umgekehrt ist der Elementtyp const_reference ein einfacher bool.
  • Die vom Container verwendeten Zeiger- und Iteratortypen sind nicht notwendigerweise weder Zeiger noch konforme Iteratoren, obwohl sie
    soll den größten Teil ihres erwarteten Verhaltens simulieren.

Diese Änderungen bieten eine eigenwillige Schnittstelle zu dieser Spezialisierung und bevorzugen die Speicheroptimierung gegenüber der Verarbeitung (die möglicherweise Ihren Anforderungen entspricht oder nicht). In jedem Fall ist es nicht möglich, das unspezialisierte Template von vector for bool direkt zu instanziieren. Problemumgehungen, um dies zu vermeiden, reichen von der Verwendung eines anderen Typs (char, unsigned char) oder Containers (wie deque), um Wrapper-Typen zu verwenden oder sich weiter auf bestimmte Zuweisungstypen zu spezialisieren.

bitset ist eine Klasse, die eine ähnliche Funktionalität für Bitarrays mit fester Größe bereitstellt.

989250cookie-checkWarum nicht Vektor ein STL-Container?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy