Removing from SList (std.container)...

[Steven Schveighoffer]

On Wed, 27 Jun 2012 13:44:34 -0400, Jonathan M Davis <jmdavisProg at gmx.com>  
wrote:

> On Wednesday, June 27, 2012 08:25:04 Steven Schveighoffer wrote:
>> On Wed, 27 Jun 2012 05:37:00 -0400, Minas Mina
>>
>> <minas_mina1990 at hotmail.co.uk> wrote:
>> > How can I do that?
>> >
>> > Why not list.remove(x); like in STL?
>>
>> SList is quite unusable.
>>
>> If you are looking for STL-like containers, there is dcollections which
>> has a doubly-linked list, and supports syntax like you want.
>>
>> http://www.dsource.org/projects/dcollections
>
> There concept of SList is unusable IMHO. The singly-linked list is one  
> of the
> most useless data structures ever invented. It does have some use cases,  
> but
> almost always what you really want is doubly-linked list.

The thing that makes SList useless is the O(n) removal.  Nobody will ever  
use SList when they can write a replacement that has O(1) removal in 10  
minutes.

The concept of singly-linked lists is most certainly not useless.  They  
are perfect for FIFO queues, or LIFO stacks, and they consume 1/3 less  
space than a doubly-linked list (at least for an int/size_t)

My somewhat loose belief is that making a generic singly-linked list is a  
waste of time -- it's too difficult to implement in a way that is  
optimized for the intended use.

> As for std.container, the basics of std.container are good, but the
> documentation isn't good enough for some basic stuff, and some of it  
> needs to
> be ironed out a bit. For instance, the basic idea of how remove works is  
> fine
> given how ranges work (though it's arguably one of those few places where
> ranges are worse than iterators - hence why dcollections has cursors),  
> and
> it's exactly what you want in the general case, but it's arguably overly
> complicated for a lot of basic use cases. Adding stuff like removeFirst  
> which
> removed the first value which matched would greatly simplify a number of  
> basic
> use cases.

I haven't used std.container all that much, but I find the terminology  
very obtuse and verbose.  I can't imagine every using for example  
upperBound without having to look up what it does.

I understand the point, but it needs shortcuts.  Like how you can type  
writeln("x") instead of stdout.writeln("x").  I think that's a small  
difference that is a huge win.

But regardless, any API improvements pale in comparison to the O(n)  
removal problem for SList.

> I've been meaning to figure out a small set of basic functions like that  
> which
> would improve the API's usability for many common cases and propose  
> them, but
> there hasn't been much point in trying to do anything with it, since  
> that sort
> of thing needs to get passed Andrei (who is likely to say that the  
> current
> solution with find and take is just fine, since it's nicely generic and  
> covers
> all use cases), but he's been busy.

It doesn't hurt to propose...  Personally, I don't see myself ever using  
std.container when I prefer the API of dcollections.  But that obviously  
isn't going to be the popular choice, since it's not in phobos.

-Steve