排序后如何保持向量中重复项的顺序？

Question

我有一个结构向量，每个结构都有一个数字 ID，我用它来对向量项进行排序。我希望对 ID 进行排序，但在排序后也按照它们在原始向量中的顺序显示。让我解释...

假设你有一个像这样的向量（忽略结构）：

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

排序后我希望向量看起来像这样：

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

请记住，这些项目实际上是结构。多个可以具有相同的 ID，但其他属性的值不同。现在，我认为结构在排序后没有可预测的顺序。有没有办法保证这种输出？我可以向结构添加另一个属性来指示其原始顺序，并以某种方式在排序算法中使用它吗？

Answer 1

您正在寻找的称为“稳定排序”，C++ 标准库将其提供为std::stable_sort；当项目比较相等时，它们的出现顺序与原始数据集中出现的顺序相同。Plainstd::sort不做这样的保证（因此可以使用稍微更有效的算法进行排序，不会保留相等元素的顺序），但std::stable_sort需要使用确实做出这种保证的算法。