Using a multimap

[Dennis Jones]

Hi,

Is there a way to iterate through a multimap in such a way as to encounter
only the unique keys? In other words, since a multimap allows duplicate
keys, I would like to iterate through the entire multimap, and if a
particular key has duplicates, only see one of them. I don't think I care
about which of the duplicate entries I see, because once I have an entry, I
can use lower_bound and upper_bound to iterate through them, right? (I
won't know the keys ahead of time, so I cannot use multimap::find)

Maybe a multimap isn't even the right way to solve my problem. Here is what
I need to do: I may have some number of items (structures) in which some of
the items may contain the same value in one of its data members. For
instance:

struct MyStruct
{
int x;
...
};

There may be any number of MyStruct instances, and several may have the same
value for 'x'. If this is the case, it identifies a conflict which must be
corrected by the user. So, I need to identify those entries that have
duplicate 'x's so that the user will be aware of the conflicts and can
correct them. (Unfortunately, it is not possible to prevent the conflicts
in the first place -- which is why this problem exists at all.)

My idea was to copy the entries into a multimap using the member 'x' as the
key, and then somehow identify the entries in the multimap that have
duplicate keys. However, I am not sure how best to go about doing that.
Can anyone point me in the right direction, or suggest an alternative
solution to my problem?

Maybe another solution is to use both a map and a multimap. I could fill
both with the same entries. Since the map will not allow duplicates, any
duplicates that exist will get overritten. Then I could iterate through the
map (obtaining all of the unique keys) and use those keys as the search
criteria in multimap::find. Of course, if the list of entries is large,
this solution could use a lot of memory overhead.

Any other ideas are welcome.

Thanks,

- Dennis

 

[Phillip Mills]

My idea was to copy the entries into a multimap using the member 'x' as the
key, and then somehow identify the entries in the multimap that have
duplicate keys. However, I am not sure how best to go about doing that.
Can anyone point me in the right direction, or suggest an alternative
solution to my problem?

My first thought would be to use a map where the key would be 'x' and
the data would be a *vector* of MyStruct. Then each entry in the map
with a vector length greater than 1 would be interesting.

 

[tom_usenet]

Hi,

Is there a way to iterate through a multimap in such a way as to encounter
only the unique keys? In other words, since a multimap allows duplicate
keys, I would like to iterate through the entire multimap, and if a
particular key has duplicates, only see one of them. I don't think I care
about which of the duplicate entries I see, because once I have an entry, I
can use lower_bound and upper_bound to iterate through them, right? (I
won't know the keys ahead of time, so I cannot use multimap::find)

Maybe a multimap isn't even the right way to solve my problem. Here is what
I need to do: I may have some number of items (structures) in which some of
the items may contain the same value in one of its data members. For
instance:

struct MyStruct
{
int x;
...
};

There may be any number of MyStruct instances, and several may have the same
value for 'x'. If this is the case, it identifies a conflict which must be
corrected by the user. So, I need to identify those entries that have
duplicate 'x's so that the user will be aware of the conflicts and can
correct them. (Unfortunately, it is not possible to prevent the conflicts
in the first place -- which is why this problem exists at all.)

My idea was to copy the entries into a multimap using the member 'x' as the
key, and then somehow identify the entries in the multimap that have
duplicate keys. However, I am not sure how best to go about doing that.
Can anyone point me in the right direction, or suggest an alternative
solution to my problem?

std::map<int, std::vector<MyStruct> >
or use a filtering iterator that skips over equal keys, returning the
next iterator with a non-equal key.

Tom

 

[Kai-Uwe Bux]

Hi,

Is there a way to iterate through a multimap in such a way as to encounter
only the unique keys? In other words, since a multimap allows duplicate
keys, I would like to iterate through the entire multimap, and if a
particular key has duplicates, only see one of them. I don't think I care
about which of the duplicate entries I see, because once I have an entry,
I
can use lower_bound and upper_bound to iterate through them, right? (I
won't know the keys ahead of time, so I cannot use multimap::find)

Maybe a multimap isn't even the right way to solve my problem. Here is
what
I need to do: I may have some number of items (structures) in which some
of
the items may contain the same value in one of its data members. For
instance:

struct MyStruct
{
int x;
...
};

There may be any number of MyStruct instances, and several may have the
same
value for 'x'. If this is the case, it identifies a conflict which must
be
corrected by the user. So, I need to identify those entries that have
duplicate 'x's so that the user will be aware of the conflicts and can
correct them. (Unfortunately, it is not possible to prevent the conflicts
in the first place -- which is why this problem exists at all.)

My idea was to copy the entries into a multimap using the member 'x' as
the key, and then somehow identify the entries in the multimap that have
duplicate keys. However, I am not sure how best to go about doing that.
Can anyone point me in the right direction, or suggest an alternative
solution to my problem?

Maybe another solution is to use both a map and a multimap. I could fill
both with the same entries. Since the map will not allow duplicates, any
duplicates that exist will get overritten. Then I could iterate through
the map (obtaining all of the unique keys) and use those keys as the
search
criteria in multimap::find. Of course, if the list of entries is large,
this solution could use a lot of memory overhead.

Any other ideas are welcome.

Thanks,

- Dennis

The following is probably not the most efficient way of iterating through a
multimap visiting only the lowest pair for each key, but at least it is
easy to read:

#include <map>
#include <iostream>

int main ( void ) {
std::multimap< int, int > t;
t.insert( std::make_pair<int,int>( 1,2 ) );
t.insert( std::make_pair<int,int>( 1,3 ) );
t.insert( std::make_pair<int,int>( 2,2 ) );
t.insert( std::make_pair<int,int>( 1,6 ) );
t.insert( std::make_pair<int,int>( 3,4 ) );
t.insert( std::make_pair<int,int>( 3,1 ) );
t.insert( std::make_pair<int,int>( 4,0 ) );
for( std::multimap< int, int >::const_iterator iter = t.begin();
iter != t.end();
iter = t.upper_bound( iter->first ) ) {
std::cout << iter->first << std::endl;
}
}


Best

Kai-Uwe Bux

 

[Karl Heinz Buchegger]

Hi,

Is there a way to iterate through a multimap in such a way as to encounter
only the unique keys? In other words, since a multimap allows duplicate
keys, I would like to iterate through the entire multimap, and if a
particular key has duplicates, only see one of them. I don't think I care
about which of the duplicate entries I see, because once I have an entry, I
can use lower_bound and upper_bound to iterate through them, right? (I
won't know the keys ahead of time, so I cannot use multimap::find)

Why not simply iterate through the multimap and if the key the map comes
up with is identical to the key in the previous iteration loop, you obviously
found a duplicate.

#include <iostream>
#include <map>
#include <string>

using namespace std;

void main()
{
multimap< int, string > Mymap;

Mymap.insert( pair<int, string>( 0, "test1" ) );
Mymap.insert( pair<int, string>( 2, "test2" ) );
Mymap.insert( pair<int, string>( 0, "test3" ) );
Mymap.insert( pair<int, string>( 1, "test4" ) );
Mymap.insert( pair<int, string>( 2, "test5" ) );
Mymap.insert( pair<int, string>( 4, "test6" ) );
Mymap.insert( pair<int, string>( 3, "test7" ) );

multimap< int, string >::iterator it = Mymap.begin();
int LastKey = it->first;
cout << it->first << " " << it->second << endl;
++it;

while( it != Mymap.end() ) {
cout << it->first << " " << it->second;
if( it->first == LastKey )
cout << " duplicate";
else
LastKey = it->first;
cout << endl;
++it;
}
}

 

[Dennis Jones]

Why not simply iterate through the multimap and if the key the map comes
up with is identical to the key in the previous iteration loop, you obviously
found a duplicate.

#include <iostream>
#include <map>
#include <string>

using namespace std;

void main()
{
multimap< int, string > Mymap;

Mymap.insert( pair<int, string>( 0, "test1" ) );
Mymap.insert( pair<int, string>( 2, "test2" ) );
Mymap.insert( pair<int, string>( 0, "test3" ) );
Mymap.insert( pair<int, string>( 1, "test4" ) );
Mymap.insert( pair<int, string>( 2, "test5" ) );
Mymap.insert( pair<int, string>( 4, "test6" ) );
Mymap.insert( pair<int, string>( 3, "test7" ) );

multimap< int, string >::iterator it = Mymap.begin();
int LastKey = it->first;
cout << it->first << " " << it->second << endl;
++it;

while( it != Mymap.end() ) {
cout << it->first << " " << it->second;
if( it->first == LastKey )
cout << " duplicate";
else
LastKey = it->first;
cout << endl;
++it;
}
}

Wow! So many responses in such a short time! Thank you.

- Dennis

 

[Ali Cehreli]

t.insert( std::make_pair<int,int>( 1,2 ) );

I am not adding to the thread much; but providing the template arguments
to make_pair defeats its sole purpose.

This is better:

t.insert( std::make_pair( 1,2 ) );

Ali

 

[AlesD]

Dennis Jones napsal(a):

Hi,

Maybe a multimap isn't even the right way to solve my problem. Here is what
I need to do: I may have some number of items (structures) in which some of
the items may contain the same value in one of its data members. For
instance:

Any other ideas are welcome.

Thanks,

- Dennis

Hello,

if the key (MyStructure::x) is not continuous - especially if it is
sparse - you might try using transformation which will map it into
continuous range. The function is usually called hash function. There is
lots of theory if you are interested and/or looking for optimalization.

This aproach is often used for various indexes and well analyzed. Any
good book about database design will cover use of hash tables/function
and dealing with collisions - which is what might be usefull to you.

Try google with "hash table collision" as search criteria for a start if
you are curious.

AlesD

 

[Jack Klein]

On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger

[snip]

#include <iostream>
#include <map>
#include <string>

using namespace std;

void main()

^^^^

Gasp!!!

Who are you, and what have you done with the real Karl Heinz
Buchegger?!?

 

[Karl Heinz Buchegger]

On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger

[snip]

#include <iostream>
#include <map>
#include <string>

using namespace std;

void main()

^^^^

Gasp!!!

Who are you, and what have you done with the real Karl Heinz
Buchegger?!?

Oh, no! Was that really me?

for( int i = 0; i < 100; ++i )
std::cout << "I will never ever again write 'void main()'\n";