Notes sur les itérateurs du STL set/multiset

Dans la plupart des implantations de la STL, les valeurs placées dans les conteneurs associatifs set et multiset sont constantes. Pour comprendre la motivation derrière ce choix, il faut se rappeler que ces conteneurs ne sont en fait que des arbres binaires — généralement bicolores — pour lesquels les valeurs jouent le rôle de clés. Or, autoriser la modification en place de ces dernières implique qu'un utilisateur maladroit pourrait, par inadvertance, briser les invariants de la structure de données.

Concrètement, cela signifie que le code ci-dessous ne compilera pas pour toutes les implantations de la STL.

set<int> ints;
set<int>::iterator it;

ints.insert(0);
it = ints.find(0);
*it = 1;

Par exemple, GCC nous indique clairement que l'on tente d'écrire à une location accessible en lecture uniquement:

error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<_Tp>::operator*
[with _Tp = int, std::_Rb_tree_const_iterator<_Tp>::reference = const int&]()’

En pratique, il est tout de même quelques fois acceptable de modifier en place un objet stocké dans un set ou un multiset. C'est le cas lorsque la modification n'affecte pas le critère de comparaison.

Pour y arriver, il s'agit simplement d'employer un const_cast et quelques manipulations de pointeurs judicieuses. Celles-ci peuvent être isolées dans une fonction qui rend explicite la nature de l'opération.

template <typename T, typename Iterator>
inline T& mutable_derefence(Iterator& iterator) {
    return *const_cast<T*>(&(*iterator));
}

Pour modifier le champ payload d'un struct stocké dans un set, la fonction mutable_dereference est employée de la manière suivante:

set<Comparable>::iterator it = comparables.find(x);
mutable_derefence<Comparable>(it).payload = payload;

Il s'agit probablement la solution la plus élégante au problème car elle rend ces manipulations délicates explicites. Lorsque cette fonction est employée, il ne peut y avoir d'ambigüité quant aux intentions du programmeur.