joining two maps

[John]

Is there a way to union two maps into one map in O(log n) time?

 

[Gianni Mariani]

Is there a way to union two maps into one map in O(log n) time?

No. The best you can do is O(N) time.

Consider this. If you had a map with all the odd integers from 1 to 127
and another map with all the even integers between 2 and 128 and assume
this takes 7k operations, can you come up with an algoritm that would do
1-255 and 2-256 in 8k operations (where k is some constant) ?

I can easily do it in 14k operations !

 

[John]

stupid me. I was thinking if the sets were disjoint (non-overlapping).
You are absolutely right.

Here is a better formulation of my question, I have two maps M1,M2.
I would like to do the set_union type operation on it. I can of course
make a set and put the data inside it using pair. Any other ideas
on how to do this more naturally? can maps be unioned?

 

[Ivan Vecerina]

Here is a better formulation of my question, I have two maps M1,M2.
I would like to do the set_union type operation on it. I can of course
make a set and put the data inside it using pair. Any other ideas
on how to do this more naturally? can maps be unioned?

I think the way to union two maps is:
M1.insert( M2.begin(), M2.end() );

But I haven't checked the performance specifications for this...

Ivan

 

[John]

should take O(n log_2 m) where n is the smaller of M_1, M_2 and
m is the bigger one. Thanks, at least I got something to lookup.

 

[Joe Gottman]

stupid me. I was thinking if the sets were disjoint (non-overlapping).
You are absolutely right.

Here is a better formulation of my question, I have two maps M1,M2.
I would like to do the set_union type operation on it. I can of course
make a set and put the data inside it using pair. Any other ideas
on how to do this more naturally? can maps be unioned?

If you want the union to a separate set from M1 and M2, you can do the
following:

map<key, value, comp> M1plus2;
set_union(M1.begin(), M1.end(), M2.begin(), M2.end(), inserter(M1plus2,
M1plus2.end()), M1plus2.value_comp());

This finishes in O(M1.size() + M2.size()), because it always inserts new
elements at the end of the output map.

Joe Gottman