Сортировать, когда доступно только равенство
Предположим, у нас есть вектор пар:
std::vector<std::pair<A,B>> v;
где для типа A определяется только равенство:
bool operator==(A const & lhs, A const & rhs) { ... }
Как бы вы отсортировали все пары с одинаковыми first элемент будет в конечном итоге близко? Чтобы было ясно, результат, который я надеюсь достичь, должен быть таким же, как и что-то вроде этого:
std::unordered_multimap<A,B> m(v.begin(),v.end());
std::copy(m.begin(),m.end(),v.begin());
Однако я хотел бы, если возможно, чтобы:
- Сделайте сортировку на месте.
- Избегайте необходимости определять хэш-функции для равенства.
Редактировать: дополнительная конкретная информация.
В моем случае число элементов не особенно велико (я ожидаю, что N = 10 ~ 1000), хотя я должен повторить эту сортировку много раз (~ 400) как часть более крупного алгоритма, а тип данных, известный как A довольно большой (он содержит среди прочего unordered_map с ~ 20 std::pair<uint32_t,uint32_t> в нем — структура, которая мешает мне придумывать порядок и затрудняет создание хеш-функции)
Решение
Первый вариант: cluster() а также sort_within()
Рукописный двойной цикл @MadScienceDreams можно записать в виде cluster() алгоритм O(N * K) сложность с N элементы и K кластеры. Это неоднократно звонит std::partition (используя стиль C ++ 14 с общими лямбдами, легко адаптируемый к стилю C ++ 1 или даже к стилю C ++ 98 путем написания ваших собственных функциональных объектов):
template<class FwdIt, class Equal = std::equal_to<>>
void cluster(FwdIt first, FwdIt last, Equal eq = Equal{})
{
for (auto it = first; it != last; /* increment inside loop */)
it = std::partition(it, last, [=](auto const& elem){
return eq(elem, *it);
});
}
который вы называете на ваш вклад vector<std::pair> как
cluster(begin(v), end(v), [](auto const& L, auto const& R){
return L.first == R.first;
});
Следующий алгоритм для записи sort_within который принимает два предиката: объект функции равенства и сравнения и многократно вызывает std::find_if_not чтобы найти конец текущего диапазона, а затем std::sort сортировать в этом диапазоне:
template<class RndIt, class Equal = std::equal_to<>, class Compare = std::less<>>
void sort_within(RndIt first, RndIt last, Equal eq = Equal{}, Compare cmp = Compare{})
{
for (auto it = first; it != last; /* increment inside loop */) {
auto next = std::find_if_not(it, last, [=](auto const& elem){
return eq(elem, *it);
});
std::sort(it, next, cmp);
it = next;
}
}
На уже кластеризованном входе вы можете назвать его так:
sort_within(begin(v), end(v),
[](auto const& L, auto const& R){ return L.first == R.first; },
[](auto const& L, auto const& R){ return L.second < R.second; }
);
Живой пример что показывает это для некоторых реальных данных, используя std::pair<int, int>,
Второй вариант: пользовательское сравнение
Даже если нет operator< определено на AВы можете определить это сами. Здесь есть два широких варианта. Во-первых, если A можно определить, можно определить
bool operator<(A const& L, A const& R)
{
return std::hash<A>()(L) < std::hash<A>()(R);
}
и писать std::sort(begin(v), end(v)) непосредственно. У вас будет O(N log N) звонки в std::hash если вы не хотите кэшировать все уникальные значения хеша в отдельном хранилище.
Во-вторых, если A не может быть хэшируемым, но имеет методы получения членов данных x(), y() а также z(), которые однозначно определяют равенство на A: ты можешь сделать
bool operator<(A const& L, A const& R)
{
return std::tie(L.x(), L.y(), L.z()) < std::tie(R.x(), R.y(), R.z());
}
Опять можно написать std::sort(begin(v), end(v)) непосредственно.
Другие решения
если вы можете придумать функцию, которая присваивает каждому уникальному элементу уникальный номер, то вы можете построить вторичный массив с этими уникальными номерами, а затем отсортировать вторичный массив и с ним первичный, например, с помощью сортировки слиянием.
Но в этом случае вам нужна функция, которая присваивает каждому уникальному элементу уникальный номер, то есть хэш-функцию без коллизий. Я думаю, что это не должно быть проблемой.
И асимптотика этого решения, если хэш-функция имеет O (1), то создание вторичного массива — это O (N), а сортировка по первичному — O (NlogN). И резюме O (N + NlogN) = O (N logN).
И плохой стороной этого решения является то, что оно требует двойной памяти.
В заключение, основной смысл этого решения заключается в том, чтобы быстро перевести ваши элементы в элементы, которые вы можете быстро сравнить.
Алгоритм на месте
for (int i = 0; i < n-2; i++)
{
for (int j = i+2; j < n; j++)
{
if (v[j].first == v[i].first)
{
std::swap(v[j],v[i+1]);
i++;
}
}
Возможно, существует более элегантный способ написания цикла, но это O (n * m), где n — количество элементов, а m — количество ключей. Таким образом, если m намного меньше n (в лучшем случае, когда все ключи одинаковы), это может быть аппроксимировано O (n). В худшем случае номер ключа ~ = n, так что это O (n ^ 2). Я понятия не имею, что вы ожидаете от количества ключей, поэтому я не могу сделать средний случай, но, скорее всего, O (n ^ 2) также для среднего случая.
Для небольшого количества ключей это может работать быстрее, чем неупорядоченная мультикарта, но вам придется измерить, чтобы это выяснить.
Примечание: порядок кластеров полностью случайный.
Редактировать: (гораздо эффективнее в частично кластеризованном случае, не меняет сложности)
for (int i = 0; i < n-2; i++)
{
for(;i<n-2 && v[i+1].first==v[i].first; i++){}
for (int j = i+2; j < n; j++)
{
if (v[j].first == v[i].first)
{
std::swap(v[j],v[i+1]);
i++;
}
}
Редактировать 2: В / u / MrPisarik комментарий, удаленный избыточный я проверяю во внутреннем цикле.
Я удивлен, что никто не предложил использовать std::partition еще. Это делает решение красивым, элегантным и общим:
template<typename BidirIt, typename BinaryPredicate>
void equivalence_partition(BidirIt first, BidirIt last, BinaryPredicate p) {
using element_type = typename std::decay<decltype(*first)>::type;
if(first == last) {
return;
}
auto new_first = std::partition
(first, last, [=](element_type const &rhs) { return p(*first, rhs); });
equivalence_partition(new_first, last, p);
}
template<typename BidirIt>
void equivalence_partition(BidirIt first, BidirIt last) {
using element_type = typename std::decay<decltype(*first)>::type;
equivalence_partition(first, last, std::equal_to<element_type>());
}
пример Вот.