Сортировка вектора по убыванию в двух диапазонах

14

Скажем, у меня есть вектор целых чисел:

std::vector<int> indices;
for (int i=0; i<15; i++) indices.push_back(i);

Затем я сортирую это в порядке убывания:

sort(indices.begin(), indices.end(), [](int first, int second) -> bool{return indices[first] > indices[second];})
for (int i=0; i<15; i++) printf("%i\n", indices[i]);

Это производит следующее:

14
13
12
11
10
9
8
7
6
5
4
3
2
1
0

Теперь я хочу, чтобы числа 3, 4, 5 и 6 были перемещены до конца, и сохранить для них нисходящий порядок (желательно без необходимости sortповторного использования). То есть вот что я хочу:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3

Как мне изменить функцию сравнения std::sortдля достижения этого?

Юрий
источник
4
return indices[first] > indices[second]Ты имеешь в виду return first < second;?
acraig5075
2
Для простой сортировки по убыванию, вместо лямбды можно использовать std::greaterfrom <functional>. Что касается вашего вопроса, написание более подробного компаратора, который гарантирует, что ваши значения сравниваются так, как вы хотите, может быть самым простым способом сделать это.
между
4
@ acraig5075, в порядке убывания это должно быть return first > second.
ks1322
1
@ acraig5075 Я чувствую, что что-то упустил, или люди не знают разницы между восходящим и нисходящим ?
между
3
Может быть, вы ищете std :: rotate ?
супер

Ответы:

8

Ваша функция сравнения неверна, так как значения, которые вы получаете как firstи secondявляются элементами std::vector. Следовательно, нет необходимости использовать их в качестве индексов. Итак, вам нужно изменить

return indices[first] > indices[second];

в

return first > second;

Теперь о проблеме, которую вы пытаетесь решить ...

Вы можете оставить 3, 4, 5 и 6 вне сравнения с другими элементами и сравнить их друг с другом:

std::sort(
    indices.begin(), indices.end(),
    [](int first, int second) -> bool {
        bool first_special = first >= 3 && first <= 6;
        bool second_special = second >= 3 && second <= 6;
        if (first_special != second_special)
            return second_special;
        else
            return first > second;
    }
);

демонстрация

Щелкунчик
источник
@NutCracker Да, я согласен, что лучше, чтобы сначала был верхний критерий.
переполнение кучи
5

Функции из библиотеки стандартных алгоритмов , как iota, sort, find, rotateи copyсделают вашу жизнь проще. Ваш пример сводится к:

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>


int main()
{
  std::vector<int> indices(15);
  std::iota(indices.begin(), indices.end(), 0);
  std::sort(indices.begin(), indices.end(), std::greater<>());

  auto a = std::find(indices.begin(), indices.end(), 6);
  auto b = std::find(indices.begin(), indices.end(), 3);
  std::rotate(a, b + 1, indices.end());

  std::copy(indices.begin(), indices.end(), std::ostream_iterator<int>(std::cout, "\n"));
  return 0;
}

Вывод:

14
13
12
11
10
9
8
7
2
1
0
6
5
4
3


@TedLyngmo в комментариях показывает, что его можно / нужно улучшить с помощью:

auto a = std::lower_bound(indices.begin(), indices.end(), 6, std::greater<int>{});
auto b = a + 4;
acraig5075
источник
auto b = a + 4;неправильно (если вы хотите сохранить соответствие с предыдущим фрагментом). Это должно быть auto b = a + 3;потому, что std::rotateвы используетеb + 1
Biagio Festa
3

Решение 1

Простой подход с нелинейным компаратором.

inline constexpr bool SpecialNumber(const int n) noexcept {
  return n < 7 && 2 < n;
}

void StrangeSortSol1(std::vector<int>* v) {
  std::sort(v->begin(), v->end(), [](const int a, const int b) noexcept {
    const bool aSpecial = SpecialNumber(a);
    const bool bSpecial = SpecialNumber(b);

    if (aSpecial && bSpecial) return b < a;
    if (aSpecial) return false;
    if (bSpecial) return true;
    return b < a;
  });
}

Решение 2

Используя std::algorithms (раздел)!

inline constexpr bool SpecialNumber(const int n) noexcept {
  return n < 7 && 2 < n;
}

void StrangeSortSol2(std::vector<int>* v) {
  auto pivot = std::partition(v->begin(), v->end(), std::not_fn(SpecialNumber));
  std::sort(v->begin(), pivot, std::greater{});
  std::sort(pivot, v->end(), std::greater{});
}

Вопросы производительности

Может показаться, что второе решение медленнее из-за перегрузки раздела. Вероятно, нет, из-за предсказания кеша и ошибки ветвления в современных процессорах.

эталонный тест

Бьяджо Феста
источник
Любой хороший компилятор должен преобразовываться n <= 6 && 3 <= n во все, что лучше всего подходит для целевого ЦП, чтобы вы ничего не получили, вводя числа 2 и 7, кроме потенциальной путаницы - и зачем брать указатель на вектор вместо ссылки?
Тед Люнгмо
Не используйте `const int number` в качестве функции аргумента
Антуан Морриер
1
@AntoineMorrier Почему?
переполнение кучи
@HeapOverflow Потому что это то же самое без использования const :).
Антуан Морье
@ AntoineMorrier Я не думаю, что это то же самое. Разве это не constговорит читателю, что функция не меняет значение? В этом конкретном случае с одной строкой это может быть понятно, но в целом это не так.
Переполнение кучи