Discussion :

[camboui]

Le dernier élément d'un vector<> peut s'obtenir par deux écritures

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
v.end()-1
v.rbegin()

On est tous d'accord je suppose que c'est la même chose... enfin presque, parce que v.end()-1 est de type iterator alors que v.rbegin() est de type reverse_iterator.

Mon soucis intervient lorsque je veut retirer le dernier élément d'un vector.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
v.erase(v.end()-1)
v.erase(v.rbegin())

Le compilateur refuse la deuxième expression, c'est assez dommage je trouve (VC++6).

[nikko34]

ça devrait être possible en utilisant la méthode .base() du reverse_iterator:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
v.erase( v.rbegin().base() );

<EDIT> et en fait non c'est dangereux </EDIT>

Rien n'indique que iterator et reverse_iterator se doivent d'être du même type, donc .base() te renvoie l'iterator correspondant à ton reverse_iterator.

euh sinon, pour faire simple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
v.pop_back();

[camboui]

J'en apprend tous les jours...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
void pop_back()
	{erase(end() - 1); }

Merci !

[corrector]

Rien n'indique que iterator et reverse_iterator se doivent d'être du même type,

Tout indique qu'ils ne peuvent pas être du même type!

.base() te renvoie l'iterator correspondant à ton reverse_iterator.

base() renvoie l'itérateur stocké par le reverse_iterator, celui qui a été passé en argument au constructeur :

reverse_iterator<I>(i).base() = i

base() ne renvoie pas un itérateur correspondant dans le sens où tu l'entends : pointant sur le même objet.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
v.erase( v.rbegin().base() );

Non surtout pas! Par définition :

v.rbegin() = V::reverse_iterator(v.end())

où V est le type de v, donc

v.rbegin().base() = v.end()

Par définition, v.end() ne pointe pas sur un élément, et donc v.erase(v.rbegin().base()) a un comportement indéfini.

Pour le principe de fonctionnement de reverse_iterator et la relation entre *r et r.base(), je te conseille de lire une doc sur la STL.

Pour un exemple de code utilisant les propriétés de reverse_iterator et notamment base(), regarde mon message #4.

[nikko34]

ouaip, tu as raison, je me suis encore fait avoir par le erase( end ) et gcc.

C'est juste la deuxième fois que je fais la même erreur ici. Ca doit vouloir dire quelque chose, je dois faire un blocage là dessus.

sinon, pop_back(), c'est bien.

[yan]

a propose des interator

http://www.developpez.net/forums/sho...d.php?t=451033

[corrector]

ouaip, tu as raison, je me suis encore fait avoir par le erase( end ) et gcc.

C'est juste la deuxième fois que je fais la même erreur ici. Ca doit vouloir dire quelque chose, je dois faire un blocage là dessus.

Tu utilises le mode de débogage de la STL?

[nikko34]

Tu utilises le mode de débogage de la STL?

Je ne pense pas, j'utilise mon GCC sans rien de spécial, sous SUSE10.

Est-ce que ça peut être considéré comme un bug? Vu que le comportement est indéfini, tout peut se passer...

Effectivement VisualC++ crashe avec le même code. J'aurais pu éviter de raconter des bétises ( oui je teste quand même tout le code que je poste )

[corrector]

Le dernier élément d'un vector<> peut s'obtenir par deux écritures

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
v.end()-1
v.rbegin()

On est tous d'accord je suppose que c'est la même chose...

Non, justement, en dehors du fait que :

&*(v.end()-1) == &*v.rbegin()

le comportement n'est pas le même.

enfin presque, parce que v.end()-1 est de type iterator alors que v.rbegin() est de type reverse_iterator.

Mon soucis intervient lorsque je veut retirer le dernier élément d'un vector.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
v.erase(v.end()-1)
v.erase(v.rbegin())

Le compilateur refuse la deuxième expression, c'est assez dommage je trouve (VC++6).

