Discussion :

[arkerone]

Bonjour,

je souhaite supprimer les éléments non commun à deux vectors dans le premier vector existe-il un moyen élégant de faire ceci avec la STL?

Merci de vos réponse.

[Nogane]

Bonjour,
Je n'ai pas de solution "élégante" sur des vector, mais si vous pouvez utiliser des set, vous pourrez peut-être utiliser set_intersection.

[oodini]

Une composition de find() et de remove_if() ?

Sinon, set_intersection() est également utilisable avec les vecteurs.

[Nogane]

Oups, j'ai lu la doc trop vite. Effectivement set_intersection est utilisable avec les vectors, a condition qu'ils soient triés.

Ca donnerai quelque chose comme:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
void removeDouble(vector<int> &vect1, vector<int> & vect2)
{
  sort(vect1.begin(), vect1.end());
  sort(vect2.begin(), vect2.end());
 
  vector<int> vect3;
  set_intercection(
    vect1.begin(), vect1.end(),
    vect2.begin(), vect2.end(),
    back_inserter(vect3));
  vect3.swap(vect1);
}

Inconvénient(ou pas): vect1 et vect2 doivent être triés

[arkerone]

Merci problème résolu

[JolyLoic]

Inconvénient(ou pas): vect1 et vect2 doivent être triés

D'un autre côté, je ne vois pas comment réaliser cet algo efficacement sans commencer pas trier les données...

[Steph_ng8]

Si les vecteurs ne doivent pas être triés, on peut faire comme ça :

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
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
 
 
template <typename T>
struct not_find
{
 
    not_find(std::vector<T> const& v) : m_begin(v.begin()), m_end(v.end())
    {}
 
    bool operator () (T const& x)
    {
        return !std::find(m_begin, m_end, x);
    }
 
 
  private:
    typename std::vector<T>::const_iterator m_begin;
    typename std::vector<T>::const_iterator m_end;
 
};
 
 
//***********//
 
template <typename T>
void intersection(std::vector<T>& vect1, std::vector<T> const& vect2)
{
    typename std::vector<T>::iterator pos =
      std::remove_if(vect1.begin(), vect1.end(), not_find<T>(vect2));
    vect1.erase(pos, vect1.end());
}

J'ai mis des template partout parce que je ne connais pas les types manipulés, mais ce n'est pas forcément nécessaire.
D'ailleurs, les typename avant les types d'itérateurs ne sont là qu'à cause des template.

std::remove_if se contente de déplacer les éléments « supprimés » à la fin de la plage passée en paramètre, et retourne un itérateur sur le premier élément « supprimé ».
C'est pour cela qu'il faut les effacer explicitement après.
La documentation indique que cette méthode est sûre avec les séquences, et qu'il faut prendre des précautions avec les autres types de conteneurs.


Pour en revenir à la STL, il faudrait faire quelque chose du genre :

Code :

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

1
2
3
4
5
6
7
8
9
std::remove_if(vect1.begin(),
               vect1.end(),
               std::not1(
                 bind1st2nd(vect2.begin(),
                            vect2.end(),
                            ptr_fun(std::find)
                           )
               )
              );

avec bind1st2nd qui s'inspire de std::bind1st et std::bind2nd (ce sont peut-être des extensions non-standard) afin de forcer les deux premiers paramètres d'un foncteur à 3 arguments, et ptr_fun qui s'inspire des std::ptr_fun afin de créer un foncteur à 3 arguments à partir d'une fonction à 3 arguments.