Le const ici est la cause du problème de compilation. Cependant, ayant moi-même implémenté un arbre AVL, je ne comprends pas pourquoi.
Voici le code:
In file included from /usr/include/c++/7/string:48:0,
from /usr/include/c++/7/bits/locale_classes.h:40,
from /usr/include/c++/7/bits/ios_base.h:41,
from /usr/include/c++/7/ios:42,
from /usr/include/c++/7/ostream:38,
from /usr/include/c++/7/iostream:39,
from demo.cpp:1:
/usr/include/c++/7/bits/stl_function.h: In instantiation of ‘struct std::_Identity<int* const>’:
/usr/include/c++/7/bits/stl_tree.h:2091:29: required from ‘std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = int* const; _Key = int* const; _Val = int* const; _KeyOfValue = std::_Identity<int* const>; _Compare = std::less<int* const>; _Alloc = std::allocator<int* const>]’
/usr/include/c++/7/bits/stl_set.h:510:48: required from ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int* const; _Compare = std::less<int* const>; _Alloc = std::allocator<int* const>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<int* const>; std::set<_Key, _Compare, _Alloc>::value_type = int* const]’
demo.cpp:11:18: required from here
/usr/include/c++/7/bits/stl_function.h:877:7: error: ‘const _Tp& std::_Identity<_Tp>::operator()(const _Tp&) const [with _Tp = int* const]’ cannot be overloaded
operator()(const _Tp& __x) const
^~~~~~~~
/usr/include/c++/7/bits/stl_function.h:873:7: error: with ‘_Tp& std::_Identity<_Tp>::operator()(_Tp&) const [with _Tp = int* const]’
operator()(_Tp& __x) const
Et voici l'erreur:
#include <set>
int main ()
{
int a;
// I want the set to carry the "promise"
// to keep the pointers constant
std::set<int * const> x;
x.insert(&a);
}
Existe-t-il une manière «propre» de procéder? (c'est-à-dire pas une solution de rechange comme créer une "classe pointeur" avec un comparateur pour chaque situation comme celle-ci)
3 Réponses :
Voici un programme simple pour illustrer le problème que vous rencontrez:
int main(int argc, char ** argv)
{
int * const a = NULL;
int * const b = NULL;
b = a; // error: cannot assign to variable 'b' with const-qualified type
}
Notez que c'est une erreur de compilation pour changer la valeur d'une variable de int * const code>, car la variable est considérée en lecture seule.
std :: set a en interne le même problème - il doit modifier les variables du type spécifié, et il ne peut pas faites-le si son type spécifié est en lecture seule.
Changer le type en const int * à la place est probablement ce que vous voulez faire, car ce type permet d'écraser les pointeurs si nécessaire (sans autoriser les modifications des int vers lesquels ils pointent).
Belle explication. L'erreur visual studio throw catch le met également en évidence. Le standard C ++ interdit les conteneurs d'éléments const car l'allocateur
Mais l'élément de l'ensemble n'est-il pas le pointeur? et un ensemble ne modifie jamais les éléments (et je suppose donc que l'implémentation std :: set utilise const sur le type de données quoi qu'il en soit?)
Le set doit stocker ses éléments quelque part - peut-être par exemple dans un tableau interne (ou similaire). Au fur et à mesure que le set est mis à jour, il devra ajouter / supprimer des éléments à / de ce tableau interne. Par conséquent, les éléments du tableau doivent être modifiables ou le set ne peut pas faire son travail.
"Changer le type en const int * à la place est probablement ce que vous voulez faire, car ce type permet aux pointeurs d'être écrasés si nécessaire (tout en ne permettant pas de modifier les entiers vers lesquels ils pointent)." Ce n'est pas ce que je voulais faire. Je réécris un arbre quaternaire et je veux un ensemble
Je ne vois vraiment pas pourquoi vous avez besoin de const class_name * const , travaillez simplement avec const_iterator . Comment empêcher le pointeur d'être modifié en interne dans std :: set affecte votre code?
@ElliottSmith Je veux pouvoir ajouter / supprimer / trouver dans le temps de log (n), mais pas modifier. à mon avis, c'est exactement ce que fait l'ensemble. Pourquoi ne pouvez-vous pas considérer & a comme juste un autre nombre?
@ElliottSmith • Ahh, dans ce cas, un std :: set n'est pas la chose à utiliser.
@Jack, L'exemple de la question est évidemment une grande simplification de mon vrai problème. Les pointeurs sont partagés dans ma classe QTree et je ne veux pas qu'aucune des fonctions ne modifie les pointeurs vers les nœuds, car il existe de nombreuses copies superficielles. Je peux facilement le faire en n'utilisant pas le "const" et en m'assurant à la place de ne rien faire de stupide, mais j'essaie d'utiliser const là où cela convient (c'est-à-dire que les changements de pointeurs ici provoqueraient de faux résultats ou une erreur de segmentation). STL / RBT peut facilement faire cela - donc je ne vois pas pourquoi std :: set ne le peut pas?
@ElliottSmith Je ne suis pas sûr de comprendre votre commentaire - pouvez-vous me donner un exemple de la façon dont un utilisateur pourrait modifier les éléments d'un std :: set ? (AFAICT, vous pouvez insérer ou supprimer des éléments, mais pas les modifier sur place, bien que je puisse manquer quelque chose)
Ok, les pointeurs sont partagés, ce qui est bien. Ensuite, ils sont copiés par valeur dans un std :: set , ce qui est toujours bien. S'ils sont const int * , vous ne pouvez pas modifier la valeur, alors où est votre problème? Je pense qu'il y a un malentendu de base ici, pourriez-vous fournir un scénario de cas réel dans lequel vous en avez besoin pour être const int * const À L'INTÉRIEUR du std :: set ?
@JeremyFriesner: Étant donné qu'il ne déplace aucun élément, un std :: set certainement n'a pas besoin de modifier un T : vous pouvez < i> initialiser un objet const, après tout. Mais il doit être non-const pour d’autres raisons (comme indiqué dans la réponse de marcinj).
Vous ne pouvez pas modifier les éléments stockés dans un std :: set donc le point est sans objet. Il est conçu pour garder les éléments dans un ordre trié et des modifications briseraient cette garantie. C'est pourquoi les itérateurs (à la fois std :: set et std :: set ) les deux renvoient des références const .
Il n'y a aucun moyen de modifier un élément sans mutable (ou const_cast ), auquel cas vous devez toujours garantir que l'ordre reste le même.
J'avais bêtement oublié que std :: set force de toute façon cette const-ness. Merci pour votre réponse.
Mais quand même, si vous voulez utiliser les fonctionnalités const corectness de c ++ et qu'à un moment donné vous n'avez que des pointeurs const vers T disponibles, vous ne pourrez pas utiliser std :: set
Vous pouvez généralement copier un const T dans un T et int * ne fait pas exception.
Dernier point: "Il est conçu pour garder les éléments dans un ordre trié et des modifications briseraient cette garantie." Je voudrais juste dire que ce n'est pas strictement vrai - il vous suffit de garder la clé constante (tout ce qui affecte l'opérateur <) - c'est implémenté comme ça dans std :: map. Cependant, std :: set ne fournit qu'un accès const à l'ensemble de l'élément. Juste un détail technique, mais peut-être pourriez-vous modifier la réponse pour clarifier cela?
@ElliottSmith c'est vrai, j'ai modifié cette possibilité, mais j'aimerais garder le libellé initial tel quel car mutable ou const_cast sont des exceptions à la règle .
Une réponse plus formelle est que std :: set répond aux exigences d'être AllocatorAwareContainer :
Un ensemble satisfait toutes les exigences d'un conteneur, d'un conteneur réversible ([container.requirements]), d'un associatif container ([associative.reqmts]), et d'un conteneur prenant en charge l'allocateur (Tableau 65) .
et dans [allocator.requirements] dans table 33 vous pouvez lire:
T, U, C any cv-unqualified object type ([basic.types])
où T est identique à X :: value_type où X est une classe d'allocateur pour le type T . Cela signifie que std :: allocator ne répond pas aux exigences ci-dessus.
Ceci est vrai pour de nombreux autres conteneurs, par exemple vector, vous pouvez en savoir plus ici: C ++ 11 autorise-t-il le vecteur
[edit[
Visual Studio donne une erreur légèrement plus descriptive:
C: \ Program Files (x86) \ Microsoft Visual Studio 14.0 \ VC \ INCLUDE \ xmemory0 (585): erreur C2338: Le standard C ++ interdit les conteneurs d'éléments const car l'allocateur est mal formé.
avec clang, vous pouvez voir que les premières lignes d'erreur dirigent vers les en-têtes d'allocateur:
../include/c++/5.5.0/ext/new_allocator.h:93:7: erreur : plusieurs surcharges de 'address' instancient sur la même signature '__gnu_cxx :: new_allocator :: const_pointer (__gnu_cxx :: new_allocator :: const_reference) const noexcept' (aka 'int * const * (int * const &) const noexcept') adresse (const_reference __x) ........
const int *! = int * constOui. Je suis conscient?
Je le signale car un
int * constest une valeur qui ne peut pas être modifiée, ce qui implique que toute structure interne dustd :: setne sera pas copy-constructible ou assignable, ce qui va à l'encontre des exigences de toute collection STL. Vous voulez empêcher les modifications des données pointées, mais stocker des pointeurs qui ne peuvent pas être modifiés n'a aucun sens car vous ne travaillez pas directement avec la structure interne.Je suis confus, les éléments d'un ensemble ne peuvent pas être modifiés , qui est le garantir que vous recherchez