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

Handling maps.

P: n/a
Hi all,

Say I have two maps m1 and m2. Both have key as std::string and value
as long.

m1 could hold entries like
"abc" 123
"def" 456

m2 could have entries like
"abc" 789
"hij" 111

I want to show the union of these results like this

"abc" 123 789
"def" 456 0
"hij" 0 111

One way to deal with it would be to form a map<string, vector<long> >,
then loop over m1 and fill it, then loop over m2 and if there is some
existent entry for a key then push_back the value in vector. Doesn't
seem very clean to me. I am sure there might be better approaches. Can
you suggest some ?

Should I have something like map<string, long[2]> instead of m1 and m2
in the first place ?

Thanks.
Jul 22 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a
Old Monk wrote:

Hi all,

Say I have two maps m1 and m2. Both have key as std::string and value
as long.

m1 could hold entries like
"abc" 123
"def" 456

m2 could have entries like
"abc" 789
"hij" 111

I want to show the union of these results like this

"abc" 123 789
"def" 456 0
"hij" 0 111

One way to deal with it would be to form a map<string, vector<long> >,
then loop over m1 and fill it, then loop over m2 and if there is some
existent entry for a key then push_back the value in vector. Doesn't
seem very clean to me.
It's probably the way I would do it (the lazy way)
I am sure there might be better approaches. Can
you suggest some ?
The idea of adapting the idea behind merge sort comes to my mind.

initialize top_first with the first entry in map1
inttialize top_scnd with the first entry in map2

while top_first && top_secnd {

if *top_first == *top_secnd
build new entry combining *top_first and *top_scnd, add to map3
advance top_first
advance top_secnd

else
if *top_first < *top_scnd
build new entry from *top_first, add to map3
advance top_first
else
build new entry from *top_secnd, add to map3
advance top_secnd
}
// while loop finished, either top_first or top_secnd
// or both have reached the end of their map. But one of
// the maps may still contain eintries, add them to the
// result
while top_first {
build new entry from *top_first, add to map3
advance top_first
}

while top_secnd {
build new entry from *top_secnd, add to map3
advance top_secnd
}
Something like that. Might be faster since no search through
the maps is involved.


Should I have something like map<string, long[2]> instead of m1 and m2
in the first place ?


long[2] *would* be fine. But since plain vanilla arrays don't satisfy the
copy and assignment requirements imposed by the standard containers, it
cannot be used. But you could do:

struct Entry
{
long Value1;
long Value2;
}

map< string, Entry >

If that is ok for m1 and m2 is only you to decide. I wouldn't do it. The
operation you want to do is not a standard one, so why blow up the input
maps needlessly. For the result you can either use

map< string, vector< long > >

or
map< string, Entry >

it doesn't make much of a difference (in this specific case. If you
sometimes plan to merge 3 input maps, then things change. But for the
moment ...)

--
Karl Heinz Buchegger
kb******@gascad.at
Jul 22 '05 #2

P: n/a
In article <41***************@gascad.at>,
Karl Heinz Buchegger <kb******@gascad.at> wrote:
Old Monk wrote:

Hi all,

Say I have two maps m1 and m2. Both have key as std::string and value
as long.

m1 could hold entries like
"abc" 123
"def" 456

m2 could have entries like
"abc" 789
"hij" 111

I want to show the union of these results like this

"abc" 123 789
"def" 456 0
"hij" 0 111

One way to deal with it would be to form a map<string, vector<long> >,
then loop over m1 and fill it, then loop over m2 and if there is some
existent entry for a key then push_back the value in vector. Doesn't
seem very clean to me.


It's probably the way I would do it (the lazy way)
I am sure there might be better approaches. Can
you suggest some ?


The idea of adapting the idea behind merge sort comes to my mind.

initialize top_first with the first entry in map1
inttialize top_scnd with the first entry in map2

while top_first && top_secnd {

if *top_first == *top_secnd
build new entry combining *top_first and *top_scnd, add to map3
advance top_first
advance top_secnd

else
if *top_first < *top_scnd
build new entry from *top_first, add to map3
advance top_first
else
build new entry from *top_secnd, add to map3
advance top_secnd
}
// while loop finished, either top_first or top_secnd
// or both have reached the end of their map. But one of
// the maps may still contain eintries, add them to the
// result
while top_first {
build new entry from *top_first, add to map3
advance top_first
}

while top_secnd {
build new entry from *top_secnd, add to map3
advance top_secnd
}
Something like that. Might be faster since no search through
the maps is involved.


Should I have something like map<string, long[2]> instead of m1 and m2
in the first place ?


long[2] *would* be fine. But since plain vanilla arrays don't satisfy the
copy and assignment requirements imposed by the standard containers, it
cannot be used. But you could do:

struct Entry
{
long Value1;
long Value2;
}

map< string, Entry >

If that is ok for m1 and m2 is only you to decide. I wouldn't do it. The
operation you want to do is not a standard one, so why blow up the input
maps needlessly. For the result you can either use

map< string, vector< long > >

or
map< string, Entry >

it doesn't make much of a difference (in this specific case. If you
sometimes plan to merge 3 input maps, then things change. But for the
moment ...)


Another option would be to use std::pair, as in:

map< string, pair< long, long > >;
Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.