OVH Cloud OVH Cloud

Trier un vecteur d'iterateur à l'envers

12 réponses
Avatar
Michaël Delva
Salut à tous,

continuant sur mes tâtonnements concernant les algos de la STL (c'est pas
faute de chercher et de m'user les yeux sur Le Language C++ par
Stroustrup), je n'arrive pas trier un vecteur d'iterateurs en ordre
inverse, donc de end() à begin()...

Comment vous faites ça?

Merci d'avance!!

10 réponses

1 2
Avatar
Jean-Sebastien Mouret
"Michaël Delva" writes:

Salut à tous,

continuant sur mes tâtonnements concernant les algos de la STL (c'est pas
faute de chercher et de m'user les yeux sur Le Language C++ par
Stroustrup), je n'arrive pas trier un vecteur d'iterateurs en ordre
inverse, donc de end() à begin()...

Comment vous faites ça?



en admettant que tu aies un operateur < sur tes iterateurs (T):

std::sort(v.begin(), v.end(), not2(std::less<T>()));

mais je pense sincerement qu'un simple:

std::reverse(v.begin(), v.end());

devrait suffire car tu ne dois surement pas avoir d'opérateur <

tu peux aussi parcourir ton vecteur en sens inverse avec
un reverse_iterator et ses potes rbegin() et rend().


--

"creating the future" (c) framfab

Avatar
Fabien LE LEZ
On 03 Mar 2004 01:10:05 GMT, "Michaël Delva"
wrote:

je n'arrive pas trier un vecteur d'iterateurs en ordre
inverse, donc de end() à begin()...

Comment vous faites ça?


Je fais pas ;-)
Ou du moins, si j'ai bien compris ton problème, je ne l'ai jamais
fait.

Voici donc comment j'ai compris ta question :

- tu as un std::X<MaClasse> (où X == vector, deque ou list), qui est
le conteneur "de base".
- tu as un std::vector <std::list<MaClasse>::iterator>, que tu
cherches à trier suivant la position de chaque iterateur dans le
conteneur de base.

A priori donc, il te faut un prédicat "EstPosterieurA" pour "std::sort
(it, it, predicat)".

Histoire de simplifier les écritures :

typedef std::X<MaClasse> Conteneur;
typedef Conteneur::iterator Iterateur; /* Note : ça peut aussi être
const_iterator */
typedef std::vector<Iterateur> VectIter;


Pour X==vector, je pense que ceci doit marcher :

template<class T> bool EstPosterieurA
(VectIter::const_iterator i1, VectIter::const_iterator i2)
{
return &*i1 > &*i2;
}

Pas trop sûr toutefois :-/

Pour X=Þque, il doit y avoir un truc, mais je connais assez mal ce
conteneur :-(

Pour X==list, je crois que la seule façon de savoir si un itérateur
est postérieur à un autre est de parcourir toute la liste à partir de
l'itérateur qui t'intéresse, et de regarder si on tombe d'abord sur
l'autre itérateur ou sur end().
Autre solution : parcourir la liste, et, pour chaque itérateur,
compter le nombre d'occurences dans le VectIter. On peut alors créer
un nouveau VectIter en se basant sur ces informations.


--
;-)

Avatar
Michaël Delva
tu peux aussi parcourir ton vecteur en sens inverse avec
un reverse_iterator et ses potes rbegin() et rend().



Parfait avec les reverse_iterator...

Je les avais oublié ceux-là...

Merci beaucoup!!

Avatar
Fabien LE LEZ
On Wed, 03 Mar 2004 02:48:17 +0100, Fabien LE LEZ
wrote:

Voici donc comment j'ai compris ta question :


Note : vu l'heure, j'ai peut-être écrit un tissu de conneries. Bien
faire attention à ma signature donc.

--
;-)

Avatar
Michaël Delva
Fabien LE LEZ wrote in
news::

Je fais pas ;-)


;-)

Ou du moins, si j'ai bien compris ton problème, je ne l'ai jamais
fait.

Voici donc comment j'ai compris ta question :

- tu as un std::X<MaClasse> (où X == vector, deque ou list), qui est
le conteneur "de base".
- tu as un std::vector <std::list<MaClasse>::iterator>, que tu
cherches à trier suivant la position de chaque iterateur dans le
conteneur de base.



Tu as bien compris... En fait j'ai un

std::vector<SJ_Sequence> toutes_possessions;

que je parcoure par itérateur, et si l'itérateur ne répond pas à
certaines exigences, je l'enregistre dans un vecteur de cet itérateur,
pour le supprimer en fin de parcours...

J'en arrive donc à ça (version réduite):

//-----------------------------------------------------------------------

typedef std::vector<SJ_Sequence>::iterator C_ITE;
std::vector<C_ITE> suppr_iterateurs;

for (C_ITE ite = toutes_possessions.begin(); ite ! toutes_possessions.end(); ++ite)
{
bool fin_poss = false,
ds_periode = false,
ds_strategie = false;

//Premier test concluant: fin_poss = true;

//Deuxième test concluant: ds_periode = true

//Si l'une des deux conditions est fausse, on stocke l'itérateur

if (!fin_poss || !ds_periode)
suppr_iterateurs.push_back(ite);
}

//On supprime les itérateurs qui ne sont pas adéquats
for (std::vector<C_ITE>::reverse_iterator ite suppr_iterateurs.rbegin();
ite != suppr_iterateurs.rend();
++ite)
toutes_possessions.erase(*ite);

