Pourquoi le vecteur n’est-il pas un conteneur STL?

Point 18 du livre de Scott Meyers Effective STL: 50 façons spécifiques d’améliorer votre utilisation du modèle standard La bibliothèque évite le vector car ce n’est pas un conteneur STL et qu’il ne contient pas vraiment de bools.

Le code suivant:

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

ne comstackra pas, en violation de l’exigence de conteneurs STL.

Erreur:

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

vector::operator [] type de retour du vector::operator [] est supposé être T &, mais pourquoi est-ce un cas particulier pour le vector ?

En quoi consiste réellement le vector ?

L’article dit plus loin:

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

Cela peut-il être utilisé comme une alternative au vector ?

Quelqu’un peut-il s’il vous plaît expliquer cela?

Pour des raisons d’optimisation de l’espace, le standard C ++ (depuis C ++ 98) appelle explicitement vector tant que conteneur standard spécial où chaque booléen utilise un bit d’espace au lieu d’un octet comme le ferait un bool normal ( implémenter une sorte de “bitet dynamic”). En échange de cette optimisation, elle n’offre pas toutes les fonctionnalités et l’interface d’un conteneur standard normal.

Dans ce cas, comme vous ne pouvez pas prendre l’adresse d’un bit dans un octet, des choses telles que operator[] ne peuvent pas renvoyer un bool& renvoient à la place un object proxy qui permet de manipuler le bit en question. Comme cet object proxy n’est pas un bool& , vous ne pouvez pas atsortingbuer son adresse à un bool* comme vous le feriez avec le résultat d’un tel appel opérateur sur un conteneur “normal”. Cela signifie à son tour que bool *pb =&v[0]; n’est pas un code valide.

D’un autre côté, deque ne fait pas appel à une telle spécialisation, donc chaque bool prend un octet et vous pouvez prendre l’adresse de la valeur renvoyée par l’ operator[] .

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

vector contient des valeurs booléennes sous forme compressée en utilisant un seul bit pour la valeur (et non 8 comme le font les tableaux bool []). Il n’est pas possible de renvoyer une référence à un bit dans c ++, il existe donc un type d’aide spécial, “référence de bit”, qui vous fournit une interface avec un peu de mémoire et vous permet d’utiliser des opérateurs et des dissortingbutions standard.

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

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

Cependant, à un moment donné, il faut mapper les objects proxy pour qu’ils se comportent comme T* ou T& . Pour les proxys iterators, on peut surcharger operator->() et accéder à l’interface du template T sans réimplémenter toutes les fonctionnalités. Cependant, pour les mandataires de référence, vous devez surcharger 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 créer un environnement de travail verbeux comme un membre .get() dans le proxy de référence, ou implémenter toutes les interfaces de T dans la référence (c’est ce qui est fait pour vector::bit_reference ), mais cela va soit perdre la syntaxe intégrée, soit introduire des conversions définies par l’utilisateur sans 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 : aucun vector n’est pas un conteneur car le standard nécessite une vraie référence, mais on peut le faire se comporter presque comme un conteneur, au moins beaucoup plus proche avec C ++ 11 (auto) qu’en C ++ 98.

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, utilisée pour les éléments de type bool et optimisée pour l’espace.

Il se comporte comme la version non spécialisée du vecteur, 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é dans un seul bit.
  • Les éléments ne sont pas construits à l’aide de l’object allocateur, mais leur valeur est directement définie sur le bit approprié dans le stockage interne.
  • Fonction flip membre et une nouvelle signature pour le swap membre.
  • Un type de membre spécial, référence, une classe qui accède à des bits individuels dans le stockage interne du conteneur avec une interface qui
    émule une référence bool. Inversement, le type de membre const_reference est un simple bool.
  • Les types de pointeur et d’iterator utilisés par le conteneur ne sont pas nécessairement des pointeurs ni des iterators conformes, bien qu’ils
    doit simuler la plupart de leurs comportements attendus.

Ces modifications offrent 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 vecteur pour bool. Solutions de contournement pour éviter cette plage d’utiliser un type différent (caractère, caractère non signé) ou conteneur (comme deque) pour utiliser des types d’encapsuleur ou pour vous spécialiser davantage pour des types d’allocateur spécifiques.

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

Regardez comment il est implémenté. la STL se construit largement sur les modèles et par conséquent les en-têtes contiennent le code qu’ils font.

par exemple, regardez l’ implémentation stdc ++ ici .

aussi intéressant même si pas un vecteur de bit conforme à stl est le llvm :: BitVector d’ ici .

l’essence de llvm::BitVector est une classe nestede appelée reference et une surcharge d’opérateur appropriée pour que le BitVector se comporte comme un vector avec certaines limitations. Le code ci-dessous est une interface simplifiée pour montrer comment BitVector cache une classe appelée reference pour que la mise en œuvre réelle se comporte presque comme un tableau réel de bool 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 les propriétés suivantes:

 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 effectivement un défaut, essayez de courir:

 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) ); va échouer (dans llvm::BitVector )

c’est la version très simple de llvm. std::vector contient également des iterators. ainsi l’appel for(auto i = b.begin(), e = b.end(); i != e; ++i) fonctionnera. et aussi std::vector::const_iterator .

Cependant, std::vector comporte toujours des limitations qui le font se comporter différemment dans certains cas.

Beaucoup considèrent que la spécialisation vector est une erreur.

Dans un article “Observer les pièces de la bibliothèque vestigiale en C ++ 17”
Il est proposé de reconsidérer la spécialisation partielle des vecteurs .

Il y a eu une longue histoire de la spécialisation bool partielle de std :: vector ne satisfaisant pas les exigences du conteneur, et en particulier, ses iterators ne satisfaisaient pas aux exigences d’un iterator à access aléatoire. Une précédente tentative de dépréciation de 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 cela signifierait de déconseiller une spécialisation particulière d’un modèle. Cela pourrait être abordé avec une formulation prudente. Le plus gros problème est que la spécialisation (empaquetée) de vector offre une optimisation importante que les clients de la bibliothèque standard recherchent réellement, mais qui ne serait plus disponible. Il est peu probable que nous soyons en mesure de déprécier 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 n’est actuellement proposée au groupe de travail sur l’évolution de la bibliothèque.