Discussion :

[FstDsi]

Salut,
je voulais savoir s'il existe une fonction prédéfini qui détermine l'intersection entre plusieurs vecteurs.Je travaille avec une structure(vecteur de vecteur d'entiers) par exemple < <1,2,3,4>,<1,2,3,4>,<1,2,4>....>

Code :

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

1
2
3
4
5
6
7
8
9
10
 
struct element
{
std::vetcor<int> elm;
};
 
struct global
{
std::vetcor<struct element> glob;
};

ce que je veux faire c'est d'obtenir l'intersection entre tous les vecteurs contenus dans une variable de type global.Si une telle fonction existe svp précisez moi comment je pourrais l'utiliser parce que je suis débutante en C++.Merci d'avance

[Dalini71]

Yop,

T'appelles quoi intersection entre vector exactement ?

Sinon je ne crois pas qu'une fonction de ce genre existe dans la STL.

[FstDsi]

En fait il s'agit de récupérer les éléments communs entre les différents vecteurs.Par exemple < <1,2,3,4>,<1,2,3,4>,<1,2,4>....> j'aurais comme résultat <1,2,4>.Je pourrais comparer les vecteurs deux à deux.Existe t il au moins une fonction qui fait cela??

[SofEvans]

Ce que tu peux faire, c'est prendre ton premier vector comme modele.
Ensuite, pour chaque element de ton vector, tu parcours ton n-ieme vector. Si il est present dans ton n-ieme vector, tu le conserve, sinon tu le supprime.

Je pense que pour le modele, il faudrait prendre un std::list qui est mieux pour supprimer une occurence au milieu.

Si tu veux plus de precision sur mon algo, demande ^^

[FstDsi]

Merci pr la réponse.Mais j'ai pas bien saisi l'idée de ton algo.Stp peut tu m'expliquer avec un exemple pr ke ça soit plus clair pour moi.Et dis moi stp a quel niveau devrais-je utiliser le std::list.

[SofEvans]

Imaginons que tu est 3 vector :

vector1 <1,2,4,5,7,12,46>
vector2 <1,2,3,4,5,6,12>
vector3 <3,5,7,12>

tu prend le premier vector (arbitraire, si on veut faire optimiser, il faudrait prendre le vector ou il y a le moins d'occurence) et tu copie son contenue dans modele qui est un std::list (c'est la meme chose qu'un vector, sauf que c'est mieux optimiser pour la suppression d'occurence en milieu (par exemple 5 pour vector1).

On a donc :

modele <1,2,4,5,7,12,46>

vector1 <1,2,4,5,7,12,46>
vector2 <1,2,3,4,5,6,12>
vector3 <3,5,7,12>

L'idée, c'est de comparer le modele a tout les autres vector sauf celui qui a servi de modele (ici c'est vector1) et de trier.

On prend la premiere valeur de modele et on regarde si elle se trouve dans vector2. Si oui, on la garde, sinon, on la supprime.

Apres comparaison de modele avec vector2 en appliquant la logique ci dessus, on obtient pour modele :

modele <1,2,4,5,12> car 7 et 46 ne sont pas present mais les autres si.

On fait la meme chose avec le suivant (et en l'occurence le dernier) vector : vector3.

A la fin, on obtient

modele <5,12>

"L'intersecion" de tes vector est donc la list modele.

Je suppose que c'est ce que tu voulait. Si tu ne comprend vraiment pas ma logique, n'hesite pas.

[koala01]

Salut,

Si tes tableaux sont triés, il existe une fonction template nommée set_intersection qui devrait pouvoir t'aider...

Elle s'utilise sous une forme proche de

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
int main()
{
    /* les tableaux à tester */
     * on le rempli "comme on veut" :D  
     */
    std::vector<int> tab1;
    std::vector<int> tab2;
    /* le tableau qui récupère le résultat */
    std::tab<int> result;
    /*  prévoyons la place suffisante dans ce tableau
     * (le nombre maximal d'objet est... la taille du tableau le plus
     * petit)
     */
    if(tab1.size()<tab2.size())
       result.reserve(tab1.size());
   else
       result.reserve(tab2.size());
   /* demandons à set_intersection de travailler pour nous */
   std::set_intersection(
           tab1.begin(), /*itérateur  sur le début du premier tableau */
           tab1.end(), /*itérateur  sur la fin du premier tableau */
           tab2.begin(), /*itérateur  sur le début du deuxième tableau */
           tab2.end(), /*itérateur  sur la fin du deuxième tableau */
           result.begin(), /*itérateur sur l'emplacement de départ dans
                            * le tableau de résultat */
         ); 
    /* on a l'intersection dans result :D */
}

NOTA: nécessite l'inclusion du fichier d'en-tete standard <algoritm>

[Luc Hermitte]

Ceci est un complément de réponse à celle de koala.

Il semblerait que si les entrées ne se chevauchent pas on puisse utiliser set_intersection en place, c'est à dire utiliser tab1 en place de result dans le code de koala. Officiellement c'est interdit, mais l'implémentation de GCC 3.4.4 (et probablement d'autres) le permet. La fonction renvoie un itérateur vers la position après le dernier élément, soit un parfait premier élément pour la fonction std::vector::erase(). Le but étant d'éviter de jongler avec plusieurs vecteurs temporaires.

Le code deviendrait:

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
std::vector<std::vector<int> > tabs = ...;
 
std::vector<int> result; 
result.reserve(tabs[0].size());
assert(tabs.size() >= 2);
std::set_intersection(
    tabs[0].begin(), tabs[0].end(), 
    tabs[1].begin(), tabs[1].end(), 
    std::back_inserter(result));
 
for (size_t i=2 ; i<tabs.size() ; ++i) {
    result.erase(
        std::set_intersection(
            result.begin(), result.end(), //<- officiellement pas supporté
            tabs[i].begin(), tabs[i].end(), 
            result.begin()                //<- officiellement pas supporté
        ), result.end()); // dernier argument de erase
}

PS: koala tu as confondu reserve() et resize(), ou oublié le back_inserter
PPS: les listes bof bof.

PPS: sinon l'ago doit pouvoir s'écrire avec un parcours concurrent à plein.
N ranges (paires begin/end d'itérateurs) en entrée. Tu en cherches le max_element. Tous les autres doivent être incrémentés jusqu'à ce max. Si une fin est atteinte, on a fini. Sinon on copie la valeur courante et on incrémente tous les itérateurs de un. Et on recommence.

[FstDsi]

Merci pour vos réponse.J'ai voulu essayé le set_intersection sur un exemple simple puisque je suis débutante mais ça ne me ramène pas le bon résultat.Je m'explique:

mon vecteur x1 contient<1,2,4,3>
mon vecteur x2 contient<1,2,3,4,5>
Le code suivant me ramène le résultat :<1,2,4> or que le résultat attendu est <1,2,3,4>

Code :

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

1
2
3
4
5
6
7
 
vector<int> setIntersection;
  set_intersection(x1.begin(), x1.end(),x2.begin(), x2.end(),back_inserter(setIntersection));
 
  for( i=0;i<setIntersection.size();i++){
    cout << setIntersection[i];
  }

PS: la fonction asset set à quoi au juste??le compilateur ne l'accepte pas.Je travaille avec visual microsoft 6.0.
Merci encore une foi

[Luc Hermitte]

Cet algo ne marche que sur des vecteurs triés. Ce qui est assez logique, n'est-ce pas ? (souviens-toi de tes cours d'algo : la fusion du tri-fusion ; set_intersection travaille selon le même principe de parcours concurrent)

assert (avec un r, vient de assert.h), c'est pour rappeler que mon bout de code (la boucle en fait) ne peut fonctionner que si on a plus de 2 vecteurs à intersecter de la sorte.

[FstDsi]

Merciiiii énormément pour vos réponses.Je vous remercie infiniment.