www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Removing from SList (std.container)...

reply "Minas Mina" <minas_mina1990 hotmail.co.uk> writes:
How can I do that?

Why not list.remove(x); like in STL?
Jun 27 2012
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Jun 27 2012
parent reply "Minas Mina" <minas_mina1990 hotmail.co.uk> writes:
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?
Jun 27 2012
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
 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.
Jun 27 2012
parent "Minas Mina" <minas_mina1990 hotmail.co.uk> writes:
Thank you for your reply. Yes, std.container really sucks.

Anyway, I made my program using C++ and STL
Jun 27 2012
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Jun 27 2012
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jun 27 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
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
Jun 27 2012
parent reply "Roman D. Boiko" <rb d-coding.com> writes:
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?
Jun 27 2012
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 27 2012
parent reply "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 19:06:46 UTC, Timon Gehr wrote:

 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.


Nice. But forces to use iterators everywhere.
Jun 27 2012
parent "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 20:00:18 UTC, Roman D. Boiko wrote:

 Nice. But forces to use iterators everywhere.


(I'm not against iterators, they are almost necessary in certain 
use cases, like this one.)
Jun 27 2012
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 27 Jun 2012 14:46:36 -0400, Roman D. Boiko <rb d-coding.com> 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?


struct Link
{
   int val;
   Link *next;
   removeNext() {assert(next); next = next.next;}
}

O(1) removal, easy as that.

Look up SList docs, even with a reference to a *specific element*, you  
cannot do O(1) removal.

Only recently did it add O(1) insertion, but only after a specific  
element.  Good luck implementing a way to do insert *before* that element  
in O(1), it will be possible, but really obtuse.

-Steve
Jun 27 2012
parent reply "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 19:10:24 UTC, Steven Schveighoffer 
wrote:

 On Wed, 27 Jun 2012 14:46:36 -0400, Roman D. Boiko 
 <rb d-coding.com> 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?


 struct Link
 {
   int val;
   Link *next;
   removeNext() {assert(next); next = next.next;}
 }

 O(1) removal, easy as that.


I thought you meant removal by index or value, not element 
reference.


 Look up SList docs, even with a reference to a *specific 
 element*, you cannot do O(1) removal.


Ha-ha, didn't know SList doesn't support that.
Jun 27 2012
parent reply "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 19:55:02 UTC, Roman D. Boiko wrote:

 Look up SList docs, even with a reference to a *specific 
 element*, you cannot do O(1) removal.


 Ha-ha, didn't know SList doesn't support that.


