Эквивалент сортировки списка Python с ключом / преобразование Шварца

Question

Эквивалент сортировки списка Python с ключом / преобразование Шварца

В Python, учитывая список, я могу отсортировать его по ключевой функции, например:

>>> 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(),

Есть ли эквивалент в C ++? std::sort() только позволяет мне предоставить пользовательский компаратор (эквивалент Python items.sort(cmp=...)), а не ключевая функция. Если нет, есть ли какая-либо хорошо протестированная, эффективная, общедоступная реализация эквивалента, которую я могу добавить в свой код?

Обратите внимание, что версия Python вызывает только key функционировать один раз за элемент, а не дважды за сравнение.

7

c++equivalent python sorting

Решение

Другие решения

Если тип ключа не очень большой (если это так, мера, я бы сказал), вы можете просто сохранить

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

вместо вашего «нормального» вектора значений. Затем вы можете вычислить и сохранить ключи ровно один раз, а затем просто использовать std::sort,

Другой, но навязчивый метод — предоставить ключ в качестве члена и затем кэшировать его. Это имеет то преимущество, что вам не нужно связываться с pairкаждый раз, когда вы получаете доступ к своему вектору.

2

Источник

Accepted Answer

Вы можете просто свернуть свой собственный:

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

Или, если это слишком глупо, вот мое оригинальное решение, которое требует от нас написать свое 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());
}

Хотя теперь мы должны переопределить быструю сортировку:

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

Который, приведя простой пример:

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
}

3