Discussion :

[b Oo]

Bonjour à tous,
je voudrais savoir s'il est possible de fusionner deux vector sans qu'il y est de doublons ?
J'ai un vector<pair<double, double> v qui contient :

Code :

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

1
2
3
4
 
v[0] = 1, 0;
v[1] = 2, 1;
v[2] = 3, 5;

et un autre tab qui contient :

Code :

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

1
2
3
4
 
tab[0] = 0, 0;
tab[1] = 1, 0;
tab[2] = 2, 4;

Je voudrais en resultat v :

Code :

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

1
2
3
4
5
 
v[0] = 0, 0;
v[1] = 1, 0;
v[2] = 2, 4;
v[3] = 3, 5;

Le merge permet de fusionner les 2 vector, et tri les pairs. Par contre j'ai des doublons.
Il faut que je fasse un unique par la suite ? Ou existe t-il une meilleur solution ? (merge qui enleve les doublons ?)

Merci d'avance.

[Médinoc]

Pour ça, j'utiliserais plutôt des set que des vector...

[b Oo]

D'accord Medinoc,
mais j'aimerais avoir la solution pour des vecteurs, s'il en existe une mieux que celle de merge, unique, erase.

[loufoque]

Le plus performant est sûrement d'avoir les deux vecteurs triés.

[JolyLoic]

std::set_union ?

[b Oo]

Jolyloic, je pense que cela va fonctionner (je ne peux pas tester tout de suite) car je n'ai pas deux fois (ou plus) le même élément dans un de mes vector.

Il faudrait que je crée un algo proche du stantard sinon.

Merci.

[koala01]

Salut,

Sauf erreur de ma part, merge() et unique() existent avec les vector...

Donc, toujours sauf erreur, avec les predicats éventuels utiles, tu devrais pouvoir utiliser un code du genre de

Code :

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

1
2
3
 
std::merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vdestination);
vdestination.unique();

et récupérer le résultat dans le vector vdestination...

[b Oo]

Non koala01, les vectors n'ont pas un membre unique.
De plus unique met tous les éléments différents au début du conteneur et met à la suite les éléments qui sont en double. Et unique renvoie un itérateur sur le debut des éléments qui sont en double.
Il faut donc faire un erase par la suite.
Je sais que l'on peut le faire avec un merge, suivi d'un unique puis d'un erase. Je voulais juste savoir s'il n'y avait pas plus simple.

[Luc Hermitte]

Accessoirement, c'est une variante d'un algo hyper classique que l'on retrouve au coeur de l'implémentation des tris-fusion.
Pondu vite fait (=> probablement bugs inside), cela doit ressembler à :

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
33
34
35
36
37
38
template <typename OI, typename II1, typename II2 o>
OI merge(II1 f1, II1 e1, II2 f2, II2 e2, OI1)
{
    for (
        ; f1!=e1 && f2!=e2
        ;
    )
    {
        if (*f1 < *f2) {
            if (*f1 != *o) *o++ = *f1++;
        } else {
            if (*f2 != *o) *o++ = *f2++;
        }
/// ou plutôt, vu que le premier *o ne doit pas être déférançable...
/// =>
        if (*f1 < *f2) { assert(f1!=e1);
            *o++ = *f1++;
            for ( ; f1 != e1 && *f1==*o; ++f1) 
            {} // purge les autres f1 identiques
        } else { assert(f2!=e2);
            *o++ = *f2++;
            for ( ; f2 != e2 && *f2==*o; ++f2) 
            {} // purge les autres f2 identiques
            // dans le cas des *f1 == *f2_initial
            for ( ; f1 != e1 && *f1==*o; ++f1) 
            {}
        }
    }
    if (f1 != e1) {
        assert(*f1 != *o);
        assert(f2==e2);
        return std::unique_copy(f1, e1, o);
    } else {
        assert(*f2 != *o);
        assert(f1==e1);
        return std::unique_copy(f2, e2, o);
    }
}

Il doit rester des cas aux limites foireux.