Distinct keys in the multimap

Discussion in 'C++' started by Przemek, Jan 31, 2005.

  1. Przemek

    Przemek Guest

    All,

    what is the efficient way to find all distinct keys in a multimap.
    I use the code

    template<class T1, class T2>
    set<T1> GetDistinctKeys(multimap<T1, T2> nMap)
    {
    T1 temp;
    multimap<T1, T2>::iterator i_ptr;
    set<T1> lSet;

    for(i_ptr=nMap.begin(); i_ptr!=nMap.end(); ++i_ptr)
    {
    lSet.insert(i_ptr->first);
    }

    return lSet;
    }

    but perhaps you have some fresh ideas :)

    Pshem
    Przemek, Jan 31, 2005
    #1
    1. Advertising

  2. Przemek

    Ron Natalie Guest

    Przemek wrote:

    >
    > but perhaps you have some fresh ideas :)
    >

    You could copy all the keys into a set, though I'm not sure
    that would be any better than your approach. I guess it depends
    what you want to do with the container full of keys when you get done.
    Ron Natalie, Jan 31, 2005
    #2
    1. Advertising

  3. Przemek wrote:
    > what is the efficient way to find all distinct keys in a multimap.


    Use a version of the standard library 'unique()' algorithm:

    /**/ template <typename T1, typename T2>
    /**/ struct pred {
    /**/ typedef typename std::multimap<T1, T2>::value_type value_type;
    /**/ bool
    /**/ operator()(value_type const& v1, value_type const& v2) const {
    /**/ return v1.first == v2.first;
    /**/ }
    /**/ };
    /**/
    /**/ template <typename T1, typename T2>
    /**/ std::vector<T1>
    /**/ get_distinct_keys(std::multimap<T1, T2> const& nMap)
    /**/ {
    /**/ std::vector<T1> distinct;
    /**/ std::unique_copy(nMap.begin(), nMap.end(),
    /**/ std::back_inserter(distinct),
    /**/ pred<T1, T2>());
    /**/ return distinct;
    /**/ }

    After writing this code, I realized that this does not really
    do the trick: this tries to assign a pair to a value. It would
    be necessary to use an iterator projecting the 'first' component
    of the 'std::multimap's 'pair'. I think Boost
    (<http://www.boost.org/>) has such iterators. Alternatively,
    you could use 'std::transform()' to do the projection first and
    then eliminate duplicate keys using 'std::reserve()' on the
    container prior to returning it. However, this assumes that the
    number of keys removed is relatively small compared to the
    total number of keys. Otherwise, the projection approach is
    probably preferable.

    BTW, THE approach to returning sequences is not by returning
    some sequence but rather to accept an output iterator as
    argument.
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    <http://www.contendix.com> - Software Development & Consulting
    Dietmar Kuehl, Jan 31, 2005
    #3
  4. Przemek

    Mike Wahler Guest

    "Przemek" <> wrote in message
    news:...
    > All,
    >
    > what is the efficient way to find all distinct keys in a multimap.
    > I use the code
    >
    > template<class T1, class T2>
    > set<T1> GetDistinctKeys(multimap<T1, T2> nMap)
    > {
    > T1 temp;
    > multimap<T1, T2>::iterator i_ptr;
    > set<T1> lSet;
    >
    > for(i_ptr=nMap.begin(); i_ptr!=nMap.end(); ++i_ptr)
    > {
    > lSet.insert(i_ptr->first);
    > }
    >
    > return lSet;
    > }
    >
    > but perhaps you have some fresh ideas :)


    Look at 'std::unique_copy' (or if you want to remove the
    duplicates from your multimap, 'std::unique').

    Depending upon what your ultimate goal is, 'unique_copy'
    might be want you want (if you want to store the unique
    values in some container type other than a set, you won't need
    to use an intermediate 'set' container to filter out
    the duplicates).


    -Mike
    Mike Wahler, Jan 31, 2005
    #4
    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. sandeep Kanwal

    serial keys/validation keys

    sandeep Kanwal, Oct 29, 2004, in forum: C++
    Replies:
    1
    Views:
    575
    Mike Wahler
    Oct 29, 2004
  2. reppisch
    Replies:
    6
    Views:
    967
    reppisch
    Jun 19, 2007
  3. puzzlecracker
    Replies:
    19
    Views:
    872
    puzzlecracker
    Oct 30, 2008
  4. Hicham Mouline
    Replies:
    1
    Views:
    382
    Kai-Uwe Bux
    Apr 11, 2010
  5. Howard Hinnant
    Replies:
    1
    Views:
    358
    Howard Hinnant
    Aug 28, 2012
Loading...

Share This Page