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 "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next 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 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.

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
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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "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.

seem to be that easy to implement. Or some other data structure with O(1) removal?
Jun 27 2012
prev sibling next sibling parent "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.

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
prev sibling next sibling parent "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.

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.

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

Jun 27 2012
prev sibling next sibling parent "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.


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
prev sibling next sibling parent "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.

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
prev sibling next sibling 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.

use cases, like this one.)
Jun 27 2012
prev sibling next sibling parent "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.


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
prev sibling next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling 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 next sibling parent "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
prev sibling next sibling parent "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
prev sibling next sibling parent "Minas Mina" <minas_mina1990 hotmail.co.uk> writes:
Doesn't Andrei plan to do something about this module?
Jun 27 2012
prev sibling 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