Multimap: how to get a key list?

Discussion in 'C++' started by Rui Maciel, Feb 28, 2010.

  1. Rui Maciel

    Rui Maciel Guest

    Is there any way to get a list of keys from a multimap besides relying on a couple of nested
    loops to assemble that list?


    Thanks in advance,
    Rui Maciel
     
    Rui Maciel, Feb 28, 2010
    #1
    1. Advertising

  2. Rui Maciel

    Brian Guest

    On Feb 28, 5:09 pm, Sam <> wrote:
    > Rui Maciel writes:
    > > Is there any way to get a list of keys from a multimap besides relying on a couple of nested
    > > loops to assemble that list?

    >
    > What nested loops? Only one loop is required to iterate over the multimap..
    >
    > There is no single function that gives you a set of all keys stored in the
    > multimap, but a single loop is all that's needed to retrieve all the keys..
    > It's fairly easy to define a template function that gives them to you,
    > something like this:
    >
    > template<typename multimap_t>
    > void keys(const multimap_t &m,
    >           std::set<typename multimap_t::key_type> &k)
    > {
    >     for (typename multimap_t::const_iterator b(m.begin()), e(m.end());
    >          b != e; ++b)
    >     {
    >          k.insert(b->first);
    >     }
    >
    > }
    >
    > The std::set automatically takes care of deduping the multimap's keys.
    >
    >


    I think that works fine. This might speed it up a little:

    template<typename multimap_t>
    void keys(const multimap_t &m,
    std::set<typename multimap_t::key_type> &k)
    {
    typename std::set<typename multimap_t::key_type>::iterator
    keys_end = k.end();
    for (typename multimap_t::const_iterator b(m.begin()),
    e(m.end());
    b != e; ++b)
    {
    k.insert(keys_end, b->first);
    }
    }

    That would work best if k is being passed in
    as an empty container as seems likely.


    Brian Wood
    http://webEbenezer.net
    (651) 251-9384
     
    Brian, Mar 1, 2010
    #2
    1. Advertising

  3. Rui Maciel

    tonydee Guest

    On Mar 2, 9:54 am, "Daniel T." <> wrote:
    > template < typename map_t, typename OutIt>
    > void keys(const map_t& aMap, OutIt out)
    > {
    >    typename map_t::const_iterator it = aMap.begin();
    >    while (it != aMap.end()) {
    >       typename map_t::key_type key = it++->first;
    >       out++ = key;
    >       while (it != aMap.end() && key == it->first)
    >          ++it;
    >    }
    > }


    Needs to be "*out++".

    I like that you've used an output iterator: set<> was a wasteful way
    of handling duplicate keys, even assuming that they're not wanted in
    the result (which the OP didn't specify). list<> or vector<> could
    reasonably be expected to outperform set<>.

    Might want to make key a reference, as copying the key could be
    expensive (alternatively, but probably more expensive, keep an
    iterator to it). Post-increments involve iterator copies - could also
    be slightly more expensive than ++it/++out afterwards, or a
    preincrement ala

    while (++it != a.Map.end() and key == it->first)
    ;

    (The short-circuit logical operator constitutes a sequence point.)


    Alternatively, one loop:

    typename map_t::key_type* p_key = NULL;

    for (typename map_t::const_iterator it = aMap.begin();
    it != aMap.end(); ++it)
    {
    if (p_key and *p_key == it->first)
    continue;
    p_key = &(it->first);
    *out++ = *p_key;
    }

    Alternatively, we could shoe-horn an STL algorithm. For example (and
    assuming we want each instance of duplicate keys:

    template <class Inserter>
    struct Assign_First : public Inserter
    {
    typedef typename Inserter::container_type container_type;

    Assign_First(container_type& c) : Inserter(c) { }

    Assign_First& operator*() { return *this; }

    template <typename Pair>
    Assign_First& operator=(const Pair& value)
    {
    Inserter::eek:perator=(value.first);
    return *this;
    }
    };

    ...

    typedef std::multimap<int, std::string> MM;
    MM mm;

    typedef std::vector<MM::key_type> Keys;
    Keys keys;

    std::copy(mm.begin(), mm.end(),
    Assign_First<std::back_insert_iterator<Keys> >(keys));

    Cheers,
    Tony
     
    tonydee, Mar 2, 2010
    #3
  4. Rui Maciel

    tonydee Guest

    On Mar 2, 1:04 pm, "Daniel T." <> wrote:
    > tonydee <> wrote:
    > > On Mar 2, 9:54 am, "Daniel T." <> wrote:
    > > > template < typename map_t, typename OutIt>
    > > > void keys(const map_t& aMap, OutIt out)
    > > > {
    > > > typename map_t::const_iterator it = aMap.begin();
    > > > while (it != aMap.end()) {
    > > > typename map_t::key_type key = it++->first;
    > > > out++ = key;
    > > > while (it != aMap.end() && key == it->first)
    > > > ++it;
    > > > }
    > > > }

    >
    > > Needs to be "*out++".

    >
    > You are right of course. I compiled my code with g++ and oddly, it
    > didn't complain about this problem.


    It's not a compilation error... just at run-time it wouldn't have
    copied anything to the output iterator....

    > Maybe this is what Sam was talking
    > about when he complained about my "lone post-increment operator."


    Not sure; sounded like he was saying that the Standard doesn't require
    an output iterator to provide a post-increment operator, which I
    understand you to have denied. I haven't looked myself.

    > >     typename map_t::key_type* p_key = NULL;

    >
    > >     for (typename map_t::const_iterator it = aMap.begin();
    > >          it != aMap.end(); ++it)
    > >     {
    > >         if (p_key and *p_key == it->first)
    > >             continue;
    > >         p_key = &(it->first);
    > >         *out++ = *p_key;
    > >     }

    >
    > I was trying to come up with something along those lines, but it hadn't
    > occurred to me to hold the key in a pointer (which is the only way this
    > idea would work.)


    You could also keep a second iterator, which is arguably a more "STL"-
    ish way to do this, but iterators aren't guaranteed to be as minimal
    as a pointer so it didn't seem as good an idea.

    Cheers,
    Tony
     
    tonydee, Mar 2, 2010
    #4
  5. On 2 mar, 01:35, "Daniel T." <> wrote:
    > In article
    > <>,
    >
    >
    >
    >  Brian <> wrote:
    > > On Feb 28, 5:09 pm, Sam <> wrote:
    > > > Rui Maciel writes:
    > > > > Is there any way to get a list of keys from a multimap besides relying on
    > > > > a couple of nested
    > > > > loops to assemble that list?

    >
    > > > What nested loops? Only one loop is required to iterate over the multimap.

    >
    > > > There is no single function that gives you a set of all keys stored in the
    > > > multimap, but a single loop is all that's needed to retrieve all the keys.
    > > > It's fairly easy to define a template function that gives them to you,
    > > > something like this:

    >
    > > > template<typename multimap_t>
    > > > void keys(const multimap_t &m,
    > > >           std::set<typename multimap_t::key_type> &k)
    > > > {
    > > >     for (typename multimap_t::const_iterator b(m.begin()), e(m.end());
    > > >          b != e; ++b)
    > > >     {
    > > >          k.insert(b->first);
    > > >     }

    >
    > > > }

    >
    > > > The std::set automatically takes care of deduping the multimap's keys..

    >
    > > I think that works fine.  This might speed it up a little:

    >
    > >   template<typename multimap_t>
    > >   void keys(const multimap_t &m,
    > >             std::set<typename multimap_t::key_type> &k)
    > >   {
    > >       typename std::set<typename multimap_t::key_type>::iterator
    > > keys_end = k.end();
    > >       for (typename multimap_t::const_iterator b(m.begin()),
    > > e(m.end());
    > >            b != e; ++b)
    > >       {
    > >            k.insert(keys_end, b->first);
    > >       }
    > >   }

    >
    > > That would work best if k is being passed in
    > > as an empty container as seems likely.

    >
    > Now that I understand the question I can give a better answer than I did
    > the first time around...
    >
    > Using the code below, you don't have to insert into a set, you can
    > insert into any output iterator (of course all of these examples work
    > with both multimaps and regular maps:
    >
    > template < typename map_t, typename OutIt>
    > void keys(const map_t& aMap, OutIt out)
    > {
    >    for (typename map_t::const_iterator it = aMap.begin();
    >          it != aMap.end();
    >          it = aMap.upper_bound(it->first))
    >       out++ = it->first;
    >
    > }

    [snip]

    Another solution is to use decoration:
    template<typename iterator_type>
    class key_iterator:
    std::iterator< typename iterator_type::iterator_category
    // return type of iterator is key type
    , typename iterator_type::value_type::first_type
    , typename iterator_type::difference_type
    >

    {
    public:
    // put here the typedefs iterator_category, ...

    // build from
    key_iterator(const iterator_type& i):it(i){}

    // usual operation on iterator
    key_iterator& operator++()
    { ++it;return *this;}

    view_iterator operator++(int)
    { return key_iterator(it++);}

    bool operator == (const key_iterator& rhs) const
    {return it == rhs.it;}

    // and so on for other iterator operations

    // return key
    reference operator*() const
    {return it->first; }
    pointer operator->() const
    {return &it->first; }

    private:
    iterator_type it;
    };

    And then you can use
    template<class T>
    key_iterator<typename T::iterator_type> key_begin(T& container)
    {
    return container.begin();
    }

    template<class T>
    key_iterator<typename T::iterator_type> key_end(T& container)
    {
    return container.end();
    }

    You can do whatever you want on the keys of an associative container.

    std::accumulate(key_begin(aMap),key_end(aMap), 0 );

    --
    Michael
     
    Michael Doubez, Mar 2, 2010
    #5
  6. On 2 mar, 14:38, "Daniel T." <> wrote:
    > In article
    > <>,
    >  Michael Doubez <> wrote:
    >
    >
    >
    > > Another solution is to use decoration:
    > > template<typename iterator_type>
    > > class key_iterator:
    > >    std::iterator< typename iterator_type::iterator_category
    > >                 // return type of iterator is key type
    > >                 , typename iterator_type::value_type::first_type
    > >                 , typename iterator_type::difference_type

    >
    > > {
    > >   public:
    > >     // put here the typedefs iterator_category,  ...

    >
    > >     // build from
    > >     key_iterator(const iterator_type& i):it(i){}

    >
    > >     // usual operation on iterator
    > >     key_iterator& operator++()
    > >     { ++it;return *this;}

    >
    > >     view_iterator  operator++(int)
    > >     { return key_iterator(it++);}

    >
    > >     bool    operator  == (const key_iterator& rhs) const
    > >     {return it == rhs.it;}

    >
    > >     // and so on for other iterator operations

    >
    > >     // return key
    > >     reference operator*() const
    > >     {return it->first; }
    > >     pointer operator->() const
    > >     {return &it->first; }

    >
    > >   private:
    > >      iterator_type it;
    > > };

    >
    > > And then you can use
    > > template<class T>
    > > key_iterator<typename T::iterator_type> key_begin(T& container)
    > > {
    > >  return container.begin();
    > > }

    >
    > > template<class T>
    > > key_iterator<typename T::iterator_type> key_end(T& container)
    > > {
    > >  return container.end();
    > > }

    >
    > > You can do whatever you want on the keys of an associative container.

    >
    > > std::accumulate(key_begin(aMap),key_end(aMap), 0 );

    >
    > I think part of the point of the exorcise was to remove duplicate keys
    > from the multimap.


    std::unique_copy() with the decorated iterator does the trick.

    --
    Michael
     
    Michael Doubez, Mar 2, 2010
    #6
  7. Rui Maciel

    Pavel Guest

    Daniel T. wrote:
    > Michael Doubez<> wrote:
    >> On 2 mar, 14:38, "Daniel T."<> wrote:
    >>> Michael Doubez<> wrote:
    >>>
    >>>
    >>>
    >>>> Another solution is to use decoration:
    >>>> template<typename iterator_type>
    >>>> class key_iterator:
    >>>> std::iterator< typename iterator_type::iterator_category
    >>>> // return type of iterator is key type
    >>>> , typename iterator_type::value_type::first_type
    >>>> , typename iterator_type::difference_type
    >>>
    >>>> {
    >>>> public:
    >>>> // put here the typedefs iterator_category, ...
    >>>
    >>>> // build from
    >>>> key_iterator(const iterator_type& i):it(i){}
    >>>
    >>>> // usual operation on iterator
    >>>> key_iterator& operator++()
    >>>> { ++it;return *this;}
    >>>
    >>>> view_iterator operator++(int)
    >>>> { return key_iterator(it++);}
    >>>
    >>>> bool operator == (const key_iterator& rhs) const
    >>>> {return it == rhs.it;}
    >>>
    >>>> // and so on for other iterator operations
    >>>
    >>>> // return key
    >>>> reference operator*() const
    >>>> {return it->first; }
    >>>> pointer operator->() const
    >>>> {return&it->first; }
    >>>
    >>>> private:
    >>>> iterator_type it;
    >>>> };
    >>>
    >>>> And then you can use
    >>>> template<class T>
    >>>> key_iterator<typename T::iterator_type> key_begin(T& container)
    >>>> {
    >>>> return container.begin();
    >>>> }
    >>>
    >>>> template<class T>
    >>>> key_iterator<typename T::iterator_type> key_end(T& container)
    >>>> {
    >>>> return container.end();
    >>>> }
    >>>
    >>>> You can do whatever you want on the keys of an associative container.
    >>>
    >>>> std::accumulate(key_begin(aMap),key_end(aMap), 0 );
    >>>
    >>> I think part of the point of the exorcise was to remove duplicate keys
    >>> from the multimap.

    >>
    >> std::unique_copy() with the decorated iterator does the trick.

    >
    > I like this idea better than the ones I came up with. OK if I use it?

    There is a caveat: unique_copy will not work for any comparator. In
    fact, the uniqueness requirement is not well-defined. If it is "leave no
    equivalent keys in terms of map comparator", neither of the proposed
    solutions other than set-based and upper_bound-based will work in
    general. If it's anything else, it depends on even more.. Blame OP :)

    -Pavel
     
    Pavel, Mar 4, 2010
    #7
  8. On 4 mar, 05:40, Pavel
    <> wrote:
    > Daniel T. wrote:
    > > Michael Doubez<>  wrote:
    > >> On 2 mar, 14:38, "Daniel T."<>  wrote:
    > >>> Michael Doubez<>  wrote:

    >
    > >>>> Another solution is to use decoration:
    > >>>> template<typename iterator_type>
    > >>>> class key_iterator:
    > >>>>     std::iterator<  typename iterator_type::iterator_category
    > >>>>                  // return type of iterator is key type
    > >>>>                  , typename iterator_type::value_type::first_type
    > >>>>                  , typename iterator_type::difference_type

    >
    > >>>> {
    > >>>>    public:
    > >>>>      // put here the typedefs iterator_category,  ...

    >
    > >>>>      // build from
    > >>>>      key_iterator(const iterator_type&  i):it(i){}

    >
    > >>>>      // usual operation on iterator
    > >>>>      key_iterator&  operator++()
    > >>>>      { ++it;return *this;}

    >
    > >>>>      view_iterator  operator++(int)
    > >>>>      { return key_iterator(it++);}

    >
    > >>>>      bool    operator  == (const key_iterator&  rhs) const
    > >>>>      {return it == rhs.it;}

    >
    > >>>>      // and so on for other iterator operations

    >
    > >>>>      // return key
    > >>>>      reference operator*() const
    > >>>>      {return it->first; }
    > >>>>      pointer operator->() const
    > >>>>      {return&it->first; }

    >
    > >>>>    private:
    > >>>>       iterator_type it;
    > >>>> };

    >
    > >>>> And then you can use
    > >>>> template<class T>
    > >>>> key_iterator<typename T::iterator_type>  key_begin(T&  container)
    > >>>> {
    > >>>>   return container.begin();
    > >>>> }

    >
    > >>>> template<class T>
    > >>>> key_iterator<typename T::iterator_type>  key_end(T&  container)
    > >>>> {
    > >>>>   return container.end();
    > >>>> }

    >
    > >>>> You can do whatever you want on the keys of an associative container..

    >
    > >>>> std::accumulate(key_begin(aMap),key_end(aMap), 0 );

    >
    > >>> I think part of the point of the exorcise was to remove duplicate keys
    > >>> from the multimap.

    >
    > >> std::unique_copy() with the decorated iterator does the trick.

    >
    > > I like this idea better than the ones I came up with. OK if I use it?

    >
    > There is a caveat: unique_copy will not work for any comparator.


    With a multimap, you are guaranteed the keys are ordered according to
    multimap<>::key_comp().

    unique_copy( key_begin(aMap),key_end(aMap)
    , back_inserter(aResult)
    , aMap.key_comp()
    );

    > In
    > fact, the uniqueness requirement is not well-defined. If it is "leave no
    > equivalent keys in terms of map comparator", neither of the proposed
    > solutions other than set-based and upper_bound-based will work in
    > general. If it's anything else, it depends on even more.. Blame OP :)


    The general solution however entails to copy the keys and sort/unique
    them according to a comparison operator (after all the container could
    have been an unordered_multimap). If the key supported only an
    equality operator, things could get really hairy in terms of
    complexity.

    With a sorted container, we can take a few shortcut; IMO that was the
    point of the exercise. (And if it was not, t'was still a nice chat)

    --
    Michael
     
    Michael Doubez, Mar 4, 2010
    #8
    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. He Shiming
    Replies:
    3
    Views:
    3,911
    He Shiming
    Dec 26, 2004
  2. PeteOlcott

    std::multimap with composite key?

    PeteOlcott, Jan 19, 2009, in forum: C++
    Replies:
    5
    Views:
    3,379
    Daniel T.
    Jan 22, 2009
  3. Victor Bazarov
    Replies:
    15
    Views:
    1,215
    Vaclav Haisman
    Aug 16, 2009
  4. M P
    Replies:
    1
    Views:
    549
  5. fish
    Replies:
    1
    Views:
    307
Loading...

Share This Page