c++ O(1)find/contains in std：：ranges：：views：：iota

uwopmtnx 于 2023-05-08 发布在其他

关注(0)|答案(2)|浏览(132)

我理解iota可能很复杂（例如无穷大），所以这在一般情况下不容易做到，但在某些情况下，它 * 应该 * 可能在O（1）中进行查找/包含操作。
举个例子

int main() {
    auto vals = views::iota(10'000'000'000, 100'000'000'000);
    return ranges::find(vals, 74'656'000'000) != vals.end();
}

运行“无限”（进行线性搜索），同时
这是O（1）的问题。
有没有一种方法可以用C++来实现这种通用的方式（即在其他视图上，find/contains需要线性时间，当它检测到iota时需要O（1）），或者我需要手动检测传递给我的函数的视图是有限iota视图，然后做>=front <=back检查？

c++

来源：https://stackoverflow.com/questions/76162376/o1-find-contains-in-stdrangesviewsiota

2条答案

按热度按时间

of1yzvn41#

iota_view始终是有序的，因此可以使用ranges::binary_search来避免无限线性搜索

int main() {
  auto vals = views::iota(10'000'000'000, 100'000'000'000);
  return ranges::binary_search(vals, 74'656'000'000);
}

Demo

赞(0）回复(0）举报 2023-05-08

h43kikqp2#

这在O（1）中是不可能的。
原因很简单，因为在C11中引入了<algorithm>，像find这样的算法只是假设一个带有迭代器的容器作为输入。因此，对于所有算法，输入都是通用的。
如果查看ranges/iota_view的成员函数，可以看到访问函数与std::vector中的类似。像find这样的算法只是使用这个接口，而不关心后面是什么，例如。它们表现为通用的而不是专门的。
C20附带的范围和视图在这里没有改变游戏规则。如果你需要性能提升，你需要自己实现一个特殊的函数。

int main() {
  auto vals = views::iota(10'000'000'000, 100'000'000'000);
  return *vals.begin() >= 74'656'000'000 && *vals.end() <= 74'656'000'000);
}

赞(0）回复(0）举报 2023-05-08

我来回答

c++ O(1)find/contains in std：：ranges：：views：：iota

2条答案

相关问题

热门标签

最新问答