Pourquoi std::set semble-t-il forcer l'utilisation d'un const_iterator ?

Question

Considérons le programme simple ci-dessous, qui tente d'itérer à travers les valeurs d'un ensemble en utilisant des références NON-const aux éléments de celui-ci :

#include <set>
#include <iostream>

class Int
{
public:
   Int(int value) : value_(value) {}
   int value() const { return value_; }
   bool operator<(const Int& other) const { return value_ < other.value(); }
private:
   int value_;
};

int
main(int argc, char** argv) {
   std::set<Int> ints;
   ints.insert(10);
   for (Int& i : ints) {
      std::cout << i.value() << std::endl;
   }
   return 0;
}

En compilant ceci, j'obtiens une erreur de gcc :

test.c: In function ‘int main(int, char**)’:
test.c:18:18: error: invalid initialization of reference of type ‘Int&’ from expression of type ‘const Int’  
for (Int& i : ints) {  
              ^  

Oui, je sais que je n'essaie pas réellement de modifier les éléments dans la boucle for. Mais le fait est que je devrais être en mesure d'obtenir une référence non constante à utiliser dans la boucle, puisque l'ensemble lui-même n'est pas qualifié de constant. J'obtiens la même erreur si je crée une fonction setter et que je l'utilise dans la boucle.

Answer 1

Un ensemble est comme une carte sans valeurs, seulement des clés. Comme ces clés sont utilisées pour un arbre qui accélère les opérations sur l'ensemble, elles ne peuvent pas changer. Ainsi, tous les éléments doivent être constants pour que les contraintes de l'arbre sous-jacent ne soient pas brisées.

Answer 2

std::set utilise les valeurs contenues pour former une structure de données rapide (généralement, un arbre rouge-noir). La modification d'une valeur signifie que la structure entière doit être modifiée. Ainsi, en forçant const ness, std::set vous empêche de le pousser dans un état non utilisable.

Answer 3

De la référence cpp :

Dans un ensemble, la valeur d'un élément l'identifie également (la valeur est elle-même la clé, de type T). elle-même la clé, de type T), et chaque valeur doit être unique. La valeur des éléments d'un ensemble ne peut être modifié une fois dans le conteneur (les éléments sont toujours const ), mais ils peuvent être insérés ou retirés du le conteneur.

Answer 4

Ce comportement est délibéré.

Le fait de vous donner un itérateur non constant pourrait vous inciter à changer l'élément de l'ensemble ; le comportement ultérieur de l'itération serait alors indéfini.

Notez que la norme C++ stipule que set<T>::iterator est const donc la bonne vieille méthode pré-C++11 ne fonctionne toujours pas.