//-----------------------------------------------------------------------


Maintenant, j'ai une question subsidiaire: comment je peux faire la
suppression directement dans la première boucle? Même avec une boucle
inversée ça marche pas...

* Si je fais avec reverse_iterator, ça marche pas, normal avec le
erase...

* Si je fais:
for (C_ITE ite = toutes_possessions.end(); ite = toutes_possessions.begin(); --ite)

Il commence le parcours depuis le .end(), donc après le dernier élément,
ce qui ne va pas non plus...

* J'avais donc cherché du côté de ça:

C_ITE ite = toutes_possessions.end();
--ite;

for (ite = toutes_possessions.end(); ite = toutes_possessions.begin(); --ite)

Mais ça plante si le vecteur est vide, et donc il y a trop de
vérifications à faire dans le code pour que ça me semble être une
solution correcte...

Peut-être aussi que je me casse la tête pour rien et que ce que je fais
est déjà la meilleure méthode??

Avatar
Franck Branjonneau
"Michaël Delva" écrivait:

news::

Maintenant, j'ai une question subsidiaire: comment je peux faire la
suppression directement dans la première boucle? Même avec une boucle
inversée ça marche pas...


std::vector<>::erase(std::vector<>::iterator) retourne un itérateur
désignant l'élément suivant celui qu'il vient de détruire ou
std::vector<>::end().
--
Franck Branjonneau

Avatar
Samuel Krempp
le Wednesday 03 March 2004 02:53, écrivit :

Parfait avec les reverse_iterator...

Je les avais oublié ceux-là...

Merci beaucoup!!


et ben, tu aurais dû mieux rédiger ta question départ car ce n'est pas du
tout ce qu'on pouvait penser que tu voulais, il n'y a aucun rapport avec un
*tri* d'itérateurs.

--
Sam

Avatar
Michaël Delva
Samuel Krempp wrote in
news:4045c6bb$0$29938$:

le Wednesday 03 March 2004 02:53, écrivit :

Parfait avec les reverse_iterator...

Je les avais oublié ceux-là...

Merci beaucoup!!


et ben, tu aurais dû mieux rédiger ta question départ car ce n'est pas
du tout ce qu'on pouvait penser que tu voulais, il n'y a aucun rapport
avec un *tri* d'itérateurs.



Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce que
font les reverse_iterator?


Avatar
Samuel Krempp
le Wednesday 03 March 2004 13:23, écrivit :

Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce que
font les reverse_iterator?


non, trier c'est pas "aller", comme les verbes le laissent penser c'est une
action bien différente.
toi tout ce que tu voulais c'est itérer en allant du dernier au premier, et
ce n'est pas le concept du tri.

En l'occurence, si tu mets les itérateurs begin() et end() dans un tableau
(c'était ça si j'ai bien suivi, non ?) il faut ensuite inverser l'ordre des
éléments. Alors là trier aurait le résultat voulu, mais ce n'est même pas
la méthode adaptée pour "retourner" un tableau, qui se fait mieux et plus
simplement.

Et à la base, aller de end() à begin() se fait sans mettre des itérateurs
dans un vecteur, donc c'est simplement ça qu'il aurait fallu demander : ce
que tu voulais vraiment faire au final.
C'est pas pour être désagréable que je dis ça, c'est pas ta faute si tu as
pensé que mettre dans un vecteur et trier était la solution à ton problème.
Mais je voulais juste te faire remarquer que tu obtiendras plus de réponses
en formulant tes questions en fonction de ton but plus que de ce que tu
penses être la solution. Et tu mettras moins de lecteurs sur des fausses
pistes.

--
Sam

Avatar
Michaël Delva
Samuel Krempp wrote in
news:40471da7$0$2441$:

le Wednesday 03 March 2004 13:23, écrivit :

Ben trier à "l'envers", c'est bien aller de end() à begin(), non? Ce
que font les reverse_iterator?


non, trier c'est pas "aller", comme les verbes le laissent penser
c'est une action bien différente.
toi tout ce que tu voulais c'est itérer en allant du dernier au
premier, et ce n'est pas le concept du tri.

En l'occurence, si tu mets les itérateurs begin() et end() dans un
tableau (c'était ça si j'ai bien suivi, non ?) il faut ensuite
inverser l'ordre des éléments. Alors là trier aurait le résultat
voulu, mais ce n'est même pas la méthode adaptée pour "retourner" un
tableau, qui se fait mieux et plus simplement.

Et à la base, aller de end() à begin() se fait sans mettre des
itérateurs dans un vecteur, donc c'est simplement ça qu'il aurait
fallu demander : ce que tu voulais vraiment faire au final.
C'est pas pour être désagréable que je dis ça, c'est pas ta faute si
tu as pensé que mettre dans un vecteur et trier était la solution à
ton problème. Mais je voulais juste te faire remarquer que tu
obtiendras plus de réponses en formulant tes questions en fonction de
ton but plus que de ce que tu penses être la solution. Et tu mettras
moins de lecteurs sur des fausses pistes.



OK, j'essaierai de mieux formuler ma question les prochaines fois. En
espérant ne pas être limité, comme c'est souvent le cas, par le vocabulaire
spécifique au C++, ce qui, je te l'accorde volontiers, n'a pas été le cas
cette fois ;-)


1 2