std.container & ranges

[Steven Schveighoffer]

On Wed, 02 Nov 2011 19:24:03 -0400, Max Wolter <awishformore at gmail.com>  
wrote:

> On 11/2/2011 2:41 PM, Steven Schveighoffer wrote:

>> I never said you couldn't (and I've even given examples of such
>> implementations). It's just not neatly packaged into a method.
>>
>> But again, if the method is exactly the same as the efficient version
>> for other containers, it becomes *impossible* to design an algorithm
>> that guarantees any sort of complexity. As I said before, quadratic sort
>> is epic fail, and needs to always be avoided.
>>
>> I'll give you a scenario:
>>
>> People often complain that Linked List does not have an opIndex on it.
>> Yes it's inefficient, but so what? "I know it's inefficient, let me
>> decide whether it's worth it or not."
>>
>> So let's say I add it to LinkList. Those people are happy.
>>
>> But now, LinkList becomes defined as a *random-access-range* according
>> to std.ranges. Therefore, std.algorithm.sort(linklist) compiles! And is
>> now something like O(n^3).
>>
>> Whereas LinkList already defines a sort method, which uses mergesort
>> (O(nlgn)). So are you going to realize this when reading someones code
>> and you see:
>>
>> sort(somelist);
>>
>> That it's going to be horribly inefficient? Why shouldn't we strive for
>> a library where such things just don't compile?
>>
>
> Hello.
>
> You generally arguing this is all nice and good, but this is a very  
> specific case.
>
> I am using a LinkList because in my code, the elements are iterated over  
> a million times and during this, I add stuff in-between elements all the  
> time. However, I will be removing stuff *very* rarely. I am thus using  
> the appropriate container and it doesn't matter whether the remove will  
> be inefficient.

A linked list (any list really) is important if you want to maintain  
insertion order.  If that's not important, don't use a list, a hash or  
tree is about as efficient.  There exist (not in D) hybrid container types  
that allow O(1) removal using value, and maintain insertion order.

In fact, the actual remove is not inefficient if you have a reference to  
an element (not just the value).  Unfortunately, for SList, this is not  
the case, but it should be fixed at some point.

But I still maintain, anything in std.container is not just a container  
for your code, it's a container that tries to cater to the most common  
needs.  If you want a remove(value) function, it is trivial to write.

> To put it another way: if removing elements was of crucial importance to  
> the performance of my code in the first place, I wouldn't (and  
> shouldn't) be using a LinkList.

As long as you don't need to search for the element to remove using its  
value, removal in a linked list should be O(1).  A linked list that does  
not allow O(1) removal and O(1) insertion given a topological reference is  
a failure (yes, that includes the current version of SList).

> Therefore, implementing an inefficient method which does this won't be  
> of consequence. Finally, the fundamental statement I'm trying to make  
> here is: adding and removing *single* elements should be a  
> straightforward method call for *any* container.

Adding, yes.  Removing a container-selected element, yes.  Removing a  
*specific* element, no.  Inserting an element in a *specific location*,  
no.  std.container has taken the stance that primitives should reflect the  
efficiency of the operation.

This is not the only valid position to have.  It's just std.container's  
position.  For example, Java allows this.

> As a side note, your example about generic programming is really neat  
> and makes sense; personally, I would never want a linked list with  
> indexes and it's also a horrible analogy to the complaint at hand.

People have asked for it and argued vigorously for it on this newsgroup,  
just as you are arguing for this.

-Steve