On Mon, 08 Mar 2010 00:20:31 -0500, Robert Jacques <[email protected]>
wrote:
On Sun, 07 Mar 2010 22:07:14 -0500, Steven Schveighoffer
<[email protected]> wrote:
On Sun, 07 Mar 2010 12:43:09 -0500, Robert Jacques <[email protected]>
wrote:
On Sun, 07 Mar 2010 08:23:03 -0500, Steven Schveighoffer
<[email protected]> wrote:
[snip]
Please define for me an O(1) slice or index operation for a
linked-list.
One for which you have references to the slice end points. I think
this will work, and I was planning on providing it in the upcoming
dcollections port. The only thing you cannot guarantee is that the
order is correct.
The container would have to do an O(N) search to verify the ranges are
actually part of the collection. And using two ranges as iterators to
create a third range feels very wrong and very bug prone: see all the
issues raised during Andrei's iterators vs ranges presentations.
Similarly, it feels wrong for something to define slicing and not
indexing.
Not two ranges, two references. That is what cursors are in
dcollections. They currently are akin to iterators, but are being changed
to immovable references.
BTW, I don't plan on adding this as a simple slice operation on a
container that cannot quickly verify that the two cursors are ordered, to
ensure it isn't accidentally used in functions that want safe slicing.
You don't need O(n) to verify the cursors are part of the collection if
the cursors identify the collection they are from.
Hm... my hash outperforms builtin AAs by a wide margin. But this is
not technically because my implementation is better, it's because AA's
use "dumb" allocation methods. I don't know about false pointers, the
hash nodes in my implementation only contain pointers, so I'm not sure
there is any possibility for false ones.
The GC isn't precise, so if you have a non-pointer type in a structure
with a pointer or in a class, you'll get false pointers. (i.e. the hash
value at each node)
I don't store the hash in the node, it is recalculated when a re-hash is
done.
I think you are overestimating the life of ranges on a container. They
will not survive that many mutations, and the worst that happens is the
range continues on fully allocated memory (i.e. your #1 above).
A year ago I would have agreed with you, but then I saw a couple of
articles about how this unlikely event does start to occur repeatably in
certain circumstances. This made a bunch of news since it threw a
massive spanner in lock-free containers, which relied on this never
happening.
references?
You can also force the container to invalidate itself once the first
wrap occurs. This at least will be a hard error.
So every container will have a finite number of operation and that's it?
That's one solution, if you want to be sure this bug doesn't occur, and
you want to be sure your ranges aren't invalidated.
-Steve
