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

Question

I have a vector which contains positive integers and -1. My problem is I want to sort the vector but dont touch -1 elements by just using std::sort(I know other approaches to solve it).

For example:

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

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

This is my idea to solve it but it didnt 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 output is: [-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 it by using std::sort ?

Answer 1

std::sort cannot do that. It sorts a range of elements in accord with a strict, weak ordering. The ordering you define is not strict-weak. And there's no way to define an ordering that is strict-weak, such that certain values remain in their current positions. And therefore, if you attempt to use sort with such an ordering, you get undefined behavior.

So you're going to have to write your own sorting function. Or you can remove the -1's (recording their positions), sort the list, then reinsert them.