Warum ist Vektor <bool> kein STL-Container?

Question

Artikel 18 von Scott Meyers Buch Effektive STL: 50 spezifische Möglichkeiten, Ihre Verwendung der Standard-Template-Bibliothekvector <bool> zu vermeiden, da es kein STL-Container ist und es nicht wirklich Bools hält.

Der folgende Code:

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

wird nicht kompiliert, Anforderung von STL-Containern zu verletzen.

Fehler:

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

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

Was besteht eigentlich aus vector<bool>?

Der Artikel sagt weiter:

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

Kann dies als Alternative zu vector<bool> verwendet werden?

Kann jemand bitte dies erklären?

Answer 1

Aus Platzoptimierung Gründen der C++ Standard (so weit zurück wie C++ 98) nennt explizit vector<bool> als spezielle Standardcontainer, wo jeder bool nur ein Bit verwendet mehr Platz als ein Byte als normales bool (würde eine Art "dynamisches Bitset" implementieren). Im Gegenzug für diese Optimierung bietet es nicht alle Möglichkeiten und Schnittstellen eines normalen Standardcontainers.

In diesem Fall können Dinge wie operator[] nicht bool& zurückgeben, aber Sie können stattdessen ein Proxy-Objekt zurückgeben, das das betreffende Bit manipulieren kann, da Sie die Adresse eines Bits innerhalb eines Bytes nicht übernehmen können. Da dieses Proxy-Objekt kein bool& ist, können Sie seine Adresse nicht einer zuweisen, wie Sie mit dem Ergebnis eines solchen Aufrufs eines "normalen" Containers aufrufen könnten. Dies bedeutet wiederum, dass bool *pb =&v[0]; kein gültiger Code ist.

Auf der anderen Seite deque hat keine solche Spezialisierung aufgerufen, so dass jedes bool ein Byte nimmt und Sie können die Adresse des Werts von operator[] nehmen.

Schließlich ist die Implementierung der MS-Standardbibliothek (wohl) suboptimal, 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.

Answer 2

vector<bool> enthält boolesche Werte in komprimierter Form mit nur einem Bit für Wert (und nicht 8 wie Bool [] Arrays tun). Es ist nicht möglich, einen Verweis auf ein Bit in C++ 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.

Answer 3

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

Vector of bool This is a specialized version of vector, which is used for elements of type bool and optimizes for space.

It behaves like the unspecialized version of vector, with the following changes:

• The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is
  stored in a single bit.
• Elements are not constructed using the allocator object, but their value is directly set on the proper bit in the internal storage.
• Member function flip and a new signature for member swap.
• A special member type, reference, a class that accesses individual bits in the container's internal storage with an interface that
  emulates a bool reference. Conversely, member type const_reference is a plain bool.
• The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they
  shall simulate most of their expected behavior.

These changes provide a quirky interface to this specialization and favor memory optimization over processing (which may or may not suit your needs). In any case, it is not possible to instantiate the unspecialized template of vector for bool directly. Workarounds to avoid this range from using a different type (char, unsigned char) or container (like deque) to use wrapper types or further specialize for specific allocator types.

bitset is a class that provides a similar functionality for fixed-size arrays of bits.

Answer 4

Schauen Sie sich an, wie es implementiert ist. Die STL baut stark auf Vorlagen auf, und daher enthalten die Header den Code, den sie ausführen.

zum Beispiel betrachten Sie die stdC++ Implementierung here.

auch interessant, obwohl nicht ein STL-konforme Bit-Vektor ist die llvm :: BitVector von here.

das Wesen der llvm::BitVector ist eine verschachtelte Klasse Überlastung reference und geeigneten Operator genannt ähnlich die BitVector verhält sich mit einigen Einschränkungen zu vector zu machen. Der folgende Code ist eine vereinfachte Schnittstelle, um zu zeigen, wie BitVector eine Klasse mit dem Namen reference versteckt, damit sich die reale Implementierung fast wie ein reales Bool-Array verhält, ohne dass für jeden Wert 1 Byte verwendet wird.

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;  
}; 

dies hier Code, um die schönen Eigenschaften hat:

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 tatsächlich einen Fehler hat, versuchen zu laufen:

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)); (innerhalb llvm::BitVector scheitern)

dies ist die sehr einfache llvm-version. std::vector<bool> hat auch funktionierende Iteratoren. so funktioniert der Anruf for(auto i = b.begin(), e = b.end(); i != e; ++i). und auch std::vector<bool>::const_iterator.

Allerdings gibt es immer noch Einschränkungen in std::vector<bool>, die es in einige Fällen anders verhalten.

Answer 5

Die Probleme sind, dass vector<bool> gibt ein Proxy-Referenzobjekt statt eine echte Referenz, so dass C++ 98 Artcode bool * p = &v[0]; wird nicht kompiliert. Moderne C++ 11 mit auto p = &v[0]; kann jedoch kompiliert werden, wenn auch returns a proxy pointer object. Howard Hinnant hat geschrieben a blog post detailliert die algorithmischen Verbesserungen bei der Verwendung solcher Proxy-Referenzen und Zeiger.

Scott Meyers hat eine lange Artikel 30 in More Effective C++ über Proxy-Klassen. Sie können einen langen Weg zu kommen fast die eingebauten Typen nachahmen: für einen bestimmten Typ T, ein Paar von Proxys (z reference_proxy<T> und iterator_proxy<T>) können im Sinne miteinander in Einklang gebracht werden, dass reference_proxy<T>::operator&() und iterator_proxy<T>::operator*() jeder inversen des anderen sind.

Allerdings muss man die Proxy-Objekte irgendwann so abbilden, dass sie sich wie T* oder T& verhalten. Bei Iterator-Proxies kann man operator->() überlasten und auf die Schnittstelle des Templates T zugreifen, ohne die gesamte Funktionalität neu zu implementieren. Für Referenzproxys müssten Sie jedoch operator.() überladen, und das ist im aktuellen C++ nicht erlaubt (obwohl Sebastian Redl presented such a proposal auf BoostCon 2013).Sie können einen ausführlichen Workaround wie einen .get() Member innerhalb des Referenzproxys erstellen oder alle Schnittstellen von T in die Referenz implementieren (dies wird für vector<bool>::bit_reference getan), aber dadurch wird entweder die eingebaute Syntax verloren oder es werden Definierte Konvertierungen, die keine integrierte Semantik für Typkonvertierungen haben (Sie können höchstens eine benutzerdefinierte Konvertierung pro Argument haben).

TL; DR: keine vector<bool> ist kein Container, da der Standard eine echte Referenz erfordert, aber es kann fast wie ein Behälter, zumindest viel näher mit C++ 11 (auto) verhalten gemacht wird als in C++ 98.

Answer 6

Viele betrachten die vector<bool> Spezialisierung als einen Fehler.

In einem Papier "Deprecating Vestigial Library Parts in C++17"
Es gibt einen Vorschlag zu Vektor Teil Spezialisierung Reconsider.

There has been a long history of the bool partial specialization of std::vector not satisfying the container requirements, and in particular, its iterators not satisfying the requirements of a random access iterator. A previous attempt to deprecate this container was rejected for C++11, N2204 .

---

One of the reasons for rejection is that it is not clear what it would mean to deprecate a particular specialization of a template. That could be addressed with careful wording. The larger issue is that the (packed) specialization of vector offers an important optimization that clients of the standard library genuinely seek, but would not longer be available. It is unlikely that we would be able to deprecate this part of the standard until a replacement facility is proposed and accepted, such as N2050 . Unfortunately, there are no such revised proposals currently being offered to the Library Evolution Working Group.