Kinds of containers

[Jonathan M Davis via Digitalmars-d]

On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
Alexandrescu wrote:
> I'm finally getting the cycles to get to thinking about Design 
> by Introspection containers. First off, there are several 
> general categories of containers. I think D should support all 
> properly. One question is which we go for in the standard 
> library.
>
> 1. Functional containers.

I fully expect that these have their place, but I honestly have 
no idea what they would be. When I've used functional languages, 
I've only ever found these attributes to be a royal pain to deal 
with, not a benefit. From what I've seen, containers are the sort 
of thing that almost always always need to be mutable to be of 
any real benefit. Upon occasion, constructing a container up 
front and then never tweaking it after that is useful, but that's 
pretty rare from what I've seen.

The only cases that I can think of where this could be really 
beneficial would be something like strings, and we're using 
arrays for those currently (though they are arguably functional 
containers given that they have immutable elements).

> 2. Reference containers.

These are where it's at IMHO. 99.999999% this is what makes sense.

> 3. Eager value containers.

_Maybe_ this makes sense for specific container types, but in 
general, it's a horrible idea IMHO. Almost all containers involve 
allocating something on the heap internally, so the fact that 
they're treated as values doesn't avoid heap allocations, and 
reference-counting reference containers solves the problem of the 
containers living past the end of the lifetime of whatever owns 
them. And having value type containers is incredibly error-prone 
- both from an efficiency standpoint and correctness standpoint. 
It's _way_ too easy to copy them when you don't mean to, and 
simple stuff like

vector<T> foo() {...}

for(auto iter = foo().begin(); iter != foo().end(); ++iter) {...}

ends up doing nasty things, because you have iterators (or 
ranges) to a container that's already been destroyed.

Honestly, unless you're counting something like a point or tuple 
as a container, I really don't see any value in these sort of 
containers. They're just too error-prone without adding any real 
value.

> 4. Copy-on-write containers.

This could be interesting for some applications (probably more so 
than functional containers), but I would expect that it would 
only really be useful for very specific containers. I certainly 
wouldn't want to end up with a copy of my vector or list because 
I added a value to it. COW for strings makes a lot of sense, 
because they don't tend to get mutated much (which is also why 
string is immutable(char)[]). But since we're already using 
arrays for strings, a COW string would then be for special cases 
only.

Overall, I think that we should focus on getting good reference 
containers while leaving the door open for cool stuff from the 
other container types. It's the reference containers that most 
programs are going to need, whereas I expect that the others are 
more likely to be nice-to-haves for a minority of applications 
and outright useless for the majority.

- Jonathan M Davis