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

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.

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.

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.

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

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

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)

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?

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

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