Effacer des éléments en commun

Le
Guillaume GOURDIN
Bonjour à tous,

je dispose de 2 std::vector, et je voudrais effacer tous les éléments
communs aux 2 vectors, quelle serait selon vous la façon la plus
élégante de procéder?

Merci pour votre aide.

- Guillaume -
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
ld
Le #20294791
On 5 oct, 17:38, Guillaume GOURDIN
Bonjour à tous,

je dispose de 2 std::vector, et je voudrais effacer tous les éléments
communs aux 2 vectors, quelle serait selon vous la façon la plus
élégante de procéder?



l'effacer ou?

pour trouver l'intersection puis la difference

http://www.cplusplus.com/reference/algorithm/set_intersection/
http://www.cplusplus.com/reference/algorithm/set_difference/

ca sera certainement plus efficace que "d'effacer" les elements les
uns apres les autres.

a+, ld.
James Kanze
Le #20305661
On Oct 5, 6:37 pm, ld
On 5 oct, 17:38, Guillaume GOURDIN


> je dispose de 2 std::vector, et je voudrais effacer tous les
> éléments communs aux 2 vectors, quelle serait selon vous la
> façon la plus élégante de procéder?



l'effacer ou?



pour trouver l'intersection puis la difference



http://www.cplusplus.com/reference/algorithm/set_intersection/http://www. cplusplus.com/reference/algorithm/set_difference/



ca sera certainement plus efficace que "d'effacer" les
elements les uns apres les autres.



Note bien que ces algorithmes exigent que les vector soit trié.
Si les vector sont trié, c'est assez simple d'écrire une boucle
qui fait l'affaire, avec des itérateurs dans les deux vectors:
si les deux éléments sont égaux, on les enlève tous les deux,
sinon, on advance l'itérateur qui désigne le plus petit. Quelque
chose du genre :

while ( a_iter != a.end() && b_iter != b.end() ) {
if ( *a_iter < *b_iter ) {
++ a_iter ;
} else if ( *b_iter < *a_iter ) {
++ b_iter ;
} else {
a_iter = a.erase( a_iter ) ;
b_iter = b.erase( b_iter ) ;
}
}

Si les vector ne sont pas triés, les algorithmes qui me viennent
à l'ésprit sont tous O(n^2) ; ils ne conviennent donc qu'à des
petits vectors. Mais si les vector ne sont pas trop gros, il ne
doit pas être difficile à concevoir un prédicat du genre,
isElementOf (qui se servira de std::find), puis se servir de
std::remove. Ensuite, on enlève de a tous les éléments de b, et
vice versa. Quelque chose du genre :

template< typename ForwardIterator >
class IsMemberOf
{
public:
IsMemberOf( ForwardIterator begin, ForwardIterator end )
: myBegin( begin )
, myEnd( end )
{
}

operator bool(
typename ForwardIterator::value_type const& element) const
{
return std::find( myBegin, myEnd, element ) != myEnd ;
}
private:
ForwardIterator myBegin ;
ForwardIterator myEnd ;
} ;

template< typename ForwardIterator >
IsMemberOf< ForwardIterator >
isMemberOf( ForwardIterator begin, ForwardIterator end )
{
return IsMemberOf< ForwardIterator >( begin, end ) ;
}

puis:

a.erase( std::remove_if( a.begin(), a.end(),
isMemberOf( b.begin(), b.end() ) ),
a.end() ) ;
b.erase( std::remove_if( b.begin(), b.end(),
isMemberOf( a.begin(), a.end() ) ),
b.end() ) ;

Simple et élégant (AMA, en tout cas), mais comme j'ai dit,
O(n^2).

--
James Kanze
ld
Le #20308111
On 7 oct, 09:43, James Kanze
On Oct 5, 6:37 pm, ld
> On 5 oct, 17:38, Guillaume GOURDIN > > je dispose de 2 std::vector, et je voudrais effacer tous les
> > éléments communs aux 2 vectors, quelle serait selon vous la
> > façon la plus élégante de procéder?
> l'effacer ou?
> pour trouver l'intersection puis la difference
>http://www.cplusplus.com/reference/algorithm/set_intersection/http://...
> ca sera certainement plus efficace que "d'effacer" les
> elements les uns apres les autres.

