Sortowanie wektora w porządku malejącym w dwóch zakresach

14

Powiedzmy, że mam wektor liczb całkowitych:

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

Następnie sortuję je w kolejności malejącej:

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

To powoduje:

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

Teraz chcę, aby cyfry 3, 4, 5 i 6 zostały przesunięte na koniec, i zachowaj dla nich malejącą kolejność (najlepiej bez konieczności używania sortpo raz drugi). To znaczy, czego chcę:

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

Jak zmodyfikować funkcję porównawczą, std::sortaby to osiągnąć?

Yury
źródło
4
return indices[first] > indices[second]Nie masz na myśli return first < second;?
acraig5075
2
Dla prostej opadającej rodzaju, std::greaterze <functional>mogą być stosowane w miejsce swojego lambda. Jeśli chodzi o twoje pytanie, najłatwiejszym sposobem może być napisanie bardziej szczegółowego komparatora, który zapewni, że twoje wartości porównają się tak, jak chcesz.
sweenish
4
@ acraig5075, w porządku malejącym powinno być return first > second.
ks1322
1
@ acraig5075 Wydaje mi się, że coś mi umknęło, czy też ludzie nie znają różnicy między wstępującym a malejącym ?
sweenish
3
Może szukasz std :: rotate ?
super

Odpowiedzi:

8

Twoja funkcja porównania jest nieprawidłowa, ponieważ wartości, które otrzymujesz jako firsti secondsą elementami std::vector. Dlatego nie ma potrzeby używania ich jako wskaźników. Musisz się zmienić

return indices[first] > indices[second];

do

return first > second;

Teraz, jeśli chodzi o problem, który próbujesz rozwiązać ...

Możesz pozostawić 3, 4, 5 i 6 w porównaniu z innymi elementami i nadal porównywać je ze sobą:

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

Próbny

Orzechówka
źródło
@NutCracker Tak, zgadzam się, że fajniej jest najpierw mieć najwyższe kryterium.
Przepełnienie stosu
5

Funkcje z biblioteki standardowych algorytmów , takich jak iota, sort, find, rotatei copyby ułatwić Ci życie. Twój przykład sprowadza się do:

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

Wynik:

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


@TedLyngmo w komentarzach podkreśla, że ​​można to / należy poprawić za pomocą:

auto a = std::lower_bound(indices.begin(), indices.end(), 6, std::greater<int>{});
auto b = a + 4;
acraig5075
źródło
auto b = a + 4;jest zły (jeśli chcesz zachować spójność z poprzednim fragmentem). Powinno tak być, auto b = a + 3;ponieważ w std::rotateużywanymb + 1
Biagio Festa
3

Rozwiązanie 1

Proste podejście z komparatorem nieliniowym .

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

Rozwiązanie 2

Używanie std::algorithms (partycji)!

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

Uwagi dotyczące wydajności

Może się wydawać, że drugie rozwiązanie jest wolniejsze z powodu obciążenia partycji. Prawdopodobnie tak nie jest, ze względu na pamięć podręczną i przewidywania braku gałęzi we współczesnych procesorach.

Reper

Biagio Festa
źródło
Każdy dobry kompilator powinien przekształcić się w n <= 6 && 3 <= n to, co działa najlepiej dla docelowego procesora, więc nic nie zyskujesz, wprowadzając liczby 2 i 7, ale potencjalne zamieszanie - i po co wybierać wskaźnik do wektora zamiast odniesienia?
Ted Lyngmo
Nie używaj `const int number` jako funkcji argumentu
Antoine Morrier
1
@AntoineMorrier Dlaczego?
Przepełnienie stosu
@HeapOverflow Ponieważ jest tak samo bez użycia const :).
Antoine Morrier
@AntoineMorrier Nie sądzę, że to to samo. Czy nie constmówi czytelnikowi, że funkcja nie zmienia wartości? W tym konkretnym przypadku jednej linijki może to być jasne, ale ogólnie nie jest.
Przepełnienie stosu