Re: Multimap: how to get a key list?
In article
<d0b0d95f-293e-4556-a824-b96a9ebb8274@15g2000yqi.googlegroups.com>,
Brian <coal@mailvault.com> wrote:
On Feb 28, 5:09?pm, Sam <s...@email-scan.com> 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;
}
However, depending on the number of elements in the map with the same
key, the OP's idea of using two loops may be the fastest.
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; // (a)
out++ = key;
while (key == it->first)
++it;
}
}
Some people might find the post-increment operator usage at (a) kind of
off putting; if so, just add a line pre-incrementing it after that line.