equivalente di Python elenco di ordinamento con la chiave/Trasformata di Schwartz

Question

In Python, data una lista, posso ordinarlo da una funzione chiave, ad esempio:

>>> 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 for a 
heavy computation for b 
heavy computation for c 
heavy computation for d 
>>> items 
['d', 'b', 'c', 'a'] 

Come si vede, la lista non era ordinato in modo alfanumerico, ma da il valore restituito di get_value().

Esiste un equivalente in C++? std::sort() mi consente solo di fornire un comparatore personalizzato (equivalente a Python items.sort(cmp=...)), non una funzione chiave. In caso contrario, è disponibile un'implementazione ben collaudata, efficiente e pubblicamente disponibile dell'equivalente che posso inserire nel mio codice?

Si noti che la versione Python chiama solo la funzione key una volta per elemento, non due per confronto.

Answer 1

Si potrebbe semplicemente rotolare il proprio:

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); 
    }); 
} 

Se KeyFunc è troppo costoso, si dovrà creare un vettore separato con i valori.

Possiamo anche incidere insieme una classe che ci permetterà di utilizzare ancora 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); 

    for (; first != last; ++first) { 
     ordering.emplace_back(func(*first), first); 
    } 

    std::sort(ordering.begin(), ordering.end()); 
} 

Oppure, se questo è troppo hacky, ecco la mia soluzione originale, che ci impone di scrivere il nostro 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); 

    for (; first != last; ++first) { 
     ordering.emplace_back(func(*first), first); 
    } 

    // now sort this vector by the ordering - we're going 
    // to sort ordering, but each swap has to do iter_swap too 
    quicksort_with_benefits(ordering, 0, ordering.size()); 
} 

Anche se ora dobbiamo reimplementare 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 i = p; 
    for (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; 
} 

.210

Il che, dato un semplice esempio:

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 
} 

Answer 2

Se il tipo di chiave non è molto grande (se lo è, misurare direi), si può solo salvare un

std::vector< std::pair<key_type, value_type>> vec; 

invece di il tuo vettore di valore "normale". È quindi possibile calcolare e proteggere i tasti esattamente una volta e quindi utilizzare semplicemente std::sort.

Un altro metodo, ma intrusivo, fornirebbe la chiave come membro e quindi la memorizzerà nella cache. Ciò avrebbe il vantaggio che non è necessario pasticciare con lo pair s ogni volta che si accede al vettore.