Pourquoi le vecteur <bool> :: const_reference de libc ++ n'est-il pas booléen?

92

Section 23.3.7 Classe vector<bool>[vector.bool], paragraphe 1 stipule:

template <class Allocator> class vector<bool, Allocator> {
public:
    // types:
    typedef bool              const_reference;
    ...

Cependant, ce programme ne parvient pas à se compiler lors de l'utilisation de libc ++:

#include <vector>
#include <type_traits>

int
main()
{
    static_assert(std::is_same<std::vector<bool>::const_reference, bool>{}, "?");
}

De plus, je note que la norme C ++ a été cohérente dans cette spécification depuis C ++ 98. Et je note en outre que libc ++ n'a toujours pas suivi cette spécification depuis la première introduction de libc ++.

Quelle est la motivation de cette non-conformité?

Howard Hinnant
la source

Réponses:

99

La motivation de cette extension, détectable par un programme conforme, et donc non conforme, est de faire vector<bool>se comporter davantage vector<char>par rapport aux références (const et autres).

introduction

Depuis 1998, vector<bool>a été ridiculisé comme «pas tout à fait un conteneur». Le LWG 96 , l'une des toutes premières questions du LWG, a lancé le débat. Aujourd'hui, 17 ans plus tard, vector<bool>reste largement inchangé.

Cet article donne des exemples spécifiques sur la façon dont le comportement de vector<bool>diffère de toutes les autres instanciations de vector, ce qui nuit au code générique. Cependant, le même article discute longuement des très belles propriétés de performance que vector<bool>peuvent avoir si elles sont correctement mises en œuvre.

Résumé : ce vector<bool>n'est pas un mauvais conteneur. C'est en fait très utile. Il a juste un mauvais nom.

Retour à const_reference

Comme présenté ci-dessus et détaillé ici , ce qui est mauvais, vector<bool>c'est qu'il se comporte différemment dans le code générique des autres vectorinstanciations. Voici un exemple concret:

#include <cassert>
#include <vector>

template <class T>
void
test(std::vector<T>& v)
{
    using const_ref = typename std::vector<T>::const_reference;
    const std::vector<T>& cv = v;
    const_ref cr = cv[0];
    assert(cr == cv[0]);
    v[0] = 1;
    assert(true == cv[0]);
    assert(cr == cv[0]);  // Fires!
}

int
main()
{
    std::vector<char> vc(1);
    test(vc);
    std::vector<bool> vb(1);
    test(vb);
}

La spécification standard indique que l'assertion marquée // Fires!se déclenchera, mais uniquement lorsqu'elle testest exécutée avec un vector<bool>. Lorsqu'il est exécuté avec un vector<char>(ou n'importe quel vectorautre boolsi une valeur non par défaut appropriée Test attribuée), le test réussit.

L'implémentation libc ++ cherchait à minimiser les effets négatifs de vector<bool>se comporter différemment dans le code générique. Une chose qu'il a faite pour y parvenir est de créer vector<T>::const_referenceune référence proxy , tout comme celle spécifiée vector<T>::reference, sauf que vous ne pouvez pas l'attribuer via elle. Autrement dit, sur libc ++, vector<T>::const_referenceest essentiellement un pointeur vers le bit à l'intérieur de vector, au lieu d'une copie de ce bit.

Sur libc ++, ce qui précède testpasse pour les deux vector<char>et vector<bool>.

A quel prix?

L'inconvénient est que cette extension est détectable, comme le montre la question. Cependant, très peu de programmes se soucient réellement du type exact de cet alias, et davantage de programmes se soucient du comportement.

Quelle est la motivation de cette non-conformité?

Pour donner au client libc ++ un meilleur comportement en code générique, et peut-être après des tests sur le terrain suffisants, proposez cette extension à un futur standard C ++ pour l'amélioration de l'ensemble de l'industrie C ++.

Une telle proposition pourrait prendre la forme d'un nouveau conteneur (par exemple bit_vector) qui a à peu près la même API que celle d'aujourd'hui vector<bool>, mais avec quelques mises à niveau telles que celles const_referencedécrites ici. Suivi de la dépréciation (et éventuellement de la suppression) de la vector<bool>spécialisation. bitsetpourrait également utiliser une petite mise à jour dans ce département, par exemple add const_reference, et un ensemble d'itérateurs.

Autrement dit, le recul bitsetest de vector<bool>(qui devrait être renommé bit_vector- ou autre), comme arrayest vector. Et l'analogie devrait être vrai que l' on parle ou pas boolcomme value_typede vectoret array.

Il existe plusieurs exemples de fonctionnalités C ++ 11 et C ++ 14 qui ont commencé comme des extensions dans libc ++. C'est ainsi que les normes évoluent. Une expérience concrète positive démontrée sur le terrain a une forte influence. Les standards sont un groupe conservateur lorsqu'il s'agit de modifier les spécifications existantes (comme elles devraient l'être). Deviner, même si vous êtes sûr de bien deviner, est une stratégie risquée pour faire évoluer une norme internationalement reconnue.

Howard Hinnant
la source
1
Question: le projet de proposition récent sur les itérateurs de proxy par @EricNiebler pourrait-il / voudrait-il légitimer d'une manière ou d'une autre les extensions libc ++ et mettre vector<bool>sur des bases plus de première classe?
TemplateRex
Remarque: je préférerais avoir un vector_bool<Alloc>et un array_bool<N>pour représenter les versions compactées (y compris les itérateurs de proxy à accès aléatoire itérant tous les bits) de vector<bool, Alloc>et array<bool, N>. Cependant, bitset<N>(et c'est cousin boost::dynamic_bitset<Alloc>) représentent une abstraction différente: à savoir les versions compressées de std::set<int>. Je voudrais donc avoir, disons, bit_array<N>et bit_vector<Alloc>être les successeurs de la franchise bitset, avec des itérateurs bidirectionnels appropriés (itérant sur les 1 bits, plutôt que sur tous les bits). Que pensez-vous de ceci?
TemplateRex
5
Mon projet de proposition sur les itérateurs de proxy ferait vector<bool>un conteneur à accès aléatoire conforme à la norme std. Cela ne ferait pas vector<bool>une bonne idée. :-) Je suis d'accord avec Howard. Cela aurait dû être appelé autre chose.
Eric Niebler
1
Pourquoi n'y a-t-il pas un moyen de désactiver les extensions libc ++ et d'obtenir un comportement strictement conforme? (Je ne demande même pas de faire de la conformité la valeur par défaut, juste un moyen de désactiver les extensions de libc ++ pour pouvoir écrire du code portable). Comme vous le savez, j'ai été mordu par les extensions de tuple libc ++ dans le passé, et récemment mordu par l'extension bitset :: const_reference.
gnzlbg
5
@gnzlbg: Une quantité limitée de ressources économiques et temporelles était disponible pour le développement initial de libc ++. Par la suite, la mise en œuvre était vouée à ne pas satisfaire tous les utilisateurs. Compte tenu des ressources disponibles, des compromis d'ingénierie ont été faits dans le but de maximiser le nombre d'utilisateurs satisfaits, de maximiser les avantages pour l'ensemble de la communauté C ++. Désolé pour votre expérience. Je note que les extensions de tuple que vous avez enfreintes se trouvent maintenant dans le document de travail actuel de C ++ 1z. Sur cette question, vous vous êtes sacrifié sans le savoir pour que beaucoup puissent en bénéficier, et ceux-là vous doivent beaucoup de gratitude.
Howard Hinnant