Idiomatic C ++ to create std :: vector from the last n elements of std :: map

Question

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

I'm not interested in maintaining order in the vector.

I can copy elements, for example:

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 another way, more idiomatic, to do this?

Answer 1

std::copy is suitable if you want to copy types without changes. However, std::map<T,U>::iterator_type::value_type not U (the type you want to copy), but std::pair<T,U> (in other words, dereferencing the map iterator gives a couple of types of keys and values ), so the original copy will not work.

So, we need to copy the elements, performing the conversion on this path. Why std::transform .

For convenience, I'm going to assume that your compiler supports C ++ 11 lambda expressions and the auto keyword. If not, then it can simply be trivially rewritten as a functor. But we are looking for something 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 first two 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, so we cannot just say map.end() - n . The operator - not defined. Instead, we should use std::next (which for bi-directional operators takes not linear, but constant time, but there is no way).

(Note, I have not tried compiling this code, so a little tweaking may be required)

Answer 2

std::transform would be the most idiomatic way. You need a functional object:

 template<typename PairType> struct Second { typename PairType::second_type operator()( PairType const& obj ) const { return obj.second; } } 

(If you work a lot with std::map or other things that use std::pair , you will get this in your tool.)

After that, this is a little inconvenient because you only need the last n. since iterators in the map are not random access iterators, and you cannot add or subtract arbitrary values, the easiest solution is to copy them, then delete the ones you don't want:

 std::vector<MyType> extractLastN( std::map<double, MyType> const& source, size_t n ) { std::vector<MyType> results; std::transform( source.begin(), source.end(), std::back_inserter( results ), Second<std::map<double, MyType>::value_type>() ); if ( results.size() > n ) { results.erase( results.begin(), results.end() - n ); } return results; } 

This is not the most efficient, but depending on n and where it might be enough. If you want to avoid additional copying, etc. (probably worth it only if n usually much smaller than the size of the map), you will need to do something more pleasant:

 std::vector<MyType> extractLastN( std::map<double, MyType> const& source, ptrdiff_t n ) { std::map<double, MyType>::const_iterator start = source.size() <= n ? source.begin() : std::prev( source.end(), n ); std::vector<MyType> results; std::transform( start, source.end(), std::back_inserter( results ), Second<std::map<double, MyType>::value_type>() ); return results; } 

(If you don't have access to C ++ 11, std::prev simply:

 template<typename IteratorType> IteratorType prev( IteratorType start, ptrdiff_t n ) { std::advance( start, -n ); return start; } 

Again, if you work a lot with the standard library, you probably already have it in your toolbox.)

Answer 3

Here's a simple version of Boost.Range:

 #include <boost/range/iterator_range_core.hpp> #include <boost/range/adaptor/map.hpp> //#include <boost/range/adaptor/reversed.hpp> // comment in for 'reversed' #include <map> #include <vector> struct X{}; int main(){ std::map<int, X> m; unsigned n = 0; auto vec(boost::copy_range<std::vector<X>>( boost::make_iterator_range(m, m.size()-n, 0) | boost::adaptors::map_values //| boost::adaptors::reversed // comment in to copy in reverse order )); } 

Answer 4

One way to do this is to use a simple for_each :

  map<int,double> m; vector<double> v; //Fill map auto siter = m.end(); advance(siter, -3); for_each(siter, m.end(), [&](pair<int,double> p) { v.push_back(p.second); }); 

EDIT It's even easier to use std::prev with for_each :

  map<int,double> m; vector<double> v; //Fill map for_each(prev(m.end(), 3), m.end(), [&](pair<int,double> p) { v.push_back(p.second); }); 

In addition, if you want to fill the vector in reverse order, you can use:

 for_each(m.rbegin(), next(m.rbegin(), 3), [&](pair<int,double> p) { v.push_back(p.second); }); 

Answer 5

Do it back:

 assert(n <= m.size()); std::copy(m.rbegin(), m.rbegin()+n, std::back_inserter(v)); 

bidirectional FTW iterators.

---

OK, I obviously haven't woken up yet, and that was wishful thinking. I still prefer to go back to get the last n, though, so the working version looks like this:

 #include <map> #include <vector> #include <algorithm> #include <iterator> using namespace std; // I'm assuming it ok to copy min(m.size(), n) template <typename Iter> Iter safe_advance(Iter begin, Iter const &end, int distance) { while(distance-- > 0 && begin != end) ++begin; return begin; } void copy_last_n(map<double,int> const &m, vector<int> &v, int n) { transform(m.rbegin(), safe_advance(m.rbegin(), m.rend(), n), back_inserter(v), [](map<double,int>::value_type const &val) { return val.second; } ); } 

James Kanze already wrote the Second functor - use this if you don't have access to lambdas.

Answer 6

First, what do we want to write to be idiomatic? I suggest:

 std::vector<Mytype> v; v.reserve(n); std::transform( limited(n, m.rbegin()), limited_end(m.rend()), std::back_inserter(v), values_from(m) ); 

Now we need to make this code valid.

We can replace values_from(m) with lambda (which m does not need) or implement it using the James Canze Second class (in this case, m exists for type inference):

 template <typename Map> Second<Map::value_type> values_from(const Map &) { return Second<Map::value_type>(); } 

Implementing limited is a bit of a pain. This is a template function that returns an iterator. The type of iterator that it returns is a template that wraps another type of iterator and forwards everything to it, except that it tracks n and acts like a trailing iterator when it has been expanded n times. limited_end returns a final iterator of the same type, so it compares the same either if the underlying iterators are equal, or if one of the iterators was created using limited_end and the other one fired n to zero.

I don't have code for this convenient, but basically you get the _n equivalents of all standard algorithms, not just copy_n . In this case, we want transform_n , but it is not.

An alternative to transform would be to use copy_n with boost::transform_iterator wrapped around m.rbegin() . I will not do this either, because I always need to check documents for using transform_iterator .