Jak sortować std :: vector, ale nie zmieniaj konkretnych elementów używając std :: sort?

Question

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).

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?

Answer 1

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ć.

Answer 2

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