std::multiset 的 lower_bound 是一个非常常用的成员函数，用于在有序多重集合中查找第一个不小于（≥）给定值的元素。由于 multiset 允许重复元素且自动保持升序（默认），lower_bound 能高效地定位插入点或查找范围。

---

一、基本语法

#include <set>
std::multiset<T> ms;

// 成员函数版本（推荐）
auto it = ms.lower_bound(value);

// 全局函数版本（不推荐用于 multiset）
auto it = std::lower_bound(ms.begin(), ms.end(), value); // O(n)！

✅ 强烈建议使用成员函数 ms.lower_bound(value)
因为 multiset 是基于红黑树实现的，成员函数版本时间复杂度为 O(log n)，而全局 std::lower_bound 对非随机访问迭代器（如 set/multiset 的迭代器）是 O(n)！

---

二、功能说明

• lower_bound(x) 返回指向 第一个 ≥ x 的元素 的迭代器。
• 如果所有元素都 < x，则返回 ms.end()。
• 在 multiset 中，可能有多个等于 x 的元素，lower_bound(x) 指向第一个等于 x 的位置。

---

三、示例代码

#include <iostream>
#include <set>

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

    int x = 2;
    auto it = ms.lower_bound(x);

    if (it != ms.end()) {
        std::cout << "lower_bound(" << x << ") = " << *it << std::endl; // 输出 2
    }

    // 查找所有等于 2 的元素
    auto it_low = ms.lower_bound(2);
    auto it_high = ms.upper_bound(2); // 第一个 >2 的位置

    std::cout << "所有 2: ";
    for (auto i = it_low; i != it_high; ++i) {
        std::cout << *i << " "; // 输出 2 2 2
    }
    std::cout << std::endl;

    // 插入前查找插入位置（保持有序）
    auto pos = ms.lower_bound(3);
    // multiset 会自动插入到正确位置，通常不需要手动指定
    ms.insert(3); // 自动插入

    return 0;
}

---

四、常见用途

1. 判断元素是否存在（至少一个）

if (ms.lower_bound(x) != ms.end() && *(ms.lower_bound(x)) == x) {
    // x 存在
}

但更推荐用 ms.count(x) > 0（虽然 O(log n + count)，但简洁）或结合 upper_bound。

2. 获取所有等于 x 的元素范围

auto [low, high] = std::equal_range(ms.begin(), ms.end(), x); // 但这是 O(n)
// 更高效的是：
auto low = ms.lower_bound(x);
auto high = ms.upper_bound(x);

3. 找到第一个 ≥ x 的元素（用于贪心、调度等）

// 例如：找第一个可用资源 ≥ 需求
auto it = resources.lower_bound(demand);
if (it != resources.end()) {
    use(*it);
    resources.erase(it);
}

---

五、注意事项

项目	说明
时间复杂度	O(log n)（成员函数）
返回类型	std::multiset<T>::iterator（常量版本返回 const_iterator）
与 set 区别	set 中每个元素唯一，multiset 可重复，但 lower_bound 行为一致
自定义比较器	若 multiset 使用自定义比较（如 greater<int>），则 lower_bound 按该顺序工作

自定义比较器示例：

struct cmp {
    bool operator()(int a, int b) const { return a > b; } // 降序
};
std::multiset<int, cmp> ms = {5, 4, 3, 2, 2, 1};

auto it = ms.lower_bound(2); // 返回第一个 ≤ 2 的元素（因为是降序）
// 实际上，在降序 multiset 中，lower_bound(x) 是第一个 ≤ x 的元素

---

六、总结

• ✅ 用 ms.lower_bound(x)，不要用 std::lower_bound(ms.begin(), ms.end(), x)。
• 它返回第一个 ≥ x 的元素（按 multiset 的排序规则）。
• 常用于范围查询、存在性检查、贪心算法中的“最小满足条件”选择。

如有具体使用场景（如结合 erase、处理自定义结构体等），欢迎补充！