How can I do that?

Why not list.remove(x); like in STL?

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.

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?

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

Thank you for your reply. Yes, std.container really sucks.

Anyway, I made my program using C++ and STL

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

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

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

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?

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.