On "A New Collections Framework for the Standard Library"

[Andrei Alexandrescu via Digitalmars-d]

On 05/18/2017 11:18 AM, Jack Stouffer wrote:
> I just got around to watching Eduard Staniloiu's talk at DConf [1]
> about the collections library he was working on. One thing seemed
> odd, in that Eduard seems to be saying that the container and the
> range over the container's elements are one in the same and the
> range primitives are on the container itself.
>
> Is this accurate?

That is correct. The fundamental equation is:

Ranges + Optional Primitives = Containers

> If so, then this is completely different than the currently accepted
>  design of ranges and containers. Currently, a container allows the
> removal and insertion of elements, and to get a range of the elements
> you have to call a function or slice the container. This is how
> std.containers and Brain's EMSI container library. In this new
> library, what happens when I iterate the elements of one of these
> containers using foreach?

Iterating over a container using e.g. foreach won't consume the
container same as iterating over int[] won't consume the slice.

> Do the range primitives empty the container? How do I ask for a new,
> full range of my data in the collection to use in a range algorithm
> after I've already iterated over the elements?

There is no way to reclaim the original container. If you create a 
container, you get a range positioned to "see" the entire container. 
Once you popFront from that range, you lose all access to the first 
element in the container, unless you have a separate copy of the range. 
This is not new and not different from:

auto r = new int[10];
r.popFront;

What happens here is an array of 10 elements gets created. But you don't 
get a type "array of 10 integers". You get "a slice of integers, 
incidentally initialized to refer to the entire array of 10 integers 
that was just created". Next, you decide you don't care about the first 
element in the array. Once you call r.popFront, access to that element 
is lost forever.

As an aside, we briefly experimented with a type called "new T[]" which 
meant to refer to that initial array. I tried to redo a bunch of code 
with it. It was a failure - figuring out what's an array and what's a 
slice in the array was a continuous hassle offering no redeeming 
insight. It took me years to figure actually there's no need for 
containers and ranges - all you need is ranges.

> As Andrei originally laid out in this talk introducing ranges [2],
> ranges only shrink and never grow. Put another way, Output Ranges and
> Input Ranges are two separate things. Andrei states durning that talk
> (at 1:20:20)
>
> "Can ranges ever grow? ... No, never, because it would be
> fundamentally unsafe."
>
> I'm not sure what Andrei meant by this, but he believes that growing
>  ranges is also a bad idea.

Yes, you're not supposed to grow a range on its existing support without 
knowing whether you have room. That's a distinct matter. You can always 
grow a range by means of safe primitives that may duplicate it if 
needed, such as ~ and ~=.


Andrei