Pourquoi vector <bool> n'est-il pas un conteneur STL?

L'article 18 du livre de Scott Meyers Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library dit d'éviter vector <bool>car ce n'est pas un conteneur STL et il ne contient pas vraiment de bools.

Le code suivant:

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

ne compilera pas, violant une exigence des conteneurs STL.

Erreur:

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

vector<T>::operator []le type de retour est censé être T&, mais pourquoi est-ce un cas particulier vector<bool>?

En quoi vector<bool>consiste vraiment?

L'article dit en outre:

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

Cela peut-il être utilisé comme alternative à vector<bool>?

Quelqu'un peut-il expliquer cela?

Pour des raisons d'optimisation de l'espace, le standard C ++ (aussi loin que C ++ 98) appelle explicitement vector<bool>un conteneur standard spécial où chaque booléen n'utilise qu'un bit d'espace plutôt qu'un octet comme le ferait un bool normal (implémentation d'une sorte de "jeu de bits dynamique"). En échange de cette optimisation, il n'offre pas toutes les capacités et l'interface d'un conteneur standard normal.

Dans ce cas, puisque vous ne pouvez pas prendre l'adresse d'un bit dans un octet, des choses telles que operator[]ne peuvent pas retourner un bool&mais à la place renvoient un objet proxy qui permet de manipuler le bit particulier en question. Puisque cet objet proxy n'est pas un bool&, vous ne pouvez pas attribuer son adresse à un bool*comme vous le pourriez avec le résultat d'un tel appel d'opérateur sur un conteneur "normal". À son tour, cela signifie que ce bool *pb =&v[0];n'est pas un code valide.

D'un autre côté, dequeaucune spécialisation de ce type n'est appelée, donc chaque booléen prend un octet et vous pouvez prendre l'adresse de la valeur renvoyée operator[].

Enfin, notez que l'implémentation de la bibliothèque standard MS est (sans doute) sous-optimale en ce qu'elle utilise une petite taille de bloc pour les deques, ce qui signifie que l'utilisation de deque comme substitut n'est pas toujours la bonne réponse.

vector<bool>contient des valeurs booléennes sous forme compressée en n'utilisant qu'un seul bit pour value (et non 8 comme le font les tableaux bool []). Il n'est pas possible de renvoyer une référence à un bit en c ++, il existe donc un type d'aide spécial, "bit reference", qui vous fournit une interface vers un bit en mémoire et vous permet d'utiliser des opérateurs et des transtypages standard.

Le problème est que vector<bool>renvoie un objet de référence proxy au lieu d'une vraie référence, de sorte que le code de style C ++ 98 bool * p = &v[0];ne se compile pas. Cependant, le C ++ 11 moderne avec auto p = &v[0];peut être fait pour compiler s'il renvoieoperator& également un objet pointeur proxy . Howard Hinnant a écrit un article de blog détaillant les améliorations algorithmiques lors de l'utilisation de ces références et pointeurs proxy.

Scott Meyers a un long Item 30 dans More Effective C ++ sur les classes proxy. Vous pouvez faire un long chemin pour imiter presque les types intégrés: pour tout type donné T, une paire de proxies (par exemple reference_proxy<T>et iterator_proxy<T>) peut être rendue mutuellement cohérente dans le sens où reference_proxy<T>::operator&()et iterator_proxy<T>::operator*()sont l'inverse de l'autre.

Cependant, à un moment donné, il faut mapper les objets proxy pour qu'ils se comportent comme T*ou T&. Pour les proxies d'itérateur, on peut surcharger operator->()et accéder à l' Tinterface du modèle sans réimplémenter toutes les fonctionnalités. Cependant, pour les proxys de référence, vous auriez besoin d'une surcharge operator.(), ce qui n'est pas autorisé dans le C ++ actuel (bien que Sebastian Redl ait présenté une telle proposition sur BoostCon 2013). Vous pouvez faire un contournement détaillé comme un .get()membre à l'intérieur du proxy de référence, ou implémenter toute Tl'interface de dans la référence (c'est ce qui est fait pourvector<bool>::bit_reference), mais cela perdra la syntaxe intégrée ou introduira des conversions définies par l'utilisateur qui n'ont pas de sémantique intégrée pour les conversions de type (vous pouvez avoir au plus une conversion définie par l'utilisateur par argument).

TL; DR : no vector<bool>n'est pas un conteneur car le Standard nécessite une vraie référence, mais il peut être fait pour se comporter presque comme un conteneur, au moins beaucoup plus proche avec C ++ 11 (auto) qu'en C ++ 98.

Beaucoup considèrent la vector<bool>spécialisation comme une erreur.

Dans un article "Deprecating Vestigial Library Parts in C ++ 17",
il y a une proposition de reconsidérer la spécialisation partielle vectorielle .

Il y a eu une longue histoire de la spécialisation partielle booléenne de std :: vector ne satisfaisant pas les exigences du conteneur, et en particulier, ses itérateurs ne satisfaisant pas les exigences d'un itérateur à accès aléatoire. Une tentative précédente de désapprouver ce conteneur a été rejetée pour C ++ 11, N2204 .

L'une des raisons du rejet est qu'il n'est pas clair ce que signifierait la désapprobation d'une spécialisation particulière d'un modèle. Cela pourrait être résolu avec une formulation prudente. Le problème le plus important est que la spécialisation (emballée) du vecteur offre une optimisation importante que les clients de la bibliothèque standard recherchent véritablement, mais ne seraient plus disponibles. Il est peu probable que nous puissions annuler cette partie de la norme jusqu'à ce qu'une installation de remplacement soit proposée et acceptée, telle que N2050 . Malheureusement, aucune proposition révisée de ce type n’est actuellement proposée au Groupe de travail sur l’évolution des bibliothèques.

Regardez comment il est mis en œuvre. la STL s'appuie largement sur des modèles et, par conséquent, les en-têtes contiennent le code qu'ils contiennent.

par exemple regarder à l' stdc ++ mise en œuvre ici .

également intéressant, même si ce n'est pas un vecteur de bits conforme stl, est le llvm :: BitVector d' ici .

L'essence de la llvm::BitVectorest une classe imbriquée appelée referenceet une surcharge d'opérateur appropriée pour rendre le BitVectorcomportement similaire à vectoravec certaines limitations. Le code ci-dessous est une interface simplifiée pour montrer comment BitVector cache une classe appelée referencepour que l'implémentation réelle se comporte presque comme un vrai tableau de booléens sans utiliser 1 octet pour chaque valeur.

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

ce code a ici les belles propriétés:

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.

Ce code a en fait un défaut, essayez d'exécuter:

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

ne fonctionnera pas car assert( (&b[5] - &b[3]) == (5 - 3) );échouera (à l'intérieur llvm::BitVector)

c'est la version llvm très simple. std::vector<bool>contient également des itérateurs fonctionnels. ainsi l'appel for(auto i = b.begin(), e = b.end(); i != e; ++i)fonctionnera. et aussi std::vector<bool>::const_iterator.

Cependant, il y a encore des limites std::vector<bool>qui font qu'il se comporte différemment dans certains cas.

Cela vient de http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool Il s'agit d'une version spécialisée de vector, qui est utilisée pour les éléments de type bool et optimise pour l'espace.

Il se comporte comme la version non spécialisée de vector, avec les modifications suivantes:

• Le stockage n'est pas nécessairement un tableau de valeurs booléennes, mais l'implémentation de la bibliothèque peut optimiser le stockage afin que chaque valeur soit
  stockée dans un seul bit.
• Les éléments ne sont pas construits à l'aide de l'objet allocateur, mais leur valeur est directement définie sur le bit approprié dans la mémoire interne.
• Flip de fonction de membre et une nouvelle signature pour l'échange de membre
• Un type de membre spécial, une référence, une classe qui accède à des bits individuels dans la mémoire interne du conteneur avec une interface qui
  émule une référence booléenne. Inversement, le type de membre const_reference est un simple booléen.
• Les types de pointeur et d'itérateur utilisés par le conteneur ne sont pas nécessairement ni des pointeurs ni des itérateurs conformes, bien qu'ils
  simulent la plupart de leur comportement attendu.

Ces changements fournissent une interface originale à cette spécialisation et favorisent l'optimisation de la mémoire par rapport au traitement (qui peut ou non répondre à vos besoins). Dans tous les cas, il n'est pas possible d'instancier directement le modèle non spécialisé de vector for bool. Solutions de contournement pour éviter que cette plage n'utilise un type différent (char, unsigned char) ou un conteneur (comme deque) pour utiliser des types de wrapper ou se spécialiser davantage pour des types d'allocateurs spécifiques.

bitset est une classe qui fournit une fonctionnalité similaire pour les tableaux de bits de taille fixe.