idiomatic C++ for creating a std::vector from the last n elements of a std::map

Question

What is the C++ idiomatic way of creating a std::vector from the last n elements of a std::map?

I am not interested in preserving the order in the vector.

I can copy the elements, like this:

    std::map< double, MyType > m;
    size_t n = 3;
    std::vector< MyType > v;
    std::map< double, MyType >::iterator it = m.end();
    while ( n-- ) { // assuming m.size() >= n
        it--;
        v.push_back(it->second);
    }

But, is there any other way, more idiomatic, to do it?

Answer 1

std::copy would be suitable if you wanted to copy the types unchanged. However, std::map<T,U>::iterator_type::value_type is not U (the type you want to copy), but std::pair<T,U> (in other words, dereferencing a map iterator yields a pair of the key and value types), so a raw copy won't work.

So we need to copy the elements, performing a transformation along the way. That's what std::transform is for.

For convenience, I'm going to assume that your compiler supports C++11 lambda expressions and the auto keyword. If not, it can be fairly trivially rewritten as a functor. But we're looking for something roughly like this:

std::transform(map_first, map_last, std::back_inserter(vec), [](std::pair<double,MyType> p) { return p.second; });

Now we just need to fill in the two first parameters:

auto map_first = std::next(map.end(), -n); 
auto map_last = map.end();

The only tricky part here is that map iterators are bidirectional, but not random-access, so we can't simply say map.end() - n. The - operator is not defined. Instead, we have to use std::next (which takes linear rather than constant time for bidirectional operators, but there's no way around that).

(Note, I haven't tried compiling this code, so it might require a small bit of tweaking)