Wie std :: vector sortieren, aber bestimmte Elemente nicht mit std :: sort ändern?

Question

Ich habe einen Vektor, der positive ganze Zahlen und -1 enthält. Mein Problem ist, ich möchte den Vektor sortieren, aber nicht berühren -1 elements durch nur std::sort (ich kenne andere Ansätze, um es zu lösen).

Zum Beispiel:

Input: [-1, 150, 190, 170, -1, -1, 160, 180]

Output: [-1, 150, 160, 170 , -1, -1, 180, 190]

Das ist meine Idee, es zu lösen, aber es hat nicht funktioniert:

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

Meine Ausgabe ist: [-1, 150, 170, 190, -1, -1, 160, 180]

Der Ausgang sollte sein: [-1, 150, 160, 170, -1, -1 , 180, 190]

Gibt es eine Idee, es zu lösen, indem Sie std::sort verwenden?

Answer 1

std::sort kann das nicht tun. Es sortiert eine Reihe von Elementen in Übereinstimmung mit einer strengen, schwachen Ordnung. Die Bestellung, die Sie definieren, ist nicht strict-weak. Und es gibt keine Möglichkeit, eine Ordnung zu definieren, die strikt-schwach ist, so dass bestimmte Werte in ihren aktuellen Positionen verbleiben. Und daher, wenn Sie versuchen, sort mit einer solchen Reihenfolge zu verwenden, erhalten Sie undefiniertes Verhalten.

Sie müssen also Ihre eigene Sortierfunktion schreiben. Oder Sie können die -1 entfernen (ihre Positionen aufzeichnen), die Liste sortieren und sie dann erneut einfügen.

Answer 2

Es kann nicht allein mit std::sort getan werden. Alternative ist, die Standorte der -1 s zu extrahieren, löschen Sie alle -1 s, sortieren den Vektor und setzen gegebenenfalls:

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