By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,778 Members | 1,890 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,778 IT Pros & Developers. It's quick & easy.

joining two maps

P: n/a


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

Jul 23 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
John wrote:

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 !
Jul 23 '05 #2

P: n/a


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?

Jul 23 '05 #3

P: n/a
"John" <we**********@yahoo.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...
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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Jul 23 '05 #4

P: n/a


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.

Jul 23 '05 #5

P: n/a

"John" <we**********@yahoo.com> wrote in message
news:11**********************@g14g2000cwa.googlegr oups.com...


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
Jul 23 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.