Re: Multimap: how to get a key list?

On Mar 2, 9:54 am, "Daniel T." <danie...@earthlink.net> wrote:


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::operator=(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