Using a multimap

Discussion in 'C++' started by Dennis Jones, Aug 16, 2004.

  1. Dennis Jones

    Dennis Jones Guest

    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
     
    Dennis Jones, Aug 16, 2004
    #1
    1. Advertising

  2. In article <>,
    "Dennis Jones" <> 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
     
    Phillip Mills, Aug 16, 2004
    #2
    1. Advertising

  3. Dennis Jones

    tom_usenet Guest

    On Mon, 16 Aug 2004 08:51:07 -0700, "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?


    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
     
    tom_usenet, Aug 16, 2004
    #3
  4. Dennis Jones

    Kai-Uwe Bux Guest

    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
     
    Kai-Uwe Bux, Aug 16, 2004
    #4
  5. 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
     
    Karl Heinz Buchegger, Aug 16, 2004
    #5
  6. Dennis Jones

    Dennis Jones Guest

    "Karl Heinz Buchegger" <> wrote in message
    news:...

    > 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
     
    Dennis Jones, Aug 16, 2004
    #6
  7. Dennis Jones

    Ali Cehreli Guest

    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
     
    Ali Cehreli, Aug 16, 2004
    #7
  8. Dennis Jones

    AlesD Guest

    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
     
    AlesD, Aug 17, 2004
    #8
  9. Dennis Jones

    Jack Klein Guest

    On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger
    <> 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/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Aug 17, 2004
    #9
  10. Jack Klein wrote:
    >
    > On Mon, 16 Aug 2004 18:32:49 +0200, Karl Heinz Buchegger
    > <> 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
     
    Karl Heinz Buchegger, Aug 17, 2004
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Håvard Kverneland

    Multimap

    Håvard Kverneland, Feb 10, 2004, in forum: Java
    Replies:
    1
    Views:
    665
    Håvard Kverneland
    Feb 10, 2004
  2. John Harrison
    Replies:
    1
    Views:
    592
    Dave O'Hearn
    Aug 14, 2003
  3. Tanguy Fautré

    std::multimap insertion order guarantees

    Tanguy Fautré, Oct 5, 2003, in forum: C++
    Replies:
    13
    Views:
    825
    David B. Held
    Oct 6, 2003
  4. al

    map and multimap

    al, Jan 2, 2004, in forum: C++
    Replies:
    5
    Views:
    479
    Nick Hounsome
    Jan 3, 2004
  5. Jonay Aloat
    Replies:
    3
    Views:
    351
    Jerry Coffin
    Sep 16, 2006
Loading...

Share This Page