Perché il vettore <bool> non è un contenitore STL?

Question

Articolo 18 del libro di Scott Meyers STL effettivo: 50 modi specifici per migliorare l'utilizzo della libreria di modelli standard dice di evitare vector <bool> poiché non è un contenitore STL e in realtà non contiene i bool.

Il codice seguente:

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

non si compila, violando requisito di contenitori STL.

Errore:

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

vector<T>::operator [] tipo di ritorno si suppone che sia T &, ma perché si tratta di un caso speciale per vector<bool>?

In cosa consiste veramente lo vector<bool>?

La voce dice ancora:

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

questo può essere usato come alternativa al vector<bool>?

Qualcuno può spiegare questo?

Answer 1

Per motivi di spazio-ottimizzazione, lo standard C++ (fin dal C++ 98) chiama esplicitamente vector<bool> come un contenitore standard speciale in cui ogni bool usa solo un po ' di spazio invece di un byte come farebbe un bool normale (implementando una sorta di "bitset dinamico"). In cambio di questa ottimizzazione non offre tutte le funzionalità e l'interfaccia di un normale contenitore standard.

In questo caso, dal momento che non si può prendere l'indirizzo di un bit all'interno di un byte, cose come operator[] non possono restituire un bool& ma invece restituire un oggetto proxy che permette di manipolare il bit specifico in questione. Poiché questo oggetto proxy non è un bool&, non è possibile assegnare il proprio indirizzo a un bool* come si potrebbe con il risultato di tale chiamata operatore su un contenitore "normale". A sua volta ciò significa che bool *pb =&v[0]; non è un codice valido.

D'altra parte deque non ha tale specializzazione chiamato fuori in modo che ogni bool prende un byte e si può prendere l'indirizzo del valore di ritorno da operator[].

Infine, l'implementazione della libreria standard MS è (probabilmente) subottimale in quanto utilizza una piccola dimensione del blocco per deques, il che significa che l'utilizzo di deque come sostituto non è sempre la risposta corretta.

Answer 2

vector<bool> contiene valori booleani in forma compressa utilizzando solo un bit per il valore (e non 8 come fanno gli array bool []). Non è possibile restituire un riferimento a un bit in C++, quindi esiste un tipo di helper speciale, "riferimento bit", che fornisce un'interfaccia per alcuni bit in memoria e consente di utilizzare operatori e cast standard.

Answer 3

Questo viene da 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

Guarda come è implementato. l'STL si basa ampiamente sui modelli e quindi le intestazioni contengono il codice che fanno.

per esempio un'occhiata alla STDC++ implementazione here.

anche interessante anche se non un vettore di bit conforme stl è il llvm :: BitVector da here.

l'essenza del llvm::BitVector è una classe nidificata denominata reference ed esercente adatto sovraccarico per rendere il BitVector comporta simile a vector con alcune limitazioni. Il codice sotto è un'interfaccia semplificata per mostrare come BitVector nasconde una classe chiamata reference per far sì che l'implementazione reale si comporti quasi come una vera matrice di bool senza usare 1 byte per ogni valore.

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

questo codice ha qui le belle proprietà:

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. 

Questo codice in realtà ha un difetto, provare a eseguire:

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

non funzionerà perché assert((&b[5] - &b[3]) == (5 - 3)); falliranno (entro llvm::BitVector)

questa è la versione molto semplice di llvm. std::vector<bool> ha anche degli iteratori funzionanti. quindi la chiamata for(auto i = b.begin(), e = b.end(); i != e; ++i) funzionerà. e anche std::vector<bool>::const_iterator.

Tuttavia ci sono ancora limitazioni in std::vector<bool> che lo fanno comportarsi in modo diverso in alcuni casi.

Answer 5

Il problema è che vector<bool> restituisce un oggetto proxy di riferimento anziché un vero riferimento, in modo tale che C++ 98 codice di stile bool * p = &v[0]; non viene compilato. Tuttavia, è possibile compilare il C++ 11 moderno con auto p = &v[0]; se operator&returns a proxy pointer object. Howard Hinnant ha scritto a blog post specificando i miglioramenti algoritmici quando si utilizzano tali riferimenti e puntatori proxy.

Scott Meyers ha un lungo articolo 30 in More Effective C++ sulle classi proxy. È possibile percorso una lunga strada per quasi mimare i tipi built: per qualsiasi tipo T, una coppia di proxy (ad esempio reference_proxy<T> e iterator_proxy<T>) può essere fatta tra loro coerenti, nel senso che reference_proxy<T>::operator&() e iterator_proxy<T>::operator*() sono reciprocamente inversa.

Tuttavia, a un certo punto è necessario eseguire il mapping degli oggetti proxy per comportarsi come T* o T&. Per i proxy iteratori, è possibile sovraccaricare lo operator->() e accedere all'interfaccia del modello T senza reimplementare tutte le funzionalità. Tuttavia, per i proxy di riferimento, è necessario sovraccaricare operator.() e ciò non è consentito nell'attuale C++ (sebbene Sebastian Redl presented such a proposal su BoostCon 2013).Puoi fare un prolisso verboso come un membro di .get() all'interno del proxy di riferimento, o implementare tutta l'interfaccia di T all'interno del riferimento (questo è ciò che viene fatto per vector<bool>::bit_reference), ma questo perderà la sintassi incorporata o introdurrà conversioni definite che non hanno una semantica integrata per le conversioni di tipo (puoi avere al massimo una conversione definita dall'utente per argomento).

TL; DR: no vector<bool> non è un contenitore, perché il Principio richiede un vero e proprio riferimento, ma può essere fatto a comportarsi quasi come un contenitore, almeno molto più stretto con C++ 11 (auto) che in C++ 98.

Answer 6

Molti considerano la specializzazione vector<bool> un errore.

In un documento "Deprecating Vestigial Library Parts in C++17"
c'è una proposta per riconsiderare vettore Specializzazione parziale.

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.