Requirements for Slicing Ranges

[Jonathan M Davis]

On Sunday, September 1, 2024 9:31:23 PM MDT Richard (Rikki) Andrew Cattermole 
via Digitalmars-d wrote:
> On 02/09/2024 2:47 PM, Jonathan M Davis wrote:
> > Can anyone see something that I'm missing here?
>
> Indexing and range intervals are indeed distinct things.
>
> An interval does not have to evaluate to a specific bit of data, but an
> index does.
>
> They can also use non-integral keys.
>
> Typically both ``size_t`` and ``ptrdiff_t`` will have defined
> sequentiality, but they may not in the case of a map. Whereby an index
> works but not an interval.
>
> So the question is, how many assumptions surrounding sequentiality is
> being made, along with the key type?

The range API uses size_t for indices, and it is required that the indices
be sequential. range[3] gives you the 4th element and range[3 .. 9] gives
you a 6 element range starting at the 4th element.

Containers may do other things with keys (particularly containers like hash
tables and sorted maps), but the range API treats indices the same way that
arrays do. Doing anything else would complicate things considerably, and if
anything, the range API is arguably already too complex.

In essence, the range API provides an abstraction based on arrays, with
random-access ranges providing the full capabilities of a dynamic array /
slice aside from the capabilities related to increasing their size or doing
any kind allocations. Each lower category of range then loses capabilities
as it moves further away from being an array, with basic input ranges just
providing a way to iterate through the elements once and nothing else. Or,
if you want to view the situation in reverse, we start with a basic input
range being only able to iterate through a sequential list of elements once,
and each category of range builds up towards the capabilities of an array.

As such, the situation with keys is simple in that there are no keys in the
general sense. We're just dealing with indices, and an index needs to mean
the same thing that it would with an array. It's simply a question of where
in the hierarchy we put each capability.

Indexing requires random-access ranges. Slicing at present does not, but as
far as I can tell, from a technical persective, with regards to a sequential
data structure such as a range, it is not possible to implement indexing
without also being able to implement slicing, and I don't see how it would
be possible to implement slicing but not be possible to implement indexing.

Non-sequential data structures really don't have anything to do with ranges
aside from cases where such a data structure provides a sequential view into
its data via a range.

- Jonathan M Davis