基于函数而不是集合的二分搜索或迭代器?

Question

作为一个简单的例子，假设我想通过使用二叉搜索找到N的平方根。但我不想自己实现二进制搜索，而是使用std::lower_bound或类似方法。我可以写类似的东西吗

int square(int x) {
return x * x;
}
int square_root(int N) {
// Assume I know the results is between 0 and 10000.
return std::lower_bound(0, 10000, square, N);
}

有没有这样的函数，而不是从集合的迭代器中获取值，而是从回调函数中获取值？

或者，有没有办法基于函数而不是集合创建迭代器，以便我可以执行以下操作：

return std::lower_bound(func_it(0, square), func_it(10000, square), N);

我知道我可以自己编写这个函数或迭代器。我问标准库中是否存在这样的功能，因为它似乎很有用，但我找不到它。

Answer 1

C++20 的标准库包括范围，这基本上是为这种东西而制作的。您需要一个transform_view：

int square(int x) { return x * x; }
int sqrt(int x) {
auto space = std::views::iota(0, x + 1) | std::views::transform(square);
return std::lower_bound(space.begin(), space.end(), x) - space.begin();
}
int main() {
std::cout << "sqrt(123): " << sqrt(123) << "n"; // gives 12: (12-1)^2 < 123 <= 12^2
}

这将创建序列0, 1, 2, ..., x(iota(0, x + 1)(，对每个元素(| transform(square)(进行平方(读作|"管道"，一个sh(，搜索第一个大于或等于radicand的元素，并给出其索引/原始值(通过将其位置与序列的begin差分(。对于非负积分x，0 <= sqrt(x) <= x，所以iota(0, x + 1)是一个合适的源。在square中插入std::cerr << x << "n";可确认std::lower_bound不会回退到线性搜索。

戈博尔特