Handling maps.

[Old Monk]

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.

[Karl Heinz Buchegger]

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

[Daniel T.]

In article <41************ ***@gascad.at>,
Karl Heinz Buchegger <kb******@gasca d.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 > >;