I somehow confused removal after a referenced element (which 
should be easy to implement, but not very useful) with removal of 
that element (which is not possible in 0(1) in a singly-linked 
list.
Jun 27 2012
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 27 Jun 2012 15:57:42 -0400, Roman D. Boiko <rb d-coding.com> wrote:


 On Wednesday, 27 June 2012 at 19:55:02 UTC, Roman D. Boiko wrote:

 Look up SList docs, even with a reference to a *specific element*, you  
 cannot do O(1) removal.


 Ha-ha, didn't know SList doesn't support that.


 I somehow confused removal after a referenced element (which should be  
 easy to implement, but not very useful) with removal of that element  
 (which is not possible in 0(1) in a singly-linked list.


Removal of that element is perfectly possible, you just need to maintain a  
reference to its predecessor.  Which SList's range does not keep track  
of.  It all depends on tradeoffs of what you want for performance, vs.  
features.  It's why I contend that generic singly linked list is difficult  
to create.  Can't please everyone.

And iterators are not necessary, ranges are quite possible.

-Steve
Jun 27 2012
parent reply "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 20:14:53 UTC, Steven Schveighoffer 
wrote:

 Removal of that element is perfectly possible, you just need to 
 maintain a reference to its predecessor.  Which SList's range 
 does not keep track of.  It all depends on tradeoffs of what 
 you want for performance, vs. features.  It's why I contend 
 that generic singly linked list is difficult to create.  Can't 
 please everyone.


Yes, I agree.


 And iterators are not necessary, ranges are quite possible.


In this respect it is not only a performance vs. features 
tradeoff, semantics is (usually) different. Of course, we might 
use a range for what is semantically an iterator. But it feels 
unnatural for me.

E.g., to point to an element in the middle of some range we would 
need to create another range and pass it to a function along with 
the original range. I would hesitate to call them ranges unless 
that is explicitly a goal for some particular application. If 
that was the case, it would require an explicit explanation. (IMO)
Jun 27 2012
next sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
On Wednesday, 27 June 2012 at 20:29:02 UTC, Roman D. Boiko wrote:

 On Wednesday, 27 June 2012 at 20:14:53 UTC, Steven 
 Schveighoffer wrote:

 Removal of that element is perfectly possible, you just need 
 to maintain a reference to its predecessor.  Which SList's 
 range does not keep track of.  It all depends on tradeoffs of 
 what you want for performance, vs. features.  It's why I 
 contend that generic singly linked list is difficult to 
 create.  Can't please everyone.


 Yes, I agree.


 And iterators are not necessary, ranges are quite possible.


 In this respect it is not only a performance vs. features 
 tradeoff, semantics is (usually) different. Of course, we might 
 use a range for what is semantically an iterator. But it feels 
 unnatural for me.

 E.g., to point to an element in the middle of some range we 
 would need to create another range and pass it to a function 
 along with the original range. I would hesitate to call them 
 ranges unless that is explicitly a goal for some particular 
 application. If that was the case, it would require an explicit 
 explanation. (IMO)


Why pass the original range?
Jun 27 2012
parent "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 21:22:31 UTC, Tobias Pankrath wrote:

 E.g., to point to an element in the middle of some range we 
 would need to create another range and pass it to a function 
 along with the original range. I would hesitate to call them 
 ranges unless that is explicitly a goal for some particular 
 application. If that was the case, it would require an 
 explicit explanation. (IMO)


 Why pass the original range?


I mean the range on which to perform an operation. It could be 
passed via this parameter of member function or explicitly. It 
could be not needed for some operations (trivial, like copy or 
compare).
Jun 27 2012
prev sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, June 27, 2012 22:29:01 Roman D. Boiko wrote:

 On Wednesday, 27 June 2012 at 20:14:53 UTC, Steven Schveighoffer
 
 wrote:

 Removal of that element is perfectly possible, you just need to
 maintain a reference to its predecessor. Which SList's range
 does not keep track of. It all depends on tradeoffs of what
 you want for performance, vs. features. It's why I contend
 that generic singly linked list is difficult to create. Can't
 please everyone.


 
 Yes, I agree.
 

 And iterators are not necessary, ranges are quite possible.


 
 In this respect it is not only a performance vs. features
 tradeoff, semantics is (usually) different. Of course, we might
 use a range for what is semantically an iterator. But it feels
 unnatural for me.
 
 E.g., to point to an element in the middle of some range we would
 need to create another range and pass it to a function along with
 the original range. I would hesitate to call them ranges unless
 that is explicitly a goal for some particular application. If
 that was the case, it would require an explicit explanation. (IMO)


If you want a single element, then use take, takeExactly, or takeOne. For 
instance, that's what you do when you want to use remove in std.container 
(though apparently takeOne was missed as pointed out earlier in this thread, 
which needs to be remedied). It is true that dealing with ranges in this sort 
of situation is a bit more problematic than it is with iterators, but the 
take* functions take care of it as long as the container properly takes them 
into account (which std.container's containers are supposed to do). And if all 
you care about is having a range with one element and not whether the range is 
passable to a function on it's associated container, then the take* functions 
work just fine regardless of whether the container properly takes them into 
account. It's only an issue with the container, because the container needs 
its original range type rather than some arbitrary range which may have 
nothing to do with that container (the same happens with iterators - you just 
don't tend to wrap them in other types in the same way that happens with 
ranges).

- Jonathan M Davis
Jun 27 2012
parent reply "Roman D. Boiko" <rb d-coding.com> writes:
On Wednesday, 27 June 2012 at 21:38:28 UTC, Jonathan M Davis 
wrote:

 On Wednesday, June 27, 2012 22:29:01 Roman D. Boiko wrote:

 On Wednesday, 27 June 2012 at 20:14:53 UTC, Steven 
 Schveighoffer
 
 wrote:

 Removal of that element is perfectly possible, you just need 
 to
 maintain a reference to its predecessor. Which SList's range
 does not keep track of. It all depends on tradeoffs of what
 you want for performance, vs. features. It's why I contend
 that generic singly linked list is difficult to create. Can't
 please everyone.


 
 Yes, I agree.
 

 And iterators are not necessary, ranges are quite possible.


 
 In this respect it is not only a performance vs. features
 tradeoff, semantics is (usually) different. Of course, we might
 use a range for what is semantically an iterator. But it feels
 unnatural for me.
 
 E.g., to point to an element in the middle of some range we 
 would
 need to create another range and pass it to a function along 
 with
 the original range. I would hesitate to call them ranges unless
 that is explicitly a goal for some particular application. If
 that was the case, it would require an explicit explanation. 
 (IMO)


 If you want a single element, then use take, takeExactly, or 
 takeOne. For
 instance, that's what you do when you want to use remove in 
 std.container
 (though apparently takeOne was missed as pointed out earlier in 
 this thread,
 which needs to be remedied). It is true that dealing with 
 ranges in this sort
 of situation is a bit more problematic than it is with 
 iterators, but the
 take* functions take care of it as long as the container 
 properly takes them
 into account (which std.container's containers are supposed to 
 do). And if all
 you care about is having a range with one element and not 
 whether the range is
 passable to a function on it's associated container, then the 
 take* functions
 work just fine regardless of whether the container properly 
 takes them into
 account. It's only an issue with the container, because the 
 container needs
 its original range type rather than some arbitrary range which 
 may have
 nothing to do with that container (the same happens with 
 iterators - you just
 don't tend to wrap them in other types in the same way that 
 happens with
 ranges).

 - Jonathan M Davis


It depends entirely on intended semantics and use cases. There is 
a difference between a range, an iterator, and a link (pointer) 
to some container node. I meant a link when I used the term 
"iterator".

To illustrate, imagine a tree container. A link could point to 
some node, which could be used conceptually as a container. A 
range would define a subset of either element values or links for 
some traversal. So a range semantically implies an ordering, and 
is quite different from a link. An iterator seems to be closer to 
a range in this respect, that's why I admitted that I used the 
term incorrectly.
Jun 27 2012
parent reply "Minas Mina" <minas_mina1990 hotmail.co.uk> writes:
Doesn't Andrei plan to do something about this module?
Jun 27 2012
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Thursday, June 28, 2012 00:23:03 Minas Mina wrote:

 Doesn't Andrei plan to do something about this module?


He came up with the basic design, and he's working on the custom allocator 
design. Once that's been sorted out, std.container will be made to use it, and 
more containers will be added to it. We're trying to avoid having to implement 
the containers twice (as would happen to at least some extent if we added them 
all and then added the custom allocators later), which is why there aren't 
more of them yet. But Andrei has been very busy, so progress has been slow, 
and I don't know where he stands with it right now.

- Jonathan M Davis
Jun 27 2012
prev sibling parent Pragma Tix <pragmatix orange.fr> writes:
Am 27.06.2012 14:25, schrieb Steven Schveighoffer:

 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


I Wish dcollections has been part of Phobos 2 years ago.
But thanks to the ongoing one man show (even being absent does not help 
) ,  Library development is more or less stalled.  Don't believe ? 
Github Phobos.

What is the problem in creating  some very simple structures. Queues, 
Deques,  Stacks. create a thread safe version, fine.  None of these 
structures have a need for ranges, respective special allocating ,at all 
THESE structures have a very clear and limited job.

struct Queue(T)
{
	DeQueue() {}
	EnQueue() {}


	struct Node // double linked list node
	{
		T data;

		Node* next;
		Node* previous;

		this (..........)
		{

		}
}

And in case that you don't like that..
struct Queue(T, alias Alloc){} ..
But who cares 'cause the very first queue implementation in Phobos will 
be in 2017.

I've tried (while becoming very unpopular) to encourage you to stop that 
  "waiting for Andrej nonsense, but you behave like Lemmings....

I followed D now for 5.5 years and all I'd like to say now is :
Give up your efforts.
You folks have wasted enough foreign time and audience.

Bjoern Lietz-Spendig
Jun 28 2012