On Sun, Sep 6, 2020 at 11:46 AM Andreas Ringlstetter via Std-Proposals
<std-proposals_at_[hidden]> wrote:
>
> Arthur O'Dwyer:
> > Finally, I think you have at least two different problems here:
> > (1) [...] I think range-v3 would be capable of this task; something
> > with std::ranges::size and then repeatedly views::slice. Someone
> > better at Ranges than me might try it.
>
> There is no `std::ranges::size` for range types which couldn't yield it
> in constant time, and `views::slice` incurs a full iteration over the
> skipped iterators if not random-access.
>
> You are correct that this is the ideal solution if he input range is
> random-access.

The important thing that ranges::size brings to the table is the
disconnect between random-access ranges and O(1)-size ranges. While
`random_access_range` makes `sized_range` all but guaranteed, the
reverse is not the case.

`std::list` is only a `bidirectional_range`. And if you build a range
for its begin/end iterators, the result will not be a `sized_range`.
But `std::list` itself carries O(1) size information through the
member `size` function, so it satisfies `sized_range`. So if you pass
`std::list` directly to a range algorithm, then it has access to that
information should it be useful.

Given O(1) size information, you could apportion threads by having
each thread advance their iterator forward by the number of threads
involved. And of course their initial iterator has to be offset
appropriately, and they have to check for the end iterator when
incrementing their own. So while `slice` is probably not the best
option, having O(1) size for ranges that provide it may be enough to
build a good solution even for non-random access ranges.

If size information is insufficient for handling the problem, then
perhaps a mechanism like `ranges::size` should be considered for
carrying the extra information you need to partition such a range
efficiently.