L'interface des conteneurs est exprimée en terme de iterator, pas de reverse_iterator : insert et erase prennent des iterator; dans les conteneurs associatifs, find renvoie un iterator, etc.

En réalité, les reverse_iterator ne sont pas du tout intégrés aux conteneurs; reverse_iterator c'est juste un adaptateur d'itérateur. Il n'y avait aucun besoin de demander aux conteneurs d'implémenter rbegin, rend, alors que c'est juste reverse_iterator(end()) et reverse_iterator(begin()) respectivement, on aurait aussi bien pu définir quatre fonctions libre (non testé) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
namespace std {
template <class Container>
reverse_iterator<typename Container::iterator> rbegin (Container& c) {
    return reverse_iterator<typename Container::iterator> (c.end ());
}
 
template <class Container>
reverse_iterator<typename Container::iterator> rend (Container& c) {
    return reverse_iterator<typename Container::iterator> (c.begin());
}
 
template <class Container>
reverse_iterator<typename Container::const_iterator> rbegin (const Container& c) {
    return reverse_iterator<typename Container::const_iterator> (c.end ());
}
 
template <class Container>
reverse_iterator<typename Container::const_iterator> rend (const Container& c) {
    return reverse_iterator<typename Container::const_iterator> (c.begin());
}
} // std

Et voilà, pas la peine d'embêter les auteurs de conteneurs, le service rendu est le même, et ça montre flexibilité de la conception par adaptateur : imposer la présence systématique d'un adaptateur dans chaque classe, c'est vraiment de l'anti-conception.

De plus, l'implémentation avec des fonctions libres évite de donner l'impression que les reverse_iterator font partie de l'interface des conteneurs dans le sens d'une véritable intégration.

En fait, rien n'empêche de faire ce que tu veux avec des fonctions libres (non testé) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
template <class Container>
reverse_iterator<typename Container::iterator> 
insert (Container& c, reverse_iterator<typename Container::iterator> i) {
    return reverse_iterator<typename Container::iterator> (next (c.insert (i.base())));
}
 
template <class Container>
reverse_iterator<typename Container::iterator> 
erase (Container& c, reverse_iterator<typename Container::iterator> i) {
    return reverse_iterator<typename Container::iterator> (c.erase (prev (i.base())));
}

Cependant, les règles d'invalidation sont complètement différentes de ce qu'on a d'habitude; en effet, avec une liste (std::list), un reverse_iterator vers un élément n'est pas invalidé par la suppression de cet élément :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
// définitions, initialisation : 
typedef list<int> li_t;
lit_t li;
li.push_back (1); li.push_back (2);
typedef lit_t::reverse_iterator rev_t;
rev_t r = li.rbegin ();
 
// test :
cout << *r; // -> 2
r2 = erase (li, r);
cout << *r2; // -> 1
cout << *r; // -> 1 !!!
cout << r == r2; // -> 1

parce que dans ce cas (std::list), erase renvoie son argument. Mais attention à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
// définitions, initialisation : pareil 
// test : 
rev_t r2 = next (r);
cout << *r2; // -> 1
erase (li, r);
cout << *r2; // NON : comportement indéfini, r2 est invalidé

En effet, r2 pointait sur l'élément 1 parce que r2.base() pointait sur l'élément 2; celui-ci ayant été supprimé, r2 est invalidé, tandis que r, qui a été passé à ::erase, est toujours valide et pointe sur l'élément 1, comme r2 avant! Ce qui est tout à fait logique, parce que r.base() pointe un-après-la-fin, que ce soit avant ou après le ::erase.

Il y aura aussi des surprises avec ::insert si on s'attend à une sémantique équivalente à celles des iterator et de list::insert.

L'utilisateur doit bien comprendre ces subtilités, subtilités causées par la définition de reverse_iterator en terme de l'itérateur base() décalé d'un élément, ce qui est tout sauf un détail d'implémentation quand on change le contenu du conteneur.