等效于带有键/Schwartzian转换的Python列表排序 [英] Equivalent of Python's list sort with key / Schwartzian transform

问题描述

在Python中，给定一个列表，我可以按一个键函数对其进行排序，例如:

In Python, given a list, I can sort it by a 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 for a
heavy computation for b
heavy computation for c
heavy computation for d
>>> items
['d', 'b', 'c', 'a']

如您所见，列表不是按字母数字排序的，而是按返回值get_value()排序的.

As you see, the list was sorted not alphanumerically but by the return value of get_value().

C ++是否有等效功能? std::sort()仅允许我提供一个自定义比较器(等效于Python的items.sort(cmp=...))，而不是键函数.如果没有，我是否可以在我的代码中找到经过测试的，有效的，可公开获得的等效方法?

Is there an equivalent in C++? std::sort() only allows me to provide a custom comparator (equivalent of Python's items.sort(cmp=...)), not a key function. If not, is there any well-tested, efficient, publicly available implementation of the equivalent I can drop into my code?

请注意，Python版本仅每个元素调用一次key函数，而不是每个比较调用两次.

Note that the Python version only calls the key function once per element, not twice per comparison.

推荐答案

您可以自己滚动:

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太昂贵，则必须使用值创建一个单独的向量.

If KeyFunc is too expensive, you'll have to create a separate vector with the values.

我们甚至可以一起破解一个类，使我们仍然可以使用std::sort:

We can even hack together a class that will allow us to 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);

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

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

或者，如果这太过分了，这就是我原来的解决方案，它要求我们编写自己的sort

Or, if that's too hacky, here's my original solution, which requires us to 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);

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

尽管现在我们必须重新实现quicksort:

Although now we have to 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;
}

下面给出一个简单的示例:

Which, given a 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
}

这篇关于等效于带有键/Schwartzian转换的Python列表排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！