c++ - Equivalent of Python's list sort with key / Schwartzian transform -

in python, given list, can sort key function, e.g.:

>>> def get_value(k): ...     print "heavy computation for", k ...     return {"a": 100, "b": 30, "c": 50, "d": 0}[k] ... >>> items = ['a', 'b', 'c', 'd'] >>> items.sort(key=get_value) heavy computation heavy computation b heavy computation c heavy computation d >>> items ['d', 'b', 'c', 'a'] 

as see, list sorted not alphanumerically return value of get_value().

is there equivalent in c++? std::sort() allows me provide custom comparator (equivalent of python's items.sort(cmp=...)), not key function. if not, there well-tested, efficient, publicly available implementation of equivalent can drop code?

note python version calls key function once per element, not twice per comparison.

you roll own:

template <typename randomit, typename keyfunc> void sort_by_key(randomit first, randomit last, keyfunc func)  {     using value = decltype(*first);     std::sort(first, last, [=](const valuetype& a, const valuetype& b) {         return func(a) < func(b);     }); } 

if keyfunc expensive, you'll have create separate vector values.

we can hack class allow still use std::sort:

template <typename randomiter, typename keyfunc> void sort_by_key(randomiter first, randomiter last, keyfunc func) {     using keyt = decltype(func(*first));     using valuet = typename std::remove_reference<decltype(*first)>::type;      struct pair {         keyt key;         randomiter iter;         boost::optional<valuet> value;          pair(const keyt& key, const randomiter& iter)             : key(key), iter(iter)         { }          pair(pair&& rhs)             : key(std::move(rhs.key))             , iter(rhs.iter)             , value(std::move(*(rhs.iter)))         { }          pair& operator=(pair&& rhs) {             key = std::move(rhs.key);             *iter = std::move(rhs.value ? *rhs.value : *rhs.iter);             value = boost::none;             return *this;         }          bool operator<(const pair& rhs) const {             return key < rhs.key;         }     };      std::vector<pair> ordering;     ordering.reserve(last - first);      (; first != last; ++first) {         ordering.emplace_back(func(*first), first);     }      std::sort(ordering.begin(), ordering.end()); } 

or, if that's hacky, here's original solution, requires write our own sort

template <typename randomit, typename keyfunc> void sort_by_key_2(randomit first, randomit last, keyfunc func) {     using keyt = decltype(func(*first));     std::vector<std::pair<keyt, randomit> > ordering;     ordering.reserve(last - first);      (; first != last; ++first) {         ordering.emplace_back(func(*first), first);     }      // sort vector ordering - we're going     // sort ordering, each swap has iter_swap     quicksort_with_benefits(ordering, 0, ordering.size()); } 

although have reimplement quicksort:

template <typename key, typename iter> void quicksort_with_benefits(std::vector<std::pair<key,iter>>& a, size_t p, size_t q) {     if (p < q) {         size_t r = partition_with_benefits(a, p, q);         quicksort_with_benefits(a, p, r);         quicksort_with_benefits(a, r+1, q);     } }  template <typename key, typename iter> size_t partition_with_benefits(std::vector<std::pair<key,iter>>& a, size_t p, size_t q) {     auto key = a[p].first;     size_t = p;     (size_t j = p+1; j < q; ++j) {         if (a[j].first < key) {             ++i;             std::swap(a[i].first, a[j].first);             std::iter_swap(a[i].second, a[j].second);         }     }      if (i != p) {         std::swap(a[i].first, a[p].first);         std::iter_swap(a[i].second, a[p].second);     }     return i; } 

which, given simple example:

int main() {     std::vector<int> v = {-2, 10, 4, 12, -1, -25};      std::sort(v.begin(), v.end());     print(v); // -25 -2 -1 4 10 12      sort_by_key_2(v.begin(), v.end(), [](int i) { return i*i; });      print(v); // -1 -2 4 10 12 -25 }