O(1) find/contains in std::ranges::views::iota

Question

I understand that iota can be complex(e.g. infinite), so this can not be done easily in general case, but in some cases it should be possible to do find/contains operation in O(1).

For example

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

runs "infinitely" (doing linear search) while

obviously check can be done in O(1).

Is there a way to do this generic way with C++(i.e. find/contains that on other views takes linear time, and when it detects iota it takes O(1)), or I need to manually detect when view passed to my function is finite iota view and do the >=front <=back check?

Leighton

find would still need to do a linear operation, but contains could be specialised – Raul

I would remove find from the question and just leave contains, for the reason explained in Caleth's comment. – Polis

You're violating your own API when you try to break into the implementation of a range argument. Either have a different API with different parameters or use the range as intended. – Northrop

It's pretty hard to figure out how to customize algorithms in light already existing member functions which mean different things. Python gets away with this in a pretty interesting way: a dict is a range of keys, so having key in d work is consistent - but in C++ our hashtables are ranges of pairs... – Australian

@Australian I see your point, but do you know then why iota view does not have .contains() (constrained by something unreadable that basically guarantees value is computable in O(1)). That seems relatively ok solution. Then I could use that... – Leighton

@Polis I see your point, but not sure most C++ learners are helped by this change. find is a much older function name in C++ than contains and for example map find is not linear. Again I could be wrong, I am just guessing what ppl googling might use for search – Leighton

Answer 1

iota_view is always ordered, so you can use ranges::binary_search to avoid infinite linear 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

Kaiser

upvote since it is an improvement, but it is still O(log n), no? – Leighton

also this is getting into "intentionally breaking it" but I presume you could make a iota where std::less (default used by binary search) is giving wrong result since "incremeting" value that is done by iota actually decreses it. – Leighton

Answer 2

No it cannot be done in O(1).

The reason is simple, since the introduction of <algorithm> in C++11 the algorithms like find just assume a container with iterators as input. So for all algorithms the input is generic.

If you look at member functions of ranges/iota_view, you can see that the access functions are similar to those in std::vector. And algorithms like find simply use this interface without caring what is behind, e.g. they behave generic and not specialized.

Ranges and Views which came with C++20 are no game changers here. If you need performance boosts you need to implement a spezializated functions yourself.

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);
}

Condor

Answer 3

It can be done for O(1) with a bit field if you have extra at least 11 GB of RAM. Set the required bits number - 10'000'000'000 in a bit field, where number is between 10'000'000'000 and 100'000'000'000. Then check if the bit 74'656'000'000 - 10'000'000'000 is set. This is O(1).

Badinage