118 votes

Pourquoi le vecteur <bool> pas un conteneur STL?

Scott Meyers de l'Article 18 dit pour éviter vector <bool> que ce n'est pas un conteneur STL et il n'a pas vraiment tenir booléens.

Le code suivant:

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

ne compile pas, en violation de l'exigence de conteneurs STL.

Erreur:

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

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

Qu'est - vector<bool> vraiment consister?

L'Article dit encore:

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

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

Quelqu'un peut-il m'expliquer pourquoi?

135voto

Mark B Points 60200

Pour des raisons d'optimisation, la norme C++ (depuis C++98) explicitement appelle vector<bool> spécial conteneur standard où chaque bool utilise seulement un peu de l'espace plutôt qu'un octet normal bool serait (mise en place d'une sorte de "dynamique bitset"). En échange de cette optimisation, il n'offre pas toutes les fonctionnalités et l'interface d'un conteneur standard.

Dans ce cas, puisque vous ne pouvez pas prendre l'adresse d'un bit d'un octet, des choses comme operator[] ne pouvez pas renvoyer bool& mais au lieu de retourner un objet proxy qui permet de manipuler la donnée binaire en question. Depuis cet objet proxy n'est pas un bool&, vous ne pouvez pas donner son adresse à un bool* comme on pourrait le résultat d'un tel opérateur de faire appel à un "normal" d'un conteneur. À son tour, cela signifie qu' bool *pb =&v[0]; n'est pas un code valide.

D'autre part deque n'ont pas une telle spécialisation appelé de sorte que chaque bool prend un octet, et vous pouvez prendre l'adresse de la valeur de retour de operator[].

Enfin, notez que le ms. de la bibliothèque standard de mise en œuvre est (sans doute) sous-optimale en ce qu'il utilise un petit morceau de la taille pour les deques, ce qui signifie que l'utilisation de deque comme un substitut n'est pas toujours la bonne réponse.

30voto

Ivan Smirnov Points 851

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

27voto

TemplateRex Points 26447

Le problème c'est qu' vector<bool> renvoie un proxy de l'objet de référence au lieu d'une vraie référence, de sorte que C++98 code de style bool * p = &v[0]; ne compile pas. Cependant, C++moderne 11 auto p = &v[0]; peut être faite à la compilation si operator& également retourne un pointeur de proxy de l'objet. Howard Hinnant a écrit un billet de blog détaillant les améliorations algorithmiques lors de l'utilisation de ces proxy références et les pointeurs.

Scott Meyers a un long Article 30 de Plus Efficace C++ sur des classes de proxy. Vous pouvez trouver beaucoup de chemin à presque imiter la builtin types: pour tout type T, une paire de procurations (par exemple, reference_proxy<T> et iterator_proxy<T>) peut être fait cohérents entre eux, dans le sens qu' reference_proxy<T>::operator&() et iterator_proxy<T>::operator*() sont des uns et des autres inverse.

Cependant, à un certain moment, on a besoin de mapper les objets proxy en arrière pour se comporter comme des T* ou T&. Pour itérateur procurations, on peut surcharger operator->() et accéder au modèle T's de l'interface sans réimplanter toutes les fonctionnalités. Cependant, pour référence, les procurations, vous avez besoin de surcharger operator.(), et qui n'est pas autorisé dans le courant de C++ (bien que Sebastian Redl a présenté une proposition sur BoostCon 2013). Vous pouvez faire un verbose travail autour comme un .get() membre à l'intérieur de la référence de proxy, ou de mettre en œuvre tous les de la T's de l'interface à l'intérieur de la référence (c'est ce qui est fait pour vector<bool>::bit_reference), mais ce sera soit perdre la builtin syntaxe ou d'introduire des conversions définies par l'utilisateur qui n'ont pas intégré la sémantique pour les conversions de type (vous pouvez avoir au plus une conversion définie par l'utilisateur par l'argument).

TL;DR: non vector<bool> n'est pas un conteneur parce que la Norme exige une véritable référence, mais il peut être fait pour se comporter presque comme un conteneur, au moins beaucoup plus proche du C++11 (auto) qu'en C++98.

5voto

Alex Points 3973

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

par exemple, regardez le stdc++ mise en œuvre ici.

aussi intéressant, même s'il n'est pas stl conforme vecteur de bits est la llvm::BitVector à partir d' ici.

l'essence de l' llvm::BitVector est une classe imbriquée appelés reference et convenables la surcharge d'opérateur pour faire de l' BitVector se comporte de façon similaire à l' vector avec certaines limitations. Le code ci-dessous est une interface simplifiée pour montrer comment BitVector cache une classe appelée reference pour faire de la mise en œuvre réelle presque se comporter comme un vrai tableau de bool sans l'aide de 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 ici a les plus 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 de le lancer:

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

ne fonctionnera pas parce qu' assert( (&b[5] - &b[3]) == (5 - 3) ); va échouer (dans llvm::BitVector)

c'est très simple llvm version. std::vector<bool> a aussi le travail des itérateurs en elle. 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 limitations en std::vector<bool> qui lui permet de se comporter différemment dans certains cas.

3voto

kvv Points 216

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

Vecteur de bool C'est une version spécialisée de vecteur, qui est utilisé pour les éléments de type bool et optimise pour l'espace.

Il se comporte comme le non spécialisé à la version de vecteur, avec l' modifications suivantes:

  • Le stockage n'est pas nécessairement un tableau de bool valeurs, mais la mise en œuvre de bibliothèque peuvent optimiser le stockage de sorte que chaque valeur est
    stockées dans un seul bit.
  • Les éléments ne sont pas construites à l'aide de l'allocateur de l'objet, mais leur valeur est directement fixé sur le bon de bits dans la mémoire interne.
  • Membre de la fonction flip et une nouvelle signature pour les membres de swap.
  • Un membre spécial de type, référence, une classe qui accède à des bits individuels dans le conteneur de stockage interne avec une interface
    émule un bool référence. À l'inverse, type de membre const_reference est une plaine bool.
  • Le pointeur et l'itérateur les types utilisés par le conteneur ne sont pas nécessairement ni les pointeurs, ni conforme itérateurs, bien qu'ils
    doit simuler la plupart de leur comportement attendu.

Ces changements fournir un excentrique interface de cette spécialisation et favoriser l'optimisation de la mémoire sur le traitement (qui peuvent ou peuvent ne pas convenir à vos besoins). En tout cas, il n'est pas possible d'instancier l' non spécialisées modèle de vecteur pour le type bool directement. Solutions de contournement pour éviter cette plage d'utilisation d'un autre type (char, unsigned char) ou conteneur (comme deque) pour utiliser le wrapper de types ou de se spécialiser pour spécifique de l'allocateur types.

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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X