gpt4 book ai didi

std::lower_bound 和 std::set::lower_bound 之间的 C++ 区别?

转载 作者:可可西里 更新时间:2023-11-01 17:44:59 34 4
gpt4 key购买 nike

最近,在处理 C++ 编程问题时,我遇到了一些有趣的事情。我的算法使用了一个非常大的集合,并且会在其上多次使用 std::lower_bound 。然而,在提交我的解决方案之后,与我在纸上所做的数学运算相反,以证明我的代码足够快,它最终变得太慢了。代码看起来像这样:

using namespace std;

set<int> s;
int x;

//code code code

set<int>::iterator it = lower_bound(s.begin(),s.end(),x);

然而,在从 friend 那里得到使用 set::lower_bound 的提示后,所讨论的算法比以前运行得更快,而且它符合我的数学计算。改变后的二分查找:

set<int>::iterator it = s.lower_bound(x);

我的问题是这两者有什么区别?为什么一个比另一个工作得快得多? lower_bound 不应该是复杂度为 O(log2(n)) 的二进制搜索函数吗?在我的代码中,它最终比这慢得多。

最佳答案

std::set 通常被实现为一个自平衡树,其中绑定(bind)了一些类似列表的结构。了解此结构后,std::set::lower_bound 将遍历了解树结构属性的。这其中的每一步都意味着遵循左或右子分支。

std::lower_bound 需要对数据运行类似于二进制搜索的操作。但是由于 std::set::iteratorbidirectional (not random access) ,这要慢得多,需要在被检查的元素之间做很多增量。因此,元素之间所做的工作更加激烈。在这种情况下,算法将检查 A 和 B 中间的元素,然后调整 A 或 B 之一,找到它们中间的元素,然后重复。

关于std::lower_bound 和 std::set::lower_bound 之间的 C++ 区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31821951/

34 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com