`std::iota_view` 当给定不同类型的值和绑定时很慢？

Question

我正在解决一个编程任务，我们想要找到一个不满足给定（单调）属性的最小整数。这可以通过二分查找来实现。使用 C++20，我决定将

std::partition_point

与

std::iota_view

一起使用。我混合了几种类型，并且由于某种原因我的代码非常慢。我的代码（简化）：

#include <ranges>
#include <iostream>
#include <algorithm>
#include <climits>
bool monotone(int n)
{
    return n <= 1000000000;
}

long long MAX = INT_MAX; //weird?
int main()
{
    using namespace std;
    cout << *ranges::partition_point(ranges::iota_view(1,MAX), monotone) << endl;
}

仔细观察，奇怪的是

MAX

是

long long

类型，而它可能是 int。在我的机器上运行它会产生大约 12 秒的运行时间，这太多了，它应该是

MAX

的对数。我注意到，如果我将

ranges::iota_view(1,MAX)

更改为

ranges::iota_view(1ll, MAX)

或

ranges::iota_view(1,(int)MAX)

，代码会突然开始按预期快速“工作”（在几毫秒内完成）。

在这两种情况下，我测量到函数

monotone

被准确调用了

31

次（在本例中），因此关于谓词调用次数的时间复杂度是可以的。

有人可以向我解释一下幕后发生了什么以及为什么混合

iota_view

中的类型会产生如此缓慢的代码吗？

编辑：问题似乎在于在

ranges::distance

内部调用

ranges::partition_point

，它专门用于在线性时间内计算

std::iota_view<int,long long>::_Iterator

和

std::iota_view<int,long long>::_Sentinel

的距离的变体。相反，当给

iota_view

相同的两种类型（两个

int

或两个

long long

）时，专业化选择计算

std::iota_view<int,int>::_Iterator

和

std::iota_view<int,int>::_Iterator

之间的距离，该距离落入在其中计算的专业化中O(1) 只是两个整数的差。

但是，为什么会出现这种专门化对我来说仍然是个谜，并且希望详细解释为什么它会这样。

Answer 1

TL；博士：

• ranges::sized_sentinel_for<int, long long>

  是

  false

  ，因此

• ranges::sized_sentinel_for<decltype(v.begin()), decltype(v.end())>

  是

  false

  ，因此

• ranges::partition_point

  无法知道范围大小，必须逐步增加迭代器，几乎就像不是随机访问一样。

---

我检查的第一件事是当参数类型不同时，

ranges::iota_view<int, long>

是否仍然是

ranges::random_access_range

。是的，确实如此，但事实证明这在当时并没有多大意义。

关于

random_access_range

的有趣之处在于，它只检查

begin()

迭代器，而不检查

end()

，因为后者首先不必是迭代器，而只是一个 sentinel。

（哨兵是一种与迭代器

==

相当的类型，并且可以选择重载

-

，使其成为大小的哨兵。）

要使

iota_view<A,B>::end()

成为 iota_view<A,B>::begin() 的

大小哨兵

，

B

需要成为

A

的大小哨兵。结果

long long

不是

int

的大小哨兵，因为即使它们是可减的，减法的结果也不是

int

（而是

long long

），并且它可以隐式转换为

int

是还不够。

因此，如果

end()

不是大小标记，则 range::partition_point 无法计算范围大小，并且必须逐步移动

begin()

迭代器，就好像它是非随机访问迭代器一样。但正如您所注意到的，它仍然限制自己进行 log(N) 比较。