Äquivalent von Pythons Liste sortieren mit Schlüssel / Schwartzian-Transformation

In Python, bei einer Liste, kann ich es durch eine Tastenfunktion sortieren, zB:

>>> 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'] 

Wie Sie sehen, wurde die Liste nicht alphanumerisch sortiert, sondern durch den Rückgabewert von get_value() .

Gibt es ein Äquivalent in C ++? std::sort() erlaubt mir nur einen kundenspezifischen komparator (äquivalent von Pythons items.sort(cmp=...) ), keine Schlüsselfunktion. Wenn nicht, gibt es eine gut getestete, effiziente, öffentlich vorhandene Umsetzung des Äquivalents kann ich in meinen Code fallen

Beachten Sie, dass die Python-Version nur einmal die key einmal pro Element anruft, nicht zweimal pro Vergleich.

  • Python Math - TypeError: 'NoneType' Objekt ist nicht abonnierbar
  • Pandas gruppieren in Gruppen
  • Sortieren eines Wörterbuches hierarchisch und alphabetisch (Python)
  • So sortiere ich 2 Element Tupel von Strings in Mischauftrag mit Schlüssel Parameter (nicht cmp)
  • Schnell sortieren python rekursion
  • Sortierung von Konturen nach rechts in Python (OpenCV)
  • Numerische Sortierung einer Spalte mit Zahlen und Strings (Pandas / Python)
  • Wie man per Schlüssel (alphabetisch) in defaultdict (Liste) für einen invertierten Index anordnet
  • 2 Solutions collect form web for “Äquivalent von Pythons Liste sortieren mit Schlüssel / Schwartzian-Transformation”

    Du könntest einfach deine eigenen rollen:

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

    Wenn KeyFunc zu teuer ist, musst du einen separaten Vektor mit den Werten erstellen.

    Wir können sogar zusammen eine Klasse, die uns erlauben wird, immer noch 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()); } 

    Oder wenn das zu hackig ist, hier ist meine ursprüngliche Lösung, die uns erlaubt, unsere eigene sort zu schreiben

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

    Zwar müssen wir jetzt den Quicksort reimplementieren:

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

    Was bei einem einfachen Beispiel:

     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 } 

    Wenn der Key-Typ ist nicht schrecklich riesig (wenn es ist, messen würde ich sagen), können Sie nur speichern ein

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

    Anstelle von Ihrem "normalen" Wertvektor. Sie können dann die Schlüssel genau einmal berechnen und sichern und dann einfach std::sort .

    Eine andere, aber aufdringliche Methode würde den Schlüssel als Mitglied bereitstellen und ihn dann zwischenspeichern. Dies würde den Vorteil haben, dass du dich nicht jedes Mal mit dem pair verwirren musst.

    Python ist die beste Programmiersprache der Welt.