On Thu, 03 Nov 2011 17:13:55 -0400, Timon Gehr <timon.g...@gmx.ch> wrote:
On 11/03/2011 09:46 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 14:50:31 -0400, Timon Gehr <timon.g...@gmx.ch>
wrote:
On 11/03/2011 07:15 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 13:47:28 -0400, Timon Gehr <timon.g...@gmx.ch>
wrote:
On 11/03/2011 06:13 PM, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 12:35:36 -0400, Dmitry Olshansky
<dmitry.o...@gmail.com> wrote:
On 03.11.2011 19:34, Steven Schveighoffer wrote:
On Thu, 03 Nov 2011 10:02:22 -0400, Tobias Pankrath
<tob...@pankrath.net> wrote:
Dmitry Olshansky wrote:
And more importantly, it still would be horribly slow O(N^2).
Personally, because of that I'd prefer hand-rolled intrusive
singly-linked list any time of day.
To be honest, I don't understand this.
A "remove_if" for non-intrusive single-linked lists should be
doable in
O(N).
Yeah, poor wording going to kill me one day :) And looking at how
SList works with "checked" remove does O(N^2) turned out to be a
context for reference for intrusive singly-linked list, just my
bad.
As for why I'd rather go with intrusive lists, it's because of it
usually uses less memory due to node structures being more
padding-free.
Anyway the point should have been focused on _hand-rolled_ part,
mostly because SList is plain not ready for prime time*. And btw
singly-linked list it's not hard to implement and you can fine
tune it
how you like it e.g. they do play nice with free list allocation
strategy. Not to say of circular lists and/or using sentinels.
SList is a poor singly linked list implementation. It does not
support
O(1) removal.
-Steve
Aye, looking at SList implementation I can say that it sort of
tries
to verify that this is a correct list. Otherwise it would be O(1).
Indeed passing wrong range/iterator is quite bad in linked lists
and
could lead to all manner of funky bugs, but the cost is horrific.
Especially since insert doesn't do this extra check.
No, it's necessarily doing O(n) search for current node because it
has
no reference to the previous node.
The range type for a SList has a single pointer to the currently
iterated node. How do you remove that node without having access to
the
head/previous pointer?
The container interface does not expose references to the 'Node'
struct, therefore the following approach would be practical:
It does, actually. A range is a reference to a Node struct. But I
still
think the following approach will work.
0. Have a sentinel for end of list. (O(1) additional memory for the
entire list). It is the only node in the list that has a null 'next'
pointer.
example, for removing just the current node:
1. if the following node is not the sentinel
1.1. Move value from following node into the current node.
1.2. Remove following node.
2. if the following node is the sentinel
2.1. erase the contents of the current node (iff it has indirections)
2.2. set it's 'next' field to null
Removing an entire range is just erasing the contents of the current
node and setting the 'next' field of the associated Node to zero.
Removing a Take!Range is a simple generalization of the algorithm
above.
This would be a good addition to the type. It could not be a
stableRemove, however, because it would invalidate any ranges pointing
at the node you removed. Can you put together a pull request?
I can do that, but it will have to wait a few days, as I am quite busy
at the moment.
No rush. I just wanted to know if you would do it, and if not, I would
do it.
If not, I
can see about doing it. One issue, you could not do this if the value
is
immutable/const.
That is true. But how to fix this? Resolving it by simply not exposing
the remove method if it is impossible to implement the straightforward
way would be an option, but I don't think that is satisfying. Probably
it could be made to work by creating some kind of head mutable
structure. I will think about it. It should even be possible to
generalize std.typecons.Rebindable for structs to help this idea.
Hm... rebindable doesn't help if the item is a struct. You'd have to
store an allocated struct on the heap.
-Steve
My point is, if you have a struct like this:
struct S{
const int* x;
immutable int y;
}
Then that could be stored in the list as
struct _S{
const(int)* x;
int y;
S getS(){return S(x,y);}
}
Without putting the type system under pressure.
But on second thought, std.typecons.Rebindable can probably not
meaningfully be generalized to structs because it could not deal with
member functions.
Yes, this looks like a viable solution. Not sure how it would be done in
a generic way. I think what is best is to have getS be like this:
S *getS(){ return cast(S*)&this;}
And never provide access to this
As long as S.opCmp, S.opEquals, and S.toHash are all const, this should be
no issue (this needs to be a requirement).
I wonder if we really have to go through such trouble...
-Steve
