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 sort
po 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::sort
aby to osiągnąć?
return indices[first] > indices[second]
Nie masz na myślireturn first < second;
?std::greater
ze<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.return first > second
.Odpowiedzi:
Twoja funkcja porównania jest nieprawidłowa, ponieważ wartości, które otrzymujesz jako
first
isecond
są elementamistd::vector
. Dlatego nie ma potrzeby używania ich jako wskaźników. Musisz się zmienićdo
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ą:
Próbny
źródło
Funkcje z biblioteki standardowych algorytmów , takich jak
iota
,sort
,find
,rotate
icopy
by ułatwić Ci życie. Twój przykład sprowadza się do:Wynik:
@TedLyngmo w komentarzach podkreśla, że można to / należy poprawić za pomocą:
ź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ż wstd::rotate
używanymb + 1
Rozwiązanie 1
Proste podejście z komparatorem nieliniowym .
Rozwiązanie 2
Używanie
std::algorithm
s (partycji)!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
źródło
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?const
mówi czytelnikowi, że funkcja nie zmienia wartości? W tym konkretnym przypadku jednej linijki może to być jasne, ale ogólnie nie jest.