Container hierarchy vs. container types

[Steven Schveighoffer]

On Fri, 05 Mar 2010 11:53:47 -0500, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> Steven Schveighoffer wrote:
>> On Thu, 04 Mar 2010 18:22:55 -0500, Andrei Alexandrescu  
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>>
>>> 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.
>>  As you know, you and I disagree on some aspects of containers.   
>> However, I think our philosophies are converging.
> [snip]
>
> To summarize my understanding of your points:
>
> (a) When you only want to tweak a container's behavior in small ways,  
> inheritance is great.
>
> (b) Pass by reference is more natural for containers than pass by value.
>
> (c) Proprietary code hiding is better with interfaces.
>
> (d) Dynamically-linked code works best with interfaces.
>
> (e) Interface-based code requires less recompilation and may save on  
> generated code.
>
> (f) Interfaces simplify understanding.
>
> At the same time, you argue that ranges aren't fit as interfaces because:
>
> (a) Inlinining is difficult/impossible
>
> (b) Value semantics is more natural for ranges

A range is not a container.  A range is a small reference-like construct  
that points to a containers elements.  I stand by what I said, a container  
is more natural as a reference, ranges are more natural with value  
semantics.

If I pass an abstract range into something like std.algorithm.sort, the  
performance is going to be much worse than using a value-type range.  The  
implementation has the option of doing the latter, so why not make it an  
interface function?  In addition, std.algorithm.sort is going to expect  
value-type ranges, so you have to make copies everywhere, incurring more  
performance hits.

> One other thing I'm worried about, and was an absolute pain in my  
> preliminary tests of container implementations, is this issue of  
> "iterators/ranges/cursors are not part of the container interface". It  
> is absolutely fundamental that you can get an abstract range from an  
> abstract container because most of what you can do to a container you  
> must do with ranges. Otherwise the duplication of functionality is  
> horrid. This failure alone is a reason to abandon the container  
> hierarchy design.

It depends on what you want to do with the container.  std.algorithm is  
not the only reason to have containers.

Duplication of functionality is unavoidable if you do not have abstract  
ranges.  However, by "duplication" it most likely means forwarding calls  
to range-accepting functions.  For example, a List interface may have a  
sort function.  The implementation can forward to std.algorithm.sort if  
the list is an array, or to an internal merge sort if it is a linked list  
(in fact, this is similar to what I do now in dcollections).  I don't  
really know how you would do this without knowing one is a linked list and  
one isn't.

It's possible to take a flat non-interfaced collection library and build  
an interface on top of it, I don't see why it detracts from the original  
non-interface API.

-Steve