Container hierarchy vs. container types

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> 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.

I wasn't debating the point, just organizing ideas.

> 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.

I agree. Interface ranges are unfortunately a poor practical proposition.

>> 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.

It's not the only reason, but it is the primordial reason - just like 
"transportation" is a reason for buying a car. It would be a failure to 
define containers that can't work with std.algorithm.

> 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.

The sort example is good, but I wonder how many of those are out there.

> 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.

Perfect. So I take it we can focus on the federation of containers approach?


Andrei