Note bien que ces algorithmes exigent que les vector soit trié.



c'est pour ca que j'ai donne les liens qui donnent aussi des
equivalents sur les iterarteurs pour que le PO puisse les adapter en
fonction de ses besoins.

    a.erase( std::remove_if( a.begin(), a.end(),
                             isMemberOf( b. begin(), b.end() ) ),
             a.end() ) ;
    b.erase( std::remove_if( b.begin(), b.end(),
                             isMemberOf( a. begin(), a.end() ) ),
             b.end() ) ;

Simple et élégant (AMA, en tout cas), mais comme j'ai dit,
O(n^2).



Dans COS c'est en O(n.log(n)) ;-)

a+, ld.
Franck Branjonneau
Le #20317251
James Kanze
Si les vector ne sont pas triés, les algorithmes qui me viennent
à l'ésprit sont tous O(n^2) ; ils ne conviennent donc qu'à des
petits vectors. Mais si les vector ne sont pas trop gros, il ne
doit pas être difficile à concevoir un prédicat du genre,
isElementOf (qui se servira de std::find), puis se servir de
std::remove. Ensuite, on enlève de a tous les éléments de b, et
vice versa. Quelque chose du genre :


puis:

a.erase( std::remove_if( a.begin(), a.end(),
isMemberOf( b.begin(), b.end() ) ),
a.end() ) ;
b.erase( std::remove_if( b.begin(), b.end(),
isMemberOf( a.begin(), a.end() ) ),
b.end() ) ;



Si tu « erase » les éléments de a commun à a et b ; ta deuxième ligne est une
no-op.

Plutôt :

LeTypeQuiVaBien const tmp(std::remove_if(a.begin(), a.end(),
isMemberOf(b.begin(), b.end())));
b.erase( std::remove_if( b.begin(), b.end(),
isMemberOf( a.begin(), a.end() ) ),
b.end() ) ;



a.erase(tmp, a.end());

--
Franck Branjonneau
Lucas Levrel
Le #20312871
Le 7 octobre 2009, James Kanze a écrit :

si les deux éléments sont égaux, on les enlève tous les deux,



while ( a_iter != a.end() && b_iter != b.end() ) {
if ( *a_iter < *b_iter ) {
++ a_iter ;
} else if ( *b_iter < *a_iter ) {
++ b_iter ;
} else {
a_iter = a.erase( a_iter ) ;
b_iter = b.erase( b_iter ) ;
}
}



Et s'il y a un doublon dans a ou dans b ?

a.erase( std::remove_if( a.begin(), a.end(),
isMemberOf( b.begin(), b.end() ) ),
a.end() ) ;
b.erase( std::remove_if( b.begin(), b.end(),
isMemberOf( a.begin(), a.end() ) ),
b.end() ) ;



Je ne maîtrise pas assez pour être sûr d'avoir bien compris, mais il me
semble que dans la première étape tu enlèves du vecteur a les éléments
qu'on trouve dans b, du coup dans la seconde étape tu ne pourras pas les
enlever de b car ils ne seront plus « MemberOf » a...

--
LL
James Kanze
Le #20318231
On Oct 8, 10:28 am, Lucas Levrel
Le 7 octobre 2009, James Kanze a écrit :



> si les deux éléments sont égaux, on les enlève tous les deux,
> while ( a_iter != a.end() && b_iter != b.end() ) {
> if ( *a_iter < *b_iter ) {
> ++ a_iter ;
> } else if ( *b_iter < *a_iter ) {
> ++ b_iter ;
> } else {
> a_iter = a.erase( a_iter ) ;
> b_iter = b.erase( b_iter ) ;
> }
> }



Et s'il y a un doublon dans a ou dans b ?



Je ne vois pas ce que ça changerait.

> a.erase( std::remove_if( a.begin(), a.end(),
> isMemberOf( b.begin(), b.end() ) ),
> a.end() ) ;
> b.erase( std::remove_if( b.begin(), b.end(),
> isMemberOf( a.begin(), a.end() ) ),
> b.end() ) ;



