Discussion :

[bdx3324]

Bonjour à tous,
Jeune développeur à mes heures perdues, j'ai rencontré hier un problème de taille.
En effet, j'aimerais directement modifier des objets déjà présents dans un set.
J'ai donc d'abord tenté d'utiliser un itérateur qui s'arrête à la position souhaitée, et utilise ensuite les méthodes de la classe pour modifier ledit objet de la façon "classique" it->methode(parametres). Malheureusement, cela ne semble pas possible car les itérateurs sont des objets utilisés en lecture uniquement. Plus généralement, un bloc du style *it=2; ne va pas fonctionner.
J'ai vaguement lu quelque chose à propos de "output iterator tag", qui pourrait peut être offrir la possibilité à l'itérateur d'effectuer des modifications, mais j'avoue que je n'y ai pas compris grand chose.
L'autre idée que j'ai eue, est d'utiliser des pointeurs. Seulement, je ne vois pas commencer effectuer un parcours de set avec un simple pointeur, ou bien comment faire pointer ce pointeur sur l'objet pointé par l'itérateur.
Je vous serai très reconnaissants de m'apporter un peu d'aide à mon problème
Merci d'avance !

[ternel]

La raison pour laquelle il n'est pas possible de modifier directement un set, c'est que cela briserai à la fois l'unicité et le tri.

Suppose le set std::set<int> set = {2, 6, 8, 9}.
Que se passe-t-il si tu fais l'équivalent de *(++ ++ (set.begin()))=N. On a bien un itérateur sur 8.

on appelle successivement begin, iterator::operator++, iterator::operator*, et enfin l'opérateur primitif int:operator= int.

Pour N = 7, tout va bien.
Pour N = 4, il faut modifier l'arbre interne, pour déplacer cet int entre 2 et 6.
Pour N = 2, il faut carrément enlever le 8.
sauf que ca n'est possible à gérer que si le operator* ne retourne pas un int&, mais un proxy. Une classe qui serait le plus transparent possible, mais qui redéfinirait tous les opérateurs.

Continuons avec *(++ ++ (set.begin())) = 2 = 8.
La ca devient drole, j'ai une suppression, puis un déplacement et rééquilibrage de l'arbre.
Cette instruction est en fait équivalente à set.remove(2).


Là où ca devient vraiment grave, c'est que si tu as un itérateur modifiant, l'utilisation de std::sort devient possible, et qu'au lieu de trier, cela va vider ton set d'une bonne partie.
Et là, même le proxy n'est plus suffisant.

[bdx3324]

C'est vrai que je n'ai pas eu cette réflexion. Il vaut donc probablement mieux utiliser d'autres types de données, comme un simple vecteur ?

[renoo]

Un vecteur c'est bien c'est souvent le plus simple mais attention la suppression est en o(n), mais dans tous les cas un vecteur sera efficace si n n'est pas très grand (si n < 100 un vecteur c'est très bien).
L'autre solution serait de faire un remove puis un insert dans ton set.

[bdx3324]

Un vecteur c'est bien c'est souvent le plus simple mais attention la suppression est en o(n), mais dans tous les cas un vecteur sera efficace si n n'est pas très grand (si n < 100 un vecteur c'est très bien).
L'autre solution serait de faire un remove puis un insert dans ton set.

Mon vecteur ne sera pas très grand (une vingtaine d'objets), en revanche il risquerait d'y avoir beaucoup de remove/insert. Je vais tenter avec le vecteur !
Merci pour vos réponses !

[Daïmanu]

Si tu as beaucoup d'insertions et de suppressions, un std::list est à envisager.

Plus généralement pour choisir un container, il y a toute une série de questions à se poser résumées par cette image.

[koala01]

Salut,

L'alternative pourrait aussi très bien être la std::map : la recherche s'effectue en O(log(n)), comme pour std::set, mais le critère de tri (la "clé") et la donnée sont explicitement séparés : tu peux donc modifier la donnée sans modifier la clé, ce qui t'évite d'avoir à enlever l'élément avant de le modifier et de le remettre à sa place

Evidemment, cela implique que, quelle que soit la modification apportée à la donnée, elle ne doit en aucun cas avoir pour résultat de modifier la clé