merge de multimaps ?

Version imprimable

Bonjour,

Je dois fusionner deux multimaps.
Je sais le faire avec insert (complexité en temps dans O(N.Log(N)).
Je voudrais le faire avec merge (complexité en temps dans O(N)).

J'ai essayé ça, mais ça ne compile pas :
Code:

1 2 3 4 5 6 7 8 typedef std::multimap<int, std::pair<int, int>> Map ; // ma structure de multimap Map final_m ; Map m1 = my_algo(b1) ; // retourne une des maps à fusionner Map m2 = my_algo(b2) ; // retourne l'autre map à fusionner // erreur ici : final_m.begin() n'est pas le bon itérateur. merge (m1.begin(), m1.end(), m2.begin(), m2.end(), final_m.begin()) ;
Merci de votre aide, Olivier

05/11/2012, 10h29
cob59

Et comme ça ?

Code:

merge (m1.begin(), m1.end(), m2.begin(), m2.end(), std::back_inserter(final_m)) ;

Citation:

Envoyé par cob59

Et comme ça ?

Code:

merge (m1.begin(), m1.end(), m2.begin(), m2.end(), std::back_inserter(final_m)) ;

Presque...

J'ai eu une réponse sur stackoverflow. C'est :

Code:

inserter(final_m,end(final_m))

Voici un code de démo qui emploie cette solution :

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
39
#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>
 
typedef std::pair<int, int> Cell ;
typedef std::multimap<int, Cell> Border_map ;
 
void test_merge_maps_1()
{
Border_map a, b, c ;
std::cout << std::endl << "a" << std::endl ;
for (int i=1; i<10; i+=2)
{
    a.insert(std::pair<int, Cell>(i, Cell(i,i))) ;
    std::cout << i << " " ;
}
 
std::cout << std::endl << "b" << std::endl ;
for (int i=2; i<11; i+=2)
{
    b.insert(std::pair<int, Cell>(i, Cell(i,i))) ;
    std::cout << i << " " ;
}
 
std::cout << std::endl << "merge" << std::endl ;
std::merge(a.begin(), a.end(), b.begin(), b.end(), inserter(c,end(c))) ;
 
std::cout << "result" << std::endl ;
for(auto x: c)
    std::cout << x.first << " " ;
std::cout << std::endl ;
}
 
int main(void)
{
    test_merge_maps_1() ;
    return 0 ;
}