Pick random element subset from map

I have a map of elements:

   std::map<char,int> values;

   first['a']=10;
   first['b']=30;
   first['c']=50;
   first['d']=70;
   first['e']=90;
   first['f']=100;
   first['g']=120;

So I need to pick N elements from values as a map of pairs preferably (output format as well as input format).

I tried other different solutions from stackoverflow but they mostly applicable for vector not for any type of C++ 11 container or looks too complicated for me.

I need some more effective way than just random_shuffle which actually mutates C++ container.

Also it would be nice if this function would be applicable for any type of C++ container.