445,778 Members | 1,890 Online
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
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" 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" 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 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.