如何让multiset将新元素插入到相同值的首次出现位置之前？

嘿，这个需求其实很容易实现！默认的std::multiset确实会把新元素插到相同值的末尾，但要让新元素插在相同值首次出现的位置之前，有两种靠谱的方法，我给你详细说下：

默认的std::multiset用std::less<T>作为比较器，保持元素升序排列。我们可以利用lower_bound()方法找到第一个不小于目标值的元素迭代器，然后直接在这个位置插入新元素——因为lower_bound(val)返回的就是第一个等于val的元素（如果存在），或者第一个比val大的元素（如果不存在），插入到这个位置正好能让新元素成为相同值的第一个元素。

举个代码例子：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 2, 3};
    int insert_val = 2;

    // 找到第一个不小于insert_val的元素位置
    auto insert_pos = ms.lower_bound(insert_val);
    // 在该位置插入新元素
    ms.insert(insert_pos, insert_val);

    // 输出验证：1, 2(新), 2, 2, 3
    for (int num : ms) {
        std::cout << num << " ";
    }
    return 0;
}

运行这段代码，输出就是1 2 2 2 3，完全符合你的需求。而且这种方法完全保留了multiset原有的升序排序逻辑，只是手动指定了插入点，非常直观高效。

如果你希望容器本身就默认把新元素插到相同值的前面，可以自定义一个比较器，但要注意必须满足严格弱序的要求（否则容器行为是未定义的）。

这种方法需要给元素添加额外的标识（比如插入时间戳），通过比较标识来调整等价元素的顺序。举个例子：

#include <iostream>
#include <set>
#include <chrono>

struct Element {
    int value;
    long long timestamp;

    Element(int v) : value(v), timestamp(std::chrono::steady_clock::now().time_since_epoch().count()) {}
};

struct CompareElement {
    bool operator()(const Element& a, const Element& b) const {
        if (a.value != b.value) {
            return a.value < b.value; // 保持整体升序
        }
        // 值相等时，时间戳大的（新插入的元素）排在前面
        return a.timestamp > b.timestamp;
    }
};

int main() {
    std::multiset<Element, CompareElement> ms;
    ms.insert(Element(1));
    ms.insert(Element(2));
    ms.insert(Element(2));
    ms.insert(Element(3));

    // 插入新的2
    ms.insert(Element(2));

    // 输出验证：1, 2(新), 2, 2, 3
    for (const auto& elem : ms) {
        std::cout << elem.value << " ";
    }
    return 0;
}

不过这种方法需要修改元素类型，添加额外字段，对于简单类型（比如int）来说有点繁琐，所以更推荐第一种方法。

内容的提问来源于stack exchange，提问作者gst1502