Container insertion and removal

[Steven Schveighoffer]

On Mon, 08 Mar 2010 00:20:31 -0500, Robert Jacques <sandford at jhu.edu>  
wrote:

> On Sun, 07 Mar 2010 22:07:14 -0500, Steven Schveighoffer  
> <schveiguy at yahoo.com> wrote:
>> On Sun, 07 Mar 2010 12:43:09 -0500, Robert Jacques <sandford at jhu.edu>  
>> wrote:
>>> On Sun, 07 Mar 2010 08:23:03 -0500, Steven Schveighoffer  
>>> <schveiguy at yahoo.com> 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