How can I keep the order of duplicates in a vector after sorting it?

Question

I have a vector of structs, each struct has a numerical ID that I am using to sort the vector items by. I want the IDs to be sorted, but to also appear in the order they did in the original vector after sorting. Let me explain...

Suppose you have a vector like this (ignoring the structs):

vector<int> items = {
    1,
    2,
    5, // First 5
    8,
    9,
    6,
    5, // Second 5
    4,
    7,
    3,
    5, // Third 5
    10
};

After sorting I want the vector to look like this:

vector<int> items = {
    1,
    2,
    3,
    4,
    5, // First 5
    5, // Second 5
    5, // Third 5
    6,
    7,
    8,
    9,
    10
};

Remember, these items would actually be structs. Multiple can have the same ID, but different values for the other properties. Right now, I don't think the structs have a predictable order after sorting. Is there a way to ensure this kind output? Could I add another property to the structs indicating their original order and somehow use that in the sorting algorithm perhaps?

Answer 1

What you're looking for is called a "stable sort", and the C++ standard library provides it as std::stable_sort; when items compare equal, they appear in the same order they appeared in the original data set. Plain std::sort makes no such guarantees (and can therefore use slightly more efficient algorithms for the sorting that won't preserve order for equal elements), but std::stable_sort requires the use of algorithms that do make that guarantee.