C++ multimap::upper_bound() 函数

C++ 的 std::multimap::upper_bound() 函数用于返回一个迭代器，该迭代器指向大于指定键的第一个元素。它对于查找可以在不破坏排序顺序的情况下插入新元素的位置非常有用。与 map 不同，multimap 允许重复键，因此 upper_bound() 提供对大于键的第一个元素的访问，而不是精确匹配。此函数的时间复杂度是对数级的，即 O(log n)。

语法

以下是 std::multimap::upper_bound() 函数的语法。

iterator upper_bound (const key_type& k);
const_iterator upper_bound (const key_type& k) const;

参数

• k − 表示要搜索的键。

返回值

此函数返回容器中第一个元素的迭代器。

示例

让我们看下面的例子，我们将演示 upper_bound() 函数的使用。

#include <iostream>
#include <map>
int main()
{
    std::multimap<int, std::string> a = {
        {1, "AB"}, {2, "BC"}, {3, "CD"}, {4, "DE"}
    };
    auto x = a.upper_bound(2);
    if (x != a.end()) {
        std::cout << "First element greater than key is : ";
        std::cout << x->first << " --> " << x->second << std::endl;
    } else {
        std::cout << "No elements is greater than key." << std::endl;
    }
    return 0;
}

输出

以下是上述代码的输出：

First element greater than key is : 3 --> CD

示例

考虑另一种情况，我们将循环中使用 upper_bound() 函数。

#include <iostream>
#include <map>
int main()
{
    std::multimap<int, std::string> a = {
        {1, "TP"}, {2, "Hi"}, {3, "Hello"}, {3, "Vanakam"}
    };
    for (auto x = a.upper_bound(1); x != a.end(); ++x) {
        std::cout << x->first << " --> " << x->second << std::endl;
    }
    return 0;
}

输出

上述代码的输出如下：

2 --> Hi
3 --> Hello
3 --> Vanakam

示例

在下面的示例中，我们将结合使用 upper_bound() 函数和 equal_range() 函数。

#include <iostream>
#include <map>
int main()
{
    std::multimap<int, std::string> a = {
        {1, "TP"}, {1, "TutorialsPoint"}, {2, "Tutorix"}, {3, "Welcome"}
    };
    auto x = a.equal_range(1);
    auto y = a.upper_bound(1);
    std::cout << "Elements with given key : " << std::endl;
    for (auto z = x.first; z != x.second; ++z) {
        std::cout << z->first << " --> " << z->second << std::endl;
    }
    if (y != a.end()) {
        std::cout << "First element greater than key is :  ";
        std::cout << y->first << " --> " << y->second << std::endl;
    } else {
        std::cout << "No elements is greater than key." << std::endl;
    }
    return 0;
}

输出

如果我们运行上述代码，它将生成以下输出：

Elements with given key : 
1 --> TP
1 --> TutorialsPoint
First element greater than key is :  2 --> Tutorix