Logo GNT
Actualités Tests & Guides Bons Plans
Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11
Entraide Développement Développement Langage C++ Effacer des éléments en commun

Effacer des éléments en commun

8 réponses
Avatar
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 -
Signaler un problème avec ce contenu

8 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Avatar
ld
On 5 oct, 17:38, Guillaume GOURDIN wrote:
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.
Avatar
James Kanze
On Oct 5, 6:37 pm, ld wrote:
On 5 oct, 17:38, Guillaume GOURDIN wrote:



> 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
Avatar
ld
On 7 oct, 09:43, James Kanze wrote:
On Oct 5, 6:37 pm, ld wrote:

> On 5 oct, 17:38, Guillaume GOURDIN wrote:
> > 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.
Avatar
Franck Branjonneau
James Kanze écrivait:

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
Avatar
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 ?

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
Avatar
James Kanze
On Oct 8, 10:28 am, Lucas Levrel wrote:
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
Avatar
Lucas Levrel
Le 8 octobre 2009, James Kanze a écrit :
On Oct 8, 10:28 am, Lucas Levrel wrote:
> 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
Avatar
James Kanze
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 wrote:
> > 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