On 07.09.2020 08:17, Jason McKesson wrote:
> OK, but... what do you expect from an algorithm that is designed to be
> *generic*? That's the whole conceit behind the
> container/iterator/algorithm paradigm. That you want algorithms to be
> written against sequences without detailed knowledge of the mechanism
> by which those containers hold sequences of objects. The medium of
> interchange between algorithms and containers are iterators, a generic
> interface for moving through a sequence.
>
> If the only way to avoid these problems is to have detailed knowledge
> of the specific and unique implementation details of how an iterator
> works, then what you're writing is no longer a generic algorithm; it's
> just a member function of `std::map/set` or whatever. And it's
> probably not worth it to require such overloads of standard library
> algorithms.
>
> It seems to me that what you want is a fundamentally different take on
> "iterators" as a concept. Just trying to do a patch-fixup on certain
> containers' iterators isn't an effective solution.

To me the algorithms in STL are only templates patching together the
building blocks provided by the various iterator types, solving a
specific problem by an algorithm of implementations choice. However,
that implies that the interface for working with the iterators must be a
good fit for limitations in both common container implementation
details, and common algorithm implementation details.

Treating iterators without random-access as a purely deterministic,
sequential concept completely ignores the fact that divide-and-conquer
is an essential building block for many algorithms, and precise
random-access is an expensive operation for many container types.

In the primary example I used, as a building block for efficient
parallelization.

As it stands, this already showed in earlier versions of the C++
standard in ambiguities such as having e.g. both std::lower_bound and
std::set::lower_bound in the standard. Requiring both as a direct
consequence of the logarithmic run time not being achievable with the
non-random-access interface of the iterator of an std::set.

At the same time, std::set did not gain the necessary public interface
to plug in other divide-and-conquer style algorithms, despite the
standard tying down the time complexity requirements in such way, that
all possible implementations would had been suitable.

In these cases it's not required to have detailed knowledge about the
implementation details in order to *use* a division scheme recommended
by the iterator/container, but it is necessary to query that from the
iterator rather than enforcing a generic, static partitioning scheme (or
even linear scan) which is likely a bad fit.

Hence the proposal to add the interface for range division to the
standard, in a way which works at least on-par with any existing STL
implementation, without changing the integration side interface in any
form, and providing backward compatibility with any container / iterator
not fully integrated yet.

There still only remains (roughly) one implementation of each algorithm,
but the "divide" step is extracted to where it belongs to (tied to
iterator by either overload resolution or member), rather than being an
in-lined, hard coded choice between pure forward and full random-access
iterator.