list, ses itérateurs, les pointeurs sur objet et sa fonction sort

Salut,

Je suis pris d'un doute subit en ce qui concerne la std::list...

Je sais (ou du moins, je crois savoir) que l'insertion ne va pas invalider les pointeurs sur les objets qu'elle contient, et que la suppression ne va invalider que le pointeur sur l'objet supprimé.

Ainsi, normalement, si je prévois un code proche de

Code:

---

1 2 3 4 5 6 7 8 9 10 11

std::list<UnType> l; l.push_back(Untype); /*... */ UnType * ptr*=&(*(l.begin()); l.push_back(UnType); /* ptr reste valide  *... */ l.erase(l.rbegin()); /* ptr est toujours valide, pour autant que la suppression n'ai pas  * porté sur l'objet pointé  */

---

ptr devrait toujours être valide après la seconde insertion, ainsi qu'après l'effacement d'un objet tant que ce n'est pas l'objet pointé.

Mais qu'en est il de la fonction membre sort :question:

Se contente-t-elle de refaire les différentes liaisons entre les itérateurs, sans invalider ptr (selon l'exemple) ou va-t-elle carrément créer des copies des différents objets, ce qui reviendra à ... invalider ptr.

Sur mon système (Gcc 4.5.0), il semblerait que ptr ne soit pas invalidé, mais est-ce le comportement que l'on est réellement en droit d'attendre :question:

Et la question connexe: est-il ne serait-ce qu'intéressant d'envisager l'usage d'un shared_ptr quelconque pour représenter ptr :question:

http://www.sgi.com/tech/stl/List.html

Citation:

---

void sort(); Sorts *this according to operator<. The sort is stable, that is, the relative order of equivalent elements is preserved. All iterators remain valid and continue to point to the same elements. [6] The number of comparisons is approximately N log N, where N is the list's size.

---

C'est bien ce qu'il me semblait...

Merci :mrgreen:

Il est parfois bizare de constater comme on peut douter de choses finalement simples :P

Je laisse la discussion pour avoir la réponse à la question connexe (celle qui concerne l'utilisation d'un shared_ptr);)

hmm un shared_ptr ne fonctionne qu'avec un new
dans ce cas il faudrait une std::list< shared<UnType> > n'est-ce pas ?
car la c'est bien la liste qui est propriétaire des objets (en tous cas des copies des objets)

Oui, donc, effectivement, cela n'a strictement aucun intérêt, vu que le pointeur n'est en définitive là qu'en "soutien" afin de pouvoir accéder à un élément sélectionné de la liste...

L'idée est en fait d'avoir une classe qui se présenterait sous la forme de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class MyHolder { public: void registerItem(std::string const &); void selectItem(std::string const &) const; UnType & selected() { if(!selected_) throw unselected(); return *selected_; } UnType const & selected()const { if(!selected_) throw unselected(); return *selected_; } private: std::list<UnType> list_; mutable UnType* selected_; };

---

Du moment que je pense bien à faire pointer selected_ vers NULL quand le pointeur est invalidé, je n'ai effectivement aucun intérêt à me compliquer la vie avec les shared_ptr, quels qu'ils soient ;)

oui, apparemment comme c'est une garantie forte de la liste, tes éléments sont toujours stables, du coup la liste devrait en être la propriétaire, ca simplifie les choses.

Citation:

---

Envoyé par screetch

oui, apparemment comme c'est une garantie forte de la liste, tes éléments sont toujours stables, du coup la liste devrait en être la propriétaire, ca simplifie les choses.

---

Surtout quand tu n'as pas forcément de contraintes en termes de performances pures, et que tu fait principalement des ajouts et quelques sélections ;)

Citation:

---

Envoyé par screetch

http://www.sgi.com/tech/stl/List.html

---

Par contre, dans la norme elle-même, ce n'est pas spécifié.
A priori, je ne vois pas trop pourquoi quoi que ce soit serait invalidé, mais on ne sait jamais. Je vais poser la question.