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

Using a multimap

P: n/a
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
Jul 22 '05 #1
Share this Question
Share on Google+
9 Replies


P: n/a
On Mon, 16 Aug 2004 08:51:07 -0700, "Dennis Jones" <no****@bogus.com>
wrote:
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
Jul 22 '05 #2

P: n/a
Dennis Jones wrote:
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
Jul 22 '05 #3

P: n/a
Dennis Jones wrote:

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;
}
}

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

P: n/a
In article <10*************@corp.supernews.com>,
"Dennis Jones" <no****@bogus.com> wrote:
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.

--
Phillip Mills
Multi-platform software development
(416) 224-0714
Jul 22 '05 #5

P: n/a

"Karl Heinz Buchegger" <kb******@gascad.at> wrote in message
news:41***************@gascad.at...
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

Jul 22 '05 #6

P: n/a
On Mon, 16 Aug 2004 09:26:57 -0700, Kai-Uwe Bux wrote:
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
Jul 22 '05 #7

P: n/a
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:
<snip>
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
Jul 22 '05 #8

P: n/a
On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger
<kb******@gascad.at> wrote in comp.lang.c++:

[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?!?

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
Jul 22 '05 #9

P: n/a
Jack Klein wrote:

On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger
<kb******@gascad.at> wrote in comp.lang.c++:

[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";

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

This discussion thread is closed

Replies have been disabled for this discussion.