C++ 中 std::set::lower_bound 和 std::lower_bound 的区别

在本文中，我们将讨论 C++ 中 std::lower_bound 和 std::set::lower_bound 函数之间的区别。但在讨论它们的不同之处之前，我们必须了解 std::lower_bound 和 std::set::lower_bound 函数。

C++ 中的 std::lower_bound 是什么？

std::lower_bound 函数使用二分查找在**已排序范围**中查找给定值可插入的第一个位置，而不会破坏排序。输出是一个迭代器，它显示范围 [first, last] 中第一个大于或等于给定值的值。换句话说，函数**std::lower_bound** 确定已排序范围中大于或等于输入值的最小元素的索引。此返回迭代器之前的所有元素必须小于该值。**std::lower_bound** 之后的元素可能大于或等于该值，也可能不大于或等于该值。它使得 std::lower_bound 可以高效地进行查找和插入到存储数据中。

C++ 中的 std::set::lower_bound 是什么？

std::set 的 lower_bound() 方法执行二分查找，以查找给定键的插入位置，以保持**Set 的排序**。它返回一个迭代器，指向第一个大于或等于所搜索键的条目。

如果 Set 中不存在该键，lower_bound 返回一个迭代器，指向在所搜索键之后排序的下一个最重要元素。它发现该键的**“下边界”**在有序 Set 中。它允许高效查找，即使是 Set 中不存在的键也是如此。

如果所搜索的键大于 Set 中最大的元素，**Lower_bound** 将提供一个指向 set 容器末尾的迭代器。

std::lower_bound 和 set::lower_bound 有什么区别？

下表以表格形式比较了 std::lower_bound 和 std::set::lower_bound。

而 std::set::lower_bound 是一个集合成员函数，它利用其排序专门用于集合中的查找/插入。但两者都以 O(log n) 时间返回值的**“下边界”**。

示例

让我们通过一个程序来演示 C++ 中 std::lower_bound() 的用法。

输出

Vector contains: 1 2 4 4 5 7 8 10 
First element not less than 6 is at position: 5

在此示例中，目标值为 35，并且使用 std::lower_bound() 查找 35 可插入向量中以保持排序顺序的位置。输出表明元素 35 可以插入到位置 3 以保持排序顺序。

说明

• 程序创建一个已排序的整数向量。
• 它定义了一个要搜索的目标值（在本例中，target = 6）。
• 它使用 std::lower_bound() 查找指向第一个不小于目标的元素的迭代器。
• 之后，程序输出原始向量和第一个不小于目标的元素的位置。

示例

让我们通过一个程序来演示 C++ 中 std::set::lower_bound() 的用法。

输出

Set contains: 1 2 4 5 7 8 10 
First element not less than 6 is: 7

在此示例中，使用 std::set::lower_bound() 函数查看 35 可以插入到 Set 的哪个位置以保持排序顺序。输出表明元素 35 可以插入到位置 4 以保持排序顺序。如果找不到该组件，它将返回一个迭代器，指向第一个大于目标的元素。

说明

• 程序创建一个整数集合。集合默认总是排序的。
• 它定义了一个要搜索的目标值（在本例中，target = 6）。
• 它使用 std::set::lower_bound() 查找指向第一个不小于目标的元素的迭代器。
• 之后，程序输出原始集合和第一个不小于目标的元素。

结论

std::lower_bound 是一种通用算法，它执行二分查找以在任何排序容器中查找键的插入点，而 std::set::lower_bound 是一个 std::set 成员函数，它利用集合的排序以对数时间高效地定位键的位置或下一个最重要的元素。前者普遍适用于排序范围；后者针对 std::set 容器上的操作进行了优化。