कुंजी के साथ अजगर की सूची तरह के समतुल्य/Schwartzian

Question

बदलने अजगर में, एक सूची दी है, मैं, एक महत्वपूर्ण समारोह से यह सॉर्ट कर सकते हैं जैसे:

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

जैसा कि आप देख, सूची नहीं हल कर रहा था alphanumerically लेकिन द्वारा get_value() का वापसी मूल्य।

क्या सी ++ में समतुल्य है? std::sort() केवल मुझे एक कस्टम तुलनित्र (पायथन के items.sort(cmp=...) के बराबर) प्रदान करने की अनुमति देता है, एक महत्वपूर्ण कार्य नहीं। यदि नहीं, तो क्या मेरे कोड में समकक्ष समकक्ष के किसी भी परीक्षण, कुशल, सार्वजनिक रूप से उपलब्ध कार्यान्वयन है?

ध्यान दें कि पायथन संस्करण केवल प्रति तत्व एक बार key फ़ंक्शन को कॉल करता है, प्रति तुलना में दो बार नहीं।

Answer 1

तुम सिर्फ अपने खुद के रोल कर सकते हैं:

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

तो KeyFunc बहुत महंगा है, तो आप मूल्यों के साथ एक अलग वेक्टर बनाना होगा।

हम भी एक साथ एक वर्ग है कि हम अभी भी उपयोग करने की अनुमति देगा हैक कर सकते हैं 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()); 
} 

या, कि अगर बहुत hacky है, यहाँ अपने मूल समाधान है, जो हमें हमारे अपने 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()); 
} 

अब हालांकि हम 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 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

कौन सा, एक सरल उदाहरण दिया:

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

तो कुंजी प्रकार बहुत बड़ा नहीं है (अगर ऐसा है, को मापने मैं कहना चाहते हैं), तो आप सिर्फ एक

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

बजाय बचा सकता है आपका "सामान्य" मूल्य वेक्टर। फिर आप एक बार ठीक से चाबियाँ और सुरक्षित कर सकते हैं और फिर std::sort का उपयोग कर सकते हैं।

एक और, लेकिन घुसपैठ विधि सदस्य के रूप में कुंजी प्रदान करेगी और फिर इसे कैशिंग करेगी। यह लाभ होगा कि जब भी आप अपने वेक्टर तक पहुंचते हैं तो आपको pair एस के साथ गड़बड़ करने की आवश्यकता नहीं है।