2017-12-10 193 views
5

Mam wektor, który zawiera liczby całkowite dodatnie i -1. Mój problem polega na tym, że chcę posortować wektor, ale nie dotykać -1 elements, używając tylko std::sort (znam inne metody rozwiązania tego problemu).Jak sortować std :: vector, ale nie zmieniaj konkretnych elementów używając std :: sort?

Na przykład:

Wejście: [1, 150, 190, 170, 1, 1, 160, 180]

wyjściowe: [1, 150, 160, 170 , -1, -1, 180, 190]

to jest mój pomysł, aby go rozwiązać, ale nie zrobił praca:

sort(myVector.begin(), myVector.end(), [&](const int& a,const int& b)->bool { 
     if (a == -1 || b == -1) 
      return &a < &b; 
     return a < b; 
    }); 

Moje wyniki: [-1, 150, 170, 190, -1, -1, 160, 180]

Dane wyjściowe powinny wynosić: [-1, 150, 160, 170, -1, -1 , 180, 190]

Czy jest jakiś pomysł, aby rozwiązać go za pomocą std::sort?

+5

Nie sądzę, że jest to możliwe bezpośrednio. Funkcja 'std :: sort' działa na zakresie i nie ma sposobu, aby tymczasowo usunąć elementy i dodać je z powrotem na tych samych pozycjach później (oczywiście możesz to zrobić w wielu krokach, ale uważam, że to nie jest to, pytasz). Nie rozumiem też, co masz na myśli przez "dostosuj" 'std :: sort'. A także, jak działa 'std :: sort' jest zdefiniowana implementacja AFAIK, więc nie można wysnuć żadnych przypuszczeń na temat tego, w jaki sposób odbywa się porządkowanie. – Yashas

+0

@ Yashas przepraszam za mój angielski, masz rację, zredagowałem moje pytanie –

+2

Wyodrębnij lokalizacje '-1's do wektora, skasuj wszystkie' -1's, posortuj i potocz je z powrotem. – Ron

Odpowiedz

3

std::sort nie można tego zrobić. Sortuje szereg elementów zgodnie ze ścisłym, słabym porządkiem. Zdefiniowana przez Ciebie kolejność nie jest strict-weak. I nie ma sposobu, aby zdefiniować porządek, który jest ściśle-słaby, tak, że pewne wartości pozostają na swoich aktualnych pozycjach. I dlatego, jeśli spróbujesz użyć sort z takim porządkiem, otrzymasz niezdefiniowane zachowanie.

Musisz więc napisać własną funkcję sortowania. Możesz też usunąć wartości -1 (rejestrowanie pozycji), posortować listę, a następnie ponownie je wstawić.

0

Nie można tego zrobić, korzystając wyłącznie z std::sort. Alternatywą jest wyodrębnić lokalizacje -1 s, skasować wszystkie -1 s, sortować wektora i włóż w stosownych przypadkach:

#include <iostream> 
#include <vector> 
#include <algorithm> 

int main() { 
    std::vector<int> v{ -1, 150, 190, 170, -1, -1, 160, 180 }; 
    std::vector<int> vtemp; 
    auto it = v.begin(); 
    while ((it = std::find_if(it, v.end(), [](int x){ return x == -1; })) != v.end()) { 
     vtemp.push_back(std::distance(v.begin(), it)); 
     it++; 
    } 
    v.erase(std::remove(v.begin(), v.end(), -1), v.end()); 
    std::sort(v.begin(), v.end()); 
    for (auto el : vtemp){ 
     v.insert(v.begin() + el, -1); 
    } 
} 
+0

Istnieją oczywiste optymalizacje, aby poprawić szybkość (szczególnie przy ponownym wstawianiu -1), ale jest to rozsądne podejście. Możesz nawet zrobić to bez dodatkowej przestrzeni, przechowując pozycje -1 w samym wektorze, gdy je zgniatamy. – davidbak