Bonjours a vous,
La STL defini clairement ce qu'est un iterateur valide ou un iterateur invalide. Par exemple pour une sequence:
"If a is a Sequence, then p is a valid iterator in a if it is a valid (nonsingular) iterator that is reachable from a.begin()."
Je n'ai pas trouve de fonction dans la doc qui me permette de savoir si un iterateur est valide pour un conteneur. Est ce qu'une telle fonction existe ?
Merci

Ça m'étonnerai que ça existe (mais je ne connais pas la STL) car il y a assez peu de fonctions qui ne soient pas O(1).

Là c'est même pire, avec une liste chainée infinie (c'est possible avec la STL ?) l'algo naïf va boucler infiniment. Et je crois me souvenir que dans la stl tout les algo sont plus ou moins naïf.

Donc je dirais que cette validité est une propriété que tu dois prouver au niveau de ton programme et de ses invariant plutôt qu'essayer de la vérifier à l'exécution.

Vous m'arrêtez si je dis une bêtise, mais pour moi, la seule façon de faire une liste chaînée infinie c'est de la rendre cyclique. Si on garde en mémoire toutes les adresses des chaînons, on doit pouvoir vérifier en temps fini si une liste est finie ou non (et tester la validité d'un itérateur, qui lui pourrait provoquer une boucle infinie).

absolument, mais pour une liste non cyclique et très longue ça demande beaucoup de mémoire, gaspillé inutilement. Et c'est assez compliqué. Je suis presque sûr que si on peut faire une liste cyclique avec la STL alors les algos de celle-ci vont boucler dessus.

mmm, je me doutais bien d'un truc comme ca... En l'occurence j'en ait beson pour du debuggage. Donc, si c'est pas rapide je m'en fout un peu.

"Donc je dirais que cette validité est une propriété que tu dois prouver au niveau de ton programme et de ses invariant plutôt qu'essayer de la vérifier à l'exécution."
Je vais vous raconter rapidement. J'ai un bug aleatoire dans un code pour wii. La partie stressante est que le code marchait sur DS et sur Linux/SDL.
J'ai fini par trouver un iterateur invalide et le grand mechant bug est parti. Visiblement les deux implementations de la STL ne marchent pas exactement pareil sur les iterateurs invalides (c'est pas la faute de l'implementation, ils sont invalides on devrait rien faire avec). Et kaboom mon code.

"Je suis presque sûr que si on peut faire une liste cyclique avec la STL alors les algos de celle-ci vont boucler dessus"
Tous les algos de la STL prenne un range en parametre. Donc si les operateurs de comparaison d'iterateur sont bien defini et que les bon parametres sont passe a l'algorithme, il n'y a pas de raison que ca ne marche pas.

Manifestement, il y a deux définitions d'opérateurs invalide (ton premier post utilise le mot valide pour le définir).

Dans la doc de sgi, je viens de lire que par définition un itérateur "singular" est un itérateur sur lequel les opérations autre que l'assignation sont indéfinie. Pour être valide _dans_ une séquence, il faut en plus être accessible.

Laquelle de ces propriétés n'est pas validé par ton itérateur ? Et ce n'est pas un bogue ailleurs dans ton programme que cet itérateur invalide arrive ?

Oui probablement que c'est un bug ailleurs dans le code. Le but est d'avoir une idee de quand le bug apparait. Je voudrais faire basiquement: assert (is_valid(it)); pour detecter les bugs au plus tot et pas au moment ou je fini par ecrire sur une zone sensible.

J'ai souvent vu ce genre de bugs, lorsque des gens faisaient des erase() sur l'element en cours (ie un for( ; it != e; ++it) ... list.erase( it );

Un is_valid est assez difficile a implenter a vrai dire, enfin sans modifier STL. Tu peux tester la validite de l'adresse, mais ca depends vraiment de comment tu gere la memoire. Le _HAS_ITERATOR_DEBUGGING sur PC aide pas mal a choper ces erreurs.
Alternativement tu peux faire un petit proxy:
(example rapide pour donner l idee)
template<class Container, class Type > class ProxyIterator
{
typedef Container<Type> ContainerType;
typedef ContainerType<Type>::const_iterator IteratorType;
const ContainerType& _obj;
IteratorType& _it;

void check_validity()
{
IteratorType it = _obj.begin();
IteratorType e = _obj.end();
for( ; it != e; ++i )
if( it == _it )
return;
assert( false );
}
public:
ProxyIterator( const ContainerType& obj, IteratorType it ) : _obj( obj ), _it( it ) {}
operator Type() { check_validity(); return *_it; }
operator++()
{
check_validity();
++_it;
};
etc..

"J'ai souvent vu ce genre de bugs, lorsque des gens faisaient des erase() sur l'element en cours (ie un for( ; it != e; ++it) ... list.erase( it ); "
C'est un truc dans le genre qui m'est arrive.
basiquement j'avais ecrit:
for (it = list.begin(); it != list.end(); it++)
{
if (cnd) {it = list.erase(it); it--;}
}
ce truc la marche bien sauf quand tu efface le premier element ou tu prends l'iterateur qui est AVANT begin(). Pour une raison obscure ca ne faisait pas d'erreur dans valgrin sur PC, mais ca deconnait sur ma wii.
Je pense que le bug est corrige maintenant mais, on ne sait jamais.

"Le _HAS_ITERATOR_DEBUGGING sur PC aide pas mal a choper ces erreurs."
Tiensm je ne connais pas ca, je vais le googler.

"Alternativement tu peux faire un petit proxy"
L'idee est seduisante, avec des constructeurs bien type et des des casts implicite, on peut faire ca de facon transparente. Merci pour l'idee.