How can I apply a function to each value of a map to create a sorted sequence?

Question

Using STL in C++, how would I go about applying a function to each value in a std::map to get a std::string (printed representation of the value) and collect the std::string(s) into a collection that is sorted by a floating point key which comes from another function applied to each corresponding value in the map?

Stated another way, I want to iterate over the key value pairs in the map and create a new set of key value pairs where the new key and value are a function of the old value.

double getNewKey(origValue value);
std::string getNewValue(origValue value);
// Or is it better to map both at once in a pair?
std::pair<double, std::string> getNewPair(origValue value);

std::map<origKey, origValue> origMap;

// Perform some transformation on each value of origMap to get a new map:
std::map<double, std::string> transformedMap =
  /* What goes here to use getNewKey() and getNewValue() or use getNewPair()? */
  ;

But, please without using C++11.

Answer 1

std::transform is what you need:

#include <map>
#include <algorithm>
#include <iterator>
#include <iostream>

// using a few C++11 features to make life easier
int main(){
  std::map<int, int> src, dst; // example KV pair
  for(unsigned i=0; i < 10; ++i)
    src[i] = i;
  typedef std::map<int, int>::value_type kv_pair;
  std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()),
      [](kv_pair const& p){
        return kv_pair(p.first, p.second * 2);
      });
  for(auto& p : dst)
    std::cout << p.first << " : " << p.second << "\n";
}

Live example.