Je ne maîtrise pas assez pour être sûr d'avoir bien compris,
mais il me semble que dans la première étape tu enlèves du
vecteur a les éléments qu'on trouve dans b, du coup dans la
seconde étape tu ne pourras pas les enlever de b car ils ne
seront plus « MemberOf » a...



Là, en revanche, il y un os. Il faudrait faire plutôt quelque
chose du genre :

std::vector<T>::iterator tmp
= std::remove_if( a.begin(), a.end(),
isMemberOf( b.begin(), b.end()) );
b.erase( std::remove_if( b.begin(), b.end(),
isMemberOf( tmp, a.end() ) ) );
a.erase( tmp, a.end() ) ;

Enfin, une utilité pour la sémantique étrange de std::remove_if.

--
James Kanze
Lucas Levrel
Le #20331691
Le 8 octobre 2009, James Kanze a écrit :
On Oct 8, 10:28 am, Lucas Levrel > Le 7 octobre 2009, James Kanze a écrit :
> > si les deux éléments sont égaux, on les enlève tous les deux,
> > while ( a_iter != a.end() && b_iter != b.end() ) {
> > if ( *a_iter < *b_iter ) {
> > ++ a_iter ;
> > } else if ( *b_iter < *a_iter ) {
> > ++ b_iter ;
> > } else {
> > a_iter = a.erase( a_iter ) ;
> > b_iter = b.erase( b_iter ) ;
> > }
> > }

> Et s'il y a un doublon dans a ou dans b ?

Je ne vois pas ce que ça changerait.



Si a = (1, 2, 2, 3) et b= (0, 2, 4) il me semble que ton code aboutit à
a = (1, 2, 3) et b = (0, 4) alors qu'on veut (il me semble aussi) obtenir
a = (1, 3) et b = (0, 4).

--
LL
James Kanze
Le #20332041
On Oct 11, 11:05 am, Lucas Levrel wrote:
Le 8 octobre 2009, James Kanze a écrit :



> On Oct 8, 10:28 am, Lucas Levrel > > Le 7 octobre 2009, James Kanze a écrit :
> > > si les deux éléments sont égaux, on les enlève tous les deu x,
> > > while ( a_iter != a.end() && b_iter != b.end() ) {
> > > if ( *a_iter < *b_iter ) {
> > > ++ a_iter ;
> > > } else if ( *b_iter < *a_iter ) {
> > > ++ b_iter ;
> > > } else {
> > > a_iter = a.erase( a_iter ) ;
> > > b_iter = b.erase( b_iter ) ;
> > > }
> > > }



> > Et s'il y a un doublon dans a ou dans b ?



> Je ne vois pas ce que ça changerait.



Si a = (1, 2, 2, 3) et b= (0, 2, 4) il me semble que ton code aboutit à
a = (1, 2, 3) et b = (0, 4) alors qu'on veut (il me semble aussi) obt enir
a = (1, 3) et b = (0, 4).



En effet. Il faudra que je réflechisse un peu plus avant de
répondre. En gros, dans le else, il faudrait utiliser les erase
à deux itérateurs, avec le deuxième le résultat d'une recherche
d'un élément non-égal. De tête :
a_iter = a.erase(
a_iter,
std::find_if(
a_iter, a.end(),
std::bind2nd( std::not_equal_to< T >(),
*a_iter ) ) ;
b_iter = b.erase(
b_iter,
std::find_if(
b_iter, b.end(),
std::bind2nd( std::not_equal_to< T >(),
*b_iter ) ) ;
Ou sinon, simplement :
T to_erase = *a_iter ;
while ( *a_iter == to_erase ) {
a_iter = a.erase( a_iter ) ;
}
while ( *b_iter = to_erase ) {
b_iter = b.erase( b_iter ) ;
}
Le premier est probablement légèrement plus efficace (mais ça
m'étonne que la différence soit importante), et nettement plus
in, mais au fond, je crois que je préfère le seconde.

--
James Kanze
Publicité
Poster une réponse
Anonyme