Merge avec deux vector, sans doublons ?

Version imprimable

05/11/2006, 11h44
b Oo

Merge avec deux vector, sans doublons ?
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:

1 2 3 4 v[0] = 1, 0; v[1] = 2, 1; v[2] = 3, 5;
et un autre tab qui contient :
Code:

1 2 3 4 tab[0] = 0, 0; tab[1] = 1, 0; tab[2] = 2, 4;
Je voudrais en resultat v :
Code:

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.
05/11/2006, 11h54
Médinoc

Pour ça, j'utiliserais plutôt des set que des vector...
05/11/2006, 12h56
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.
05/11/2006, 17h31
loufoque

Le plus performant est sûrement d'avoir les deux vecteurs triés.
05/11/2006, 17h31
JolyLoic

std::set_union ?
05/11/2006, 19h41
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.
05/11/2006, 23h23
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:

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...
06/11/2006, 11h20
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.

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:

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.