C++ STL 中的 multimap upper_bound() 函数

在 C++ 的 STL（Standard Template Library）中，multimap 是一个关联式容器，它允许我们在其中存储一对多（<key, value>）的映射关系。其中，upper_bound() 函数是用于查找大于给定关键字的第一个位置的迭代器函数。使用这个函数，我们可以轻松地找到 multimap 中的下一个元素。

upper_bound() 函数的定义

upper_bound() 函数定义如下：

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

其中，k 是一个关键字，在 multimap 中按照 key 的值进行排序，函数返回一个指向第一个大于该关键字的迭代器。

示例代码

下面是一段使用 upper_bound() 函数的示例代码，在这个示例中，我们将创建一个 multimap 对象，然后向其中添加一些元素，并使用 upper_bound() 函数查找一个大于给定关键字的元素。具体如下：

#include <iostream>
#include <map>

int main() {
  std::multimap<char, int> mymultimap;

  mymultimap.insert(std::make_pair('a', 10));
  mymultimap.insert(std::make_pair('b', 20));
  mymultimap.insert(std::make_pair('c', 30));
  mymultimap.insert(std::make_pair('d', 40));
  mymultimap.insert(std::make_pair('e', 50));

  auto it = mymultimap.upper_bound('b');
  std::cout << "The first element greater than 'b' is "
            << it->first << " --> " << it->second << '\n';

  return 0;
}

编译并运行程序，输出如下：

The first element greater than 'b' is c --> 30

upper_bound() 函数的原理

upper_bound() 函数用于查找大于给定关键字的第一个位置的迭代器。对于一个给定的关键字 k，upper_bound() 函数返回的是一个迭代器，该迭代器指向一个关键字严格大于 k 的元素的位置。如果 multimap 中不存在一个关键字大于 k，则函数返回指向 multimap 中最后一个元素的迭代器。

upper_bound() 函数的特点是可以快速查找 multimap 中大于给定 key 值的元素。因为 multimap 内部实现是红黑树，查找的过程实际上就是对红黑树进行搜索和遍历。但是，由于 multimap 允许存在多个相同的 key 值，因此 upper_bound() 函数返回的迭代器指向的是严格大于给定 key 值的第一个元素位置，而不是等于该 key 值的第一个位置。

结论

通过本文，我们了解了 C++ STL 中的 multimap upper_bound() 函数的用法和原理。upper_bound() 函数的功能可以让我们轻松地寻找 multimap 中的下一个元素，并且由于 upper_bound() 函数是红黑树实现的，能够快速地进行查找与遍历操作。通过这个函数，我们可以更方便地操作 multimap 这一关联式容器。