View mode: basic / threaded / horizontal-split · Log in · Help
June 27, 2012
Re: Removing from SList (std.container)...
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
June 27, 2012
Re: Removing from SList (std.container)...
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.
June 27, 2012
Re: Removing from SList (std.container)...
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.
June 27, 2012
Re: Removing from SList (std.container)...
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.
June 27, 2012
Re: Removing from SList (std.container)...
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.)
June 27, 2012
Re: Removing from SList (std.container)...
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
June 27, 2012
Re: Removing from SList (std.container)...
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)
June 27, 2012
Re: Removing from SList (std.container)...
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?
June 27, 2012
Re: Removing from SList (std.container)...
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).
June 27, 2012
Re: Removing from SList (std.container)...
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
1 2 3
Top | Discussion index | About this forum | D home