Date: Mon, 7 Sep 2020 16:25:44 -0400

As Andreas refines the idea, I'm starting to like it.

It seems like the primitive operation being described here is something

like... It takes a range and returns an iterator `mid` such that [first,

mid) has at least one element, but where the implementation is encouraged

to attempt to make [first, mid) and [mid, last) roughly equal in size, when

possible. This is the operation you want for binary-search, or any

divide-and-conquer algorithm (e.g. QuickSelect).

Notice that in C++20 Ranges, you probably want it to return not just the

iterator but a *pair of subranges*, because in Ranges, a subrange is

permitted to carry its size along with it, and we want to permit the

possibility of returning sized subranges here.

I observe that std::lower_bound(first, last, value) is currently

implemented in terms of std::next/std::advance, whereas it could actually

be faster (on subranges of a `std::set`, at least) if it used this

`divide_range` primitive at each step instead of trying to do the exact

math.

But, if you switch std::lower_bound to use `divide_range`, and if

`divide_range` for linked-list iterators is just std::next, then the

performance of std::lower_bound would get *worse *on subranges of

std::list, because you'd basically change a pointer-chasey binary search

into a pointer-chasey linear search.

I think the conclusion there is that `divide_range` for linked-list

iterators must *not *be std::next. For arbitrary iterators it should still

return `first + std::distance(first, last)/2`, even though that takes O(n)

to compute.

Anyway, I think there's something here. It feels very STL-ish to me. But

I suspect that it's "STL from a parallel universe" where C++20 never

happened and even C++98 made a couple of choices differently. I still

can't really see it standing a chance in today's Standard.

my $.02,

â€“Arthur

It seems like the primitive operation being described here is something

like... It takes a range and returns an iterator `mid` such that [first,

mid) has at least one element, but where the implementation is encouraged

to attempt to make [first, mid) and [mid, last) roughly equal in size, when

possible. This is the operation you want for binary-search, or any

divide-and-conquer algorithm (e.g. QuickSelect).

Notice that in C++20 Ranges, you probably want it to return not just the

iterator but a *pair of subranges*, because in Ranges, a subrange is

permitted to carry its size along with it, and we want to permit the

possibility of returning sized subranges here.

I observe that std::lower_bound(first, last, value) is currently

implemented in terms of std::next/std::advance, whereas it could actually

be faster (on subranges of a `std::set`, at least) if it used this

`divide_range` primitive at each step instead of trying to do the exact

math.

But, if you switch std::lower_bound to use `divide_range`, and if

`divide_range` for linked-list iterators is just std::next, then the

performance of std::lower_bound would get *worse *on subranges of

std::list, because you'd basically change a pointer-chasey binary search

into a pointer-chasey linear search.

I think the conclusion there is that `divide_range` for linked-list

iterators must *not *be std::next. For arbitrary iterators it should still

return `first + std::distance(first, last)/2`, even though that takes O(n)

to compute.

Anyway, I think there's something here. It feels very STL-ish to me. But

I suspect that it's "STL from a parallel universe" where C++20 never

happened and even C++98 made a couple of choices differently. I still

can't really see it standing a chance in today's Standard.

my $.02,

â€“Arthur

Received on 2020-09-07 15:29:41