Container hierarchy vs. container types

[Jerry Quinn]

Andrei Alexandrescu Wrote:

> I decided to let no assumption unchallenged and got back to the 
> question: do we really need a container _hierarchy_? How much joy and 
> usefulness do people derive from dynamically changing an array with a 
> list under the same interface? Or a rb-tree vs. a binary tree vs. a 
> left-leaning binary tree?

> As far as I can tell such changes of containers are a design-time 
> decision, and extremely rarely (never as far as I remember) a runtime 
> decision to hide behind a binary interface. I'm starting to think that 
> it's quite the other way around, and a Sapir-Whorf kind of thing: The 
> fact that Java lacks symbol aliasing capability conditions the thinking 
> that a hierarchy is the right thing to do, whereas the true solution is 
> to design a flat federation of container types with name- and 
> semantics-compatible primitives, to then use them directly or via 
> design-time aliases.

I've rarely found it helpful that an ArrayList is a List, or that HashMap is a
Map.  If an API I'm passing to takes the base class, it could easily have
been done as a template. And dynamic switching hasn't ever been useful
to me. As long as the API is the same, recompiling will work and the
containers will continue to behave well.

If dynamic switching is really necessary for an application, it can be done by wrapping
the container with a class hierarchy as needed.

> Obviously I might be wrong in any number of ways. Switching containers 
> dynamically might be very useful. The precision, flexibility, and beauty 
> I'm aiming for may be useless. Container hierarchies may have some other 
> awesomeness I'm failing to see. But for the time being I'm very 
> seriously considering a simple design:
> 
> * Each specific container is an unconnected class (or struct, haven't 
> decided yet - probably structs to accommodate reference-counted containers);

Also, structs would reduce the indirections required to access the data, when
placing them inside other aggregates as well as reduce memory allocation
traffic.  I'd rather not pay for 2 allocations to create an instance of:

class C { vector!(int) v; }
 
> * Naming matches dictate semantic matches. There should be no false 
> friends - if a container defines removeFront, that should mean the same 
> thing as for other containers (i.e. O(1) removal of the first element).

This I would hesitate a bit on.  I recently changed STL maps for custom hashmaps and
not changing operator[] for different code is useful.  I'm changing the computational complexity
of an operation but conceptually it's the same kind of access.  I'm doing so because I know
that for my application, the tradeoffs elsewhere are acceptable.

> This design follows and enriches STL's design even after we have, as a 
> community, seen many hierarchy-based designs, and even though it looks 
> like hierarchies have "won". The main improvements I want to bring to 
> STL's design are (a) a better categorization of containers, (b) of 
> course replace iterators with ranges, (c) either eliminate allocators or 
> make them work.
> 
> Needless to say, I'd be very curious to hear other opinions in this 
> matter. Please speak up - the future of D depends, in small part, on 
> this too.

The concept of allocators is nice in principal, though I've never had to put them
into action.  A couple of places I could see having used STL allocators: wrapping
JNI memory or GC memory in an STL container.  Neither is particularly necessary
in D.  Another place I could envision an allocator is if I load a large static data
structure with mmap and want to wrap an STL structure around it.   I've wanted to
do this in particular with strings.  This is where C++ allocators fall down at least.
Trying to mix custom allocated data structures with standard ones is going to be painful. 

Jerry