Multimap: how to get a key list?

[Rui Maciel]

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

 

[Brian]

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

 

[tonydee]

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: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]

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.

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

 

[Michael Doubez]

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 Doubez]

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.

 

[Pavel]

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

 

[Michael Doubez]

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)