[...]
If they provide only the `LegacyForwardIterator` trait, only thing we
can do in constant time is:
std::set<int> foo;
... // fill it
auto begin = foo.begin();
auto end = foo.end();
auto middle = (begin != end) ? ++(begin) : begin;
No chance of processing the iterator range in an even remotely
balanced way without a linear scan.
FWIW, `std::for_each` is allowed to take O(n) time to do its job. If it spends 1/Kth of that time doing an O(n) traversal of the list to find its actual midpoint, then that's fine, AFAIK. There's nothing in the formal standard AFAIK that says it must use a dumb O(1) algorithm to partition the work. If you're seeing that dumb algorithm being used in implementations today, I think that's likely for software-engineering reasons, not standard-conformance reasons.
[...]
For reference, the following is about on-par with what the existing
STL implementations do:
// Generic implementation
template<typename Iter, ~~~>
std::pair<std::pair<Iter, Iter>, std::pair<Iter, Iter>>
divide(const Iter &begin, const Iter &end)
{
if constexpr (std::is_convertible_v<typename
std::iterator_traits<Iter>::iterator_category,
std::random_access_iterator_tag>)
{
// Ideal bisection
const Iter middle = end - std::distance(begin, end) / 2;
return { {begin, middle}, {begin, middle} };
Here and below, that should be {{begin, middle}, {middle, end}}, right?
Finally, I think you have at least two different problems here:
(1) Bisect (trisect,...) a range into contiguous subranges of the same iterator-type and exactly the right sizes. 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.
(2) Given a range, split it "quick and dirty" into subranges of possibly different iterator-type, and possibly not exactly the right sizes, but close enough to get speedup on parallel tasks.
You mention that unordered_set would probably be very good at #2 — but horrible at #1.
Another kind of data structure that might be good at #2 would be skiplists, whose iterators would know how to take "chunks" easily.
[...]
A heuristic alternative to "std::distance". The exact form we already
have does not have an efficient implementation for anything except
dense, compact allocations where it can be reduced to pointer
arithmetic.
Pedantry: No, std::distance uses iterator arithmetic, so it works efficiently on any random-access iterator type. std::distance of std::deque iterators is constant-time, for example, even though deque is not contiguous.
C++20 adds "contiguous iterator" as a refinement of "random-access iterator."
–Arthur