Re: Multimap: how to get a key list?

From:

Michael Doubez <michael.doubez@free.fr>

Newsgroups:

comp.lang.c++

Date:

Thu, 4 Mar 2010 01:32:23 -0800 (PST)

Message-ID:

<076c2c88-2fa6-42cb-ac7e-a7844a6bd934@y11g2000yqh.googlegroups.com>

On 4 mar, 05:40, Pavel
<pauldontspamt...@removeyourself.dontspam.yahoo> wrote:

Daniel T. wrote:

Michael Doubez<michael.dou...@free.fr> wrote:

On 2 mar, 14:38, "Daniel T."<danie...@earthlink.net> wrote:

Michael Doubez<michael.dou...@free.fr> 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_t=

ype::first_type

, typename iterator_type::differe=

nce_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& rh=

s) 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 key=

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