[C++] STL Vector : Suppression d'un ième élément

Marsh Posté le 06-07-2005 à 16:18:41

J'ai l'habitude de m'en sortir différemment, mais voila, j'ai ce cas qui se pose et je ne trouve pas de solution pas trop crade.
C'est pourtant tout con : je veux supprimer un certain nombre d'élément d'un vector, et la seule chose que je sais sur les éléments à supprimer de ce vector, c'est leur position.
Pas de bol, erase ne prend en paramètre qu'un iterator. Comment je peux m'en sortir du coup avec cette fonction ou une autre ?

Merci :jap:

Reply

Marsh Posté le 06-07-2005 à 16:18:41

Reply

Marsh Posté le 06-07-2005 à 17:25:10

avec la méthode find() tu recherches ton élément, puis tu l'effaces

Code :

vector<gnagna> u;
vector<gnagna>::iterator it = find( u.begin(), u.end(), "prout" );
u.erase(it);

---------------
J'ai un string dans l'array (Paris Hilton)

Reply

Marsh Posté le 06-07-2005 à 17:29:59

C'était un peu ce que j'entendais par "pas trop crade", c'est la seule solution que j'ai trouvé jusqu'à maintenant.

Utiliser find pour effacer des éléments dont on connait la position, c'est assez lourd

Merci quand même, si tu as d'autres idées n'hésites pas

Reply

Marsh Posté le 06-07-2005 à 17:39:22

std::remove(v.begin(), v.end(), "blah" );

Reply

Marsh Posté le 06-07-2005 à 17:53:24

Taz a écrit :

std::remove(v.begin(), v.end(), "blah" );

Idem, ça fera une recherche du début à la fin
Enfin bon tant pi, si vous connaissez pas, c'est que ça n'existe probablement pas. Je vais chercher pour une solution différente alors.

Reply

Marsh Posté le 06-07-2005 à 17:54:49

en même temps, pour trouver l'élément précis d'un tableau, faut le parcourir avant hein [:petrus75]

---------------
J'ai un string dans l'array (Paris Hilton)

Reply

Marsh Posté le 06-07-2005 à 17:55:39

ben ouais ...

si tu veux supprimer une plage, tu as les fonctions membres erase .... RTFM

Reply

Marsh Posté le 06-07-2005 à 18:24:24

Code :

vector<gnagna> u;
int position = 10 ;
vector<gnagna>::iterator it = u.begin()+position;
u.erase(it);

Reply

Marsh Posté le 06-07-2005 à 20:53:40

Harkonnen a écrit :

en même temps, pour trouver l'élément précis d'un tableau, faut le parcourir avant hein [:petrus75]

C'est effectivement ce que je fais, je parcours le vector, je prends la position des éléments qui me vont.
La difficulté, c'est que je ne peux pas traiter les éléments avant de tous les connaitre, c'est à dire après avoir parcouru la totalité du vector.

LordHarryPotter a écrit :

Code :

vector<gnagna> u;
int position = 10 ;
vector<gnagna>::iterator it = u.begin()+position;
u.erase(it);

Je vais tester ça, j'avais un doute que ça fonctionne dans tous les cas mais pourquoi pas.
Merci :jap:

Reply

Marsh Posté le 06-07-2005 à 21:14:31

Si tu dois souvent effectuer des suppressions de ton container, il faut commencer à te demander si vector est le plus adapté à ton utilisation.

Reply

Marsh Posté le 06-07-2005 à 21:14:31

Reply

Marsh Posté le 06-07-2005 à 21:22:03

Slayne a écrit :

C'est effectivement ce que je fais, je parcours le vector, je prends la position des éléments qui me vont.
La difficulté, c'est que je ne peux pas traiter les éléments avant de tous les connaitre, c'est à dire après avoir parcouru la totalité du vector.

Je vais tester ça, j'avais un doute que ça fonctionne dans tous les cas mais pourquoi pas.
Merci :jap:

