View mode: basic / threaded / horizontal-split · Log in · Help
June 27, 2012
Removing from SList (std.container)...
How can I do that?

Why not list.remove(x); like in STL?
June 27, 2012
Re: Removing from SList (std.container)...
On Wednesday, 27 June 2012 at 09:37:01 UTC, Minas Mina wrote:
> How can I do that?
>
> Why not list.remove(x); like in STL?

std.container encodes the complexity of operations in the method 
names. There is no way to remove a range in constant time in 
SList, so you only get linearRemove.

And you always need a range to remove something.
June 27, 2012
Re: Removing from SList (std.container)...
On Wednesday, 27 June 2012 at 09:52:14 UTC, Tobias Pankrath wrote:
> On Wednesday, 27 June 2012 at 09:37:01 UTC, Minas Mina wrote:
>> How can I do that?
>>
>> Why not list.remove(x); like in STL?
>
> std.container encodes the complexity of operations in the 
> method names. There is no way to remove a range in constant 
> time in SList, so you only get linearRemove.
>
> And you always need a range to remove something.

Can you show me an example or removing a number?
June 27, 2012
Re: Removing from SList (std.container)...
> Can you show me an example or removing a number?

I think that is a prime example of why std.container sucks both 
in documentation and implemantation.

We really need to improve here, sadly development seems to be 
bottlenecked by Andrei working on on allocator proposal. And 
Andrei is busy at the moment.

Here is the solution. You actually need 4 different modules from 
phobos to do this and it is absolutely not obvious how to do it.

import std.algorithm;
import std.range;
import std.container;
import std.array;

void main(string[] args)
{
    SList!int list = [1,2,3,4,5]; // our list
    writeln(list.array()); // need to create an array to print 
nicely
    auto pos = find(list[], 4); // we need a range, so we search 
for the number
    auto pos2 = take(pos, 1); // but find returns a range over 
the rest, so take one
    list.linearRemove(pos2); // remove it
    writeln(list.array()); // print it
}


I needed to look it up myself and didn't find a solution on first 
try.

My first error: You can't just do find(list, 4), because an SList 
is not a range by itself. So you need opSlice (list[]) to get a 
range over list.

Then I knew already that find gives me not what I want. I somehow 
need to restrict the range pos to the first element. But how to 
do it? I wouldn't expect  a newcomer to come up with a solution 
on its own, because pos[0..1] will not work on a forward range. 
Luckily I knew std.range.takeOne.

But hold! takeOne(pos) does not work, you need take(pos, 1).

That sucks.

None of the above is stated explicitly in the documentation. I 
knew that the container generally need a range that was extracted 
from them. How should I know that in this special case a range 
from std.range will work, too? And not all ranges work, only the 
one from take.
June 27, 2012
Re: Removing from SList (std.container)...
Thank you for your reply. Yes, std.container really sucks.

Anyway, I made my program using C++ and STL
June 27, 2012
Re: Removing from SList (std.container)...
On Wed, 27 Jun 2012 05:37:00 -0400, Minas Mina  
<minas_mina1990@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

-Steve
June 27, 2012
Re: Removing from SList (std.container)...
On Wednesday, June 27, 2012 08:25:04 Steven Schveighoffer wrote:
> On Wed, 27 Jun 2012 05:37:00 -0400, Minas Mina
> 
> <minas_mina1990@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.

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

- Jonathan M Davis
June 27, 2012
Re: Removing from SList (std.container)...
On Wed, 27 Jun 2012 13:44:34 -0400, Jonathan M Davis <jmdavisProg@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@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
June 27, 2012
Re: Removing from SList (std.container)...
On Wednesday, 27 June 2012 at 18:26:46 UTC, Steven Schveighoffer 
wrote:
> 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.
Do you mean something like indexed/sorted dictionary? It doesn't 
seem to be that easy to implement. Or some other data structure 
with O(1) removal?
June 27, 2012
Re: Removing from SList (std.container)...
On 06/27/2012 08:46 PM, Roman D. Boiko wrote:
> On Wednesday, 27 June 2012 at 18:26:46 UTC, Steven Schveighoffer wrote:
>> 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.
> Do you mean something like indexed/sorted dictionary? It doesn't seem to
> be that easy to implement. Or some other data structure with O(1) removal?

O(1) removal works quite ok for a singly linked list. eg:

1.
- Add a sentinel node to the start of your list.
- Represent an iterator into the list as a pointer to the predecessor
  of the respective node.
- Removal: trivial. rebind the 'next' reference of the pointed-to node.

2.
- Represent the empty list as a sentinel node with null 'next' field.
- For removal of a node you own a pointer to:
 -- case 1: the successor is an empty list:
    - destroy the value, set the 'next' reference to null.
 -- case 2: else:
    - move the successor's value into the node that holds the value to
      be removed, bind the 'next' reference to the successor of the
      successor.
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home