Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Using a multimap

Reply
Thread Tools

Using a multimap

 
 
Dennis Jones
Guest
Posts: n/a
 
      08-16-2004
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


 
Reply With Quote
 
 
 
 
Phillip Mills
Guest
Posts: n/a
 
      08-16-2004
In article <(E-Mail Removed)>,
"Dennis Jones" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
tom_usenet
Guest
Posts: n/a
 
      08-16-2004
On Mon, 16 Aug 2004 08:51:07 -0700, "Dennis Jones" <(E-Mail Removed)>
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
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      08-16-2004
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
 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      08-16-2004
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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Dennis Jones
Guest
Posts: n/a
 
      08-16-2004

"Karl Heinz Buchegger" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...

> 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



 
Reply With Quote
 
Ali Cehreli
Guest
Posts: n/a
 
      08-16-2004
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
 
Reply With Quote
 
AlesD
Guest
Posts: n/a
 
      08-17-2004
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:) 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
 
Reply With Quote
 
Jack Klein
Guest
Posts: n/a
 
      08-17-2004
On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger
<(E-Mail Removed)> 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
 
Reply With Quote
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      08-17-2004
Jack Klein wrote:
>
> On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger
> <(E-Mail Removed)> 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
(E-Mail Removed)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Should I implement this using string hash or multimap.. Jonay Aloat C++ 3 09-16-2006 05:58 PM
Multimap Håvard Kverneland Java 1 02-10-2004 12:07 PM
std::multimap insertion order guarantees Tanguy Fautré C++ 13 10-06-2003 04:34 PM
Re: Find specific element of multimap? John Harrison C++ 1 08-14-2003 09:42 AM
Anyone use Multimap ? slumpy Computer Support 4 07-17-2003 07:02 PM



Advertisments