Il y a un algorithme qui fait ça automatiquement : remove_if. Surtout ne pas oublier l'appel à erase après bien sur.

Reply

Marsh Posté le 06-07-2005 à 21:49:44

Et pour quoi ne récupère tu pas des iterateurs sur ton vecteur en gros t'as un vecteur d'itérateur de ton vecteur niania contenant les positions du vecvteur à supprimer :

Code :

vector<gnagna> u;
vector<vector<gnagn>::iterator> vect_pos ;
for (vector<vector<gnagn>::iterator>::iterator it = vect_pos.begin() ;
it < vect_pos.end() ; ++it)
{
u.erase(*it);
}

Ouaou un vecteur de vecteur d'itérateur et un itérateur de vecteur d'itérateur de vecteur : cool bébé

Reply

Marsh Posté le 06-07-2005 à 22:29:32

vector<truc> vect;
// nieme element a effacer dans vect
int n;
vect.erase(vect.begin()+n);
voilou! :bounce:

Message édité par sankukai8 le 07-07-2005 à 08:08:11

Reply

Marsh Posté le 07-07-2005 à 08:27:22

[:drapal]

---------------
Töp of the plöp

Reply

Marsh Posté le 07-07-2005 à 09:47:01

LordHarryPotter a écrit :

...

Sauf que normalement, le premier appel à erase invalide tes autres itérateurs et le comportement de ton algo n'est pas vraiment sur, non ?

Edit : typo
Edit 2 : La solution la plus adaptée me semble toujours d'effacer les éléments (s'ils sont contigus) avec un erase() ou alors de passer par un remove_if et un functor adapté (qui embarquerait la liste des indices, par exemple, et incrémenterait son compteur interne à chaque appel de la fonction de comparaison)

Message édité par theShOcKwAvE le 07-07-2005 à 09:53:10

Reply

Marsh Posté le 07-07-2005 à 10:01:45

Je suggèrerais plutôt quelque chose de ce genre là :

Code :

#include <vector>
#include <set>
#include <algorithm>
class Elem {};
class IndexRemover{
const std::set<size_t> &_indices;
size_t _i;
public:
IndexRemover(const std::set<size_t> &indices) : _indices(indices), _i(0) {};
bool operator () (const Elem & ) {
return _indices.find(_i++) != _indices.end();
};
};
int main() {
std::vector<Elem> vect;
std::set<size_t> indices;
std::remove_if(vect.begin(), vect.end(), IndexRemover(indices));
return 0;
}

Edit : typo ( je me bats un peu avec mon clavier )

Message édité par theShOcKwAvE le 07-07-2005 à 10:02:21

Reply

Marsh Posté le 07-07-2005 à 15:58:25

2 cas sont possibles
les elements du vecteur devant etre supprimés peuvent etre :
1/ rangés dans l'ordre croissant directement dans un tableau
dans ce cas on peut faire:

Code :

vector<truc> vect // ton vecteur
vector<int> position; // les positions a enlever dans le vect dans l'ordre croissant
while (position.size()!=0) {
vect.erase(vect.begin()+position.back());
position.pop_back();
}

2/ si les positions ne sont pas trouvées directement dans l'ordre croissant,
alors il faut les mettre. c'est important car comme on efface d'abord le dernier,
la position relative des précedents reste la meme.

je ne sait pas si on peut considerer ca comme "propre", mais j'ai vérifié, ca marche
l'avantage, c'est que les positions ne sont pas necessairement une plage!!

Message édité par sankukai8 le 08-07-2005 à 08:00:32

Reply

Marsh Posté le 07-07-2005 à 16:24:43

vect.erase(vect.begin()+position.back()); ????????

Reply

Marsh Posté le 07-07-2005 à 16:54:57

sankukai8 a écrit :

je ne sait pas si on peut considerer ca comme "propre", mais j'ai vérifié, ca marche

C'est effectivement la solution que j'ai adopté, mixé avec l'une des réponses précédentes ...
J'ai fait un vecteur d'itérateur, et j'ai effacé mes éléments dans l'ordre décroissant pour que mes itérateurs soient toujours valable même après suppression.

En tout cas c'est vraiment peu pratique, il y a surement des containers mieux adapter que les vector ou map pour faire ce genre de chose, mais le programmeur précédent avait commencé sur ça et j'ai pas le temps de tout refaire de A à Z

Reply

Marsh Posté le 08-07-2005 à 08:08:12

Taz a écrit :

vect.erase(vect.begin()+position.back()); ????????

vect est le vecteur dont on veut effacer certaine entrée

position est un vecteur d'entiers dont les entrées situent
la position (d'ou son nom) des entrées a effacer dans vect
:pfff:
sachant que vect.begin() renvoie un iterateur sur la premiere
position de vect (c'est a dire 0) et que position.back() renvoie
la derniere entrée du vecteur position (un entier), et que l'on peut
"ajouter" un entier et un iterateur, ce qui fournit un iterateur,
alors on a

vect.begin()+position.back() qui donne un iterateur egale a la position
de la derniere entrée de vect a effacer.
par consequent vect.erase(vect.begin()+position.back()) efface cette
entrée la :pt1cable:

Reply

Marsh Posté le 08-07-2005 à 08:10:43

n'est il pas possible d'effacer directement les entrées de ton vecteur
lorsque tu testes si elle est a garder ou pas plutot que de prendre sa position pour
ensuite effacer cette position?
suis-je clair???

Reply

Marsh Posté le 08-07-2005 à 10:12:02

non. tu peux additioner vector<>::value_type et vector<>::iterator si vector<>::value_type est implicitement convertible en entier. Mais c'est dégueulasse. Quand au résultat, je vois pas. si v.back() == -1, tu erase sur un itérateur invalide. Bref sémantiquement ça ne veut rien dire. Utilise end/rend/...

Reply

Marsh Posté le 08-07-2005 à 10:15:17

sankukai8 a écrit :

n'est il pas possible d'effacer directement les entrées de ton vecteur
lorsque tu testes si elle est a garder ou pas plutot que de prendre sa position pour
ensuite effacer cette position?
suis-je clair???

2 choses :
- Je suis pas sûr qu'en effaçant des objets dans mon vecteur pendant ma boucle for, mon iterateur ne fasse pas n'importe quoi. J'ai fait quelques tests avec des maps, faire un erase pendant qu'on parcoure la map, c'est pas maitrisable Dans un vector ça a l'air de marcher avec des bidouilles genre iterateur--.

- Non je ne peux pas faire comme tu dis, car quand je parcoure mon vecteur, je prends les éléments qui me plaisent, mais s'il y en a qui me plaisent mieux, je les prends à la place des premiers. Là c'est moi qui suis peut être pas très clair.
Enfin pour etre plus clair, j'ai un pixel p0, je parcoure un vecteur de pixel v dans lequel je cherche tous les pixels qui sont à une distance minimale de p0.

Reply

Marsh Posté le 08-07-2005 à 10:30:35

Slayne a écrit :

2 choses :
- Je suis pas sûr qu'en effaçant des objets dans mon vecteur pendant ma boucle for, mon iterateur ne fasse pas n'importe quoi. J'ai fait quelques tests avec des maps, faire un erase pendant qu'on parcoure la map, c'est pas maitrisable

Si, la méthode erase est faite pour.

Code :

map<string, string> trucmuche;
map<string, string>::iterator it = trucmuche.begin();
while (it!=trucmuche.end())
{
if (...)
it=trucmuche.erase(it);
else
++it;
}

Reply

Marsh Posté le 08-07-2005 à 10:41:15

void erase(iterator pos)
Et si on vire le "it=" devant, ça compile mais le résultat, c'est pas trop ça
Par contre le erase de vector marche super bien

Message édité par Slayne le 08-07-2005 à 10:50:05

Reply

Marsh Posté le 08-07-2005 à 10:50:33

Slayne a écrit :

void erase(iterator pos)
Et si on vire le "it=" devant, ça compile mais le résultat, c'est pas trop ça
Par contre le erase de vector marche super bien

Tu compiles avec quoi ? Et tu utilises quelle référence pour les signatures ?
edit: parce que même VS6 utilise une STL qui renvoie un itérateur, conforme à ça: http://www.dinkumware.com/manuals/ [...] map::erase
ou à ça:
http://msdn.microsoft.com/library/ [...] perase.asp

Message édité par Lam's le 08-07-2005 à 10:51:58

Reply

Marsh Posté le 08-07-2005 à 11:07:48

Taz a écrit :

non. tu peux additioner vector<>::value_type et vector<>::iterator si vector<>::value_type est implicitement convertible en entier. Mais c'est dégueulasse. Quand au résultat, je vois pas. si v.back() == -1, tu erase sur un itérateur invalide. Bref sémantiquement ça ne veut rien dire. Utilise end/rend/...

v.back()!=-1 car il y a le test dans le while!
position est un vecteur d'entier, donc pas de conversion implicite vers un entier!

il est possible que cela soit dégueulasse comme tu dis,meme si je ne vois pas bien pourquoi (je ne suis pas un pro du c++) mais en tout cas cela a le mérite de fonctionner sans probleme, et les positions a effacer ne sont pas un range

Code :

#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
vector<int> vect(7);
vector<int> position(3);
for (int i=0;i<7;i++) vect[i]=i;
position[0]=2;
position[1]=4;
position[2]=5;
cout<<"vecteur initial\n";
for (int i=0;i<7;i++) cout<<vect[i]<<"\n";
while (position.size()!=0) {
vect.erase(vect.begin()+position.back());
position.pop_back();
}
cout<<"apres elimination de 2 4 et 5\n";
for (int i=0;i<vect.size();i++) cout<<vect[i]<<"\n";
system("PAUSE" );
return 0;
}

lorsque je compile cela avec dev c++ j'obtient a l'ecran:

vecteur initial
0
1
2
3
4
5
6
apres elimination de 2 4 et 5
0
1
3
6

Message édité par sankukai8 le 08-07-2005 à 11:15:25

Reply

Marsh Posté le 08-07-2005 à 11:17:02

Lam's a écrit :

Tu compiles avec quoi ? Et tu utilises quelle référence pour les signatures ?
edit: parce que même VS6 utilise une STL qui renvoie un itérateur, conforme à ça: http://www.dinkumware.com/manuals/ [...] map::erase
ou à ça:
http://msdn.microsoft.com/library/ [...] perase.asp

J'utilise g++ sous une fedora 4, donc plutot récent. Et le "void erase( iterator)", je le sors directement du site de la STL hein
Enfin google groupes est mon ami, une solution est :

Code :

map<string, string> trucmuche;
map<string, string>::iterator it = trucmuche.begin();
while (it!=trucmuche.end())
{
if (...)
trucmuche.erase(it++);
else
++it;
}

~~Ca marche aussi dans une boucle for, en remplacant le it++ par it--, et en supprimant le else.~~ => Probleme avec le 1er element

Message édité par Slayne le 08-07-2005 à 11:25:10

Reply

Marsh Posté le 08-07-2005 à 11:20:57

Elle ne vous plait pas, ma méthode avec remove_if et functor ?

Reply

Marsh Posté le 08-07-2005 à 11:23:14

theShOcKwAvE a écrit :

Elle ne vous plait pas, ma méthode avec remove_if et functor ?

Si mais c'etait pour l'autre probleme, là le nouveau probleme c'est la suppression d'element dans une map pendant qu'on parcoure la map

Reply

Marsh Posté le 08-07-2005 à 11:26:38

bon je laisse béton vos bordels, c'est nimp

Reply

Marsh Posté le 08-07-2005 à 11:27:47

Pour les suppressions "à la volée" je parcours le conteneur à l'envers. Je ne sais pas trop si c'est applicable aux conteneurs de la STL, puisque je m'en sert peux - full MFC

Reply

Marsh Posté le 08-07-2005 à 11:41:27

Slayne a écrit :

J'utilise g++ sous une fedora 4, donc plutot récent. Et le "void erase( iterator)", je le sors directement du site de la STL hein

D'une part, qu'entends-tu par "le site de la STL" ?
Et d'autre part, tu me confirmes donc que ce code-ci ne compile pas avec ta version de g++:

Code :

#include <map>
#include <string>
using std::map;
using std::string;
void m()
{
map<string, string> trucmuche;
map<string, string>::iterator it = trucmuche.begin();
while (it!=trucmuche.end())
{
if (true)
it = trucmuche.erase(it); // edit
else
++it;
}
}

Message édité par Lam's le 08-07-2005 à 12:22:04

Reply

Marsh Posté le 08-07-2005 à 12:18:20

1 -> http://www.sgi.com/tech/stl/

2 -> Si si, celui ci compilera (tu n'as pas ecrit it = trucmuche.erase(it); cette fois ci). Mais il ne fera pas du tout ce qu'on attend qu'il fasse (mauvais placement de l'iterateur). Sur les groups on peut voir comme solution "trucmuche.erase(it++); " en gardant identique le reste de ton code.

Message édité par Slayne le 08-07-2005 à 12:18:31

Reply

Marsh Posté le 08-07-2005 à 12:21:50

Slayne a écrit :

1 -> http://www.sgi.com/tech/stl/

2 -> Si si, celui ci compilera (tu n'as pas ecrit it = trucmuche.erase(it); cette fois ci). Mais il ne fera pas du tout ce qu'on attend qu'il fasse (mauvais placement de l'iterateur). Sur les groups on peut voir comme solution "trucmuche.erase(it++); " en gardant identique le reste de ton code.

Oui, c'est effectivement une des 2 solutions.

J'ai oublié le "it=" devant mon erase, mais pourrais tu essayer de compiler ce bout de code ? (avec le it=" en début de ligne). Ca passe nickel sous Visual Studio, sous Forte, sous Comeau, et sous gcc 2.9 et 3.0 si je ne dis pas de bétises...

Quand au site de sgi, il est vraiment vieux et plus du tout maintenu (il date de Juin 2000)

Reply

Marsh Posté le 08-07-2005 à 12:29:11

Voila le message d'erreur

Citation :

test_map.cpp: In function int main():
test_map.cpp:84: erreur: no match for operator= in it = trucmuche. std::map<_Key, _Tp, _Compare, _Alloc>::erase [with _Key = std::string, _Tp = std::string, _Compare = std::less<std::string>, _Alloc = std::allocator<std::pair<const std::string, std::string> >](it)
/usr/lib/gcc/i386-redhat-linux/4.0.0/../../../../include/c++/4.0.0/bits/stl_tree.h:152: note: candidats sont: std::_Rb_tree_iterator<std::pair<const std::string, std::string> >& std::_Rb_tree_iterator<std::pair<const std::string, std::string> >::operator=(const std::_Rb_tree_iterator<std::pair<const std::string, std::string> >& )

Et merci pour l'info sur le site, je savais pas ... mais y'a une doc maintenu a jour ?

EDIT : "version gcc 4.0.0"

Message édité par Slayne le 08-07-2005 à 12:33:00

Reply

Marsh Posté le 08-07-2005 à 13:32:59

std::advance permet d'obtenir un itérateur sur un élément connaisant sa position.

Code :

std::vector<int> myvector( 5 );
size_t pos = 4;
std::vector<int>::iterator i = myvector.begin();
std::advance( i, pos );
myvector.erase( i );

---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite

Reply

Marsh Posté le

Reply

[C++] STL Vector : Suppression d'un ième élément

Sujets relatifs:

Leave a Replay