Discussion :

[ol9245]

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 :

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

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

[cob59]

Et comme ça ?

Code :

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

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

[ol9245]

Et comme ça ?

Code :

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

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 :

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

inserter(final_m,end(final_m))

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

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
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 ;
}