How to sort std :: vector but not change specific elements with std :: sort?

Question

I have a vector containing positive integers and -1. My problem is that I want to sort the vector, but I don't touch -1 elements , just using std::sort (I know other approaches to solving it).

For instance:

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

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

It is my idea to solve it, but it did not work:

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

My way out: [-1, 150, 170, 190, -1, -1, 160, 180]

The output should be: [-1, 150, 160, 170, -1, -1, 180, 190]

Is there any idea to solve this problem with std::sort ?

Answer 1

std::sort cannot do this. It sorts a number of elements according to a strict, weak order. You define non strict-weak . And there is no way to determine a strict-weak order, so that certain values ​​remain in their current positions. And therefore, if you try to use sort with this ordering, you will get undefined behavior.

So you have to write your own sort function. Or you can delete -1 (write down their positions), sort the list, and then reinsert them.

Answer 2

This cannot be done using std :: sort . An alternative is to extract -1 s locations, delete all -1 s, sort the vector, and reinstall if necessary:

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