std.container & ranges

[Steven Schveighoffer]

On Sat, 05 Nov 2011 17:28:34 -0400, Marco Leise <Marco.Leise at gmx.de> wrote:

> Am 02.11.2011, 12:48 Uhr, schrieb Steven Schveighoffer  
> <schveiguy at yahoo.com>:
>> In dcollections, removing a specific element (using the default  
>> comparison operator for that element) on a *fast lookup* container is  
>> as simple as:
>>
>> container.remove(container.find(x));
>>
>> Which removes the element x if it's found.  However, this is not  
>> defined for containers which use O(n) time to search (such as linked  
>> list), you must use std.algorithm.find for that:
>>
>> container.remove(find(container[], x).begin);
>>
>> Should work, and takes O(n) time.
>>
>> -Steve
>
> While I stumble over this. I found that I sometimes need a certain  
> container (data structure/algorithm), but with an additional fast  
> removal or lookup. So I returned a "handle" (a pointer or array index)  
> for any inserted element that you can store (in the element itself for  
> example) and use for lookup/removal. Templates bake the correct struct  
> for this:
>
> // The element I want to store
>
> struct Element {
>    // ... actual data
>    size_t handle; // a pointer to a node in disguise, returned from  
> insert(...)
> }
>
> // A collection node
>
> struct Node {
>    Element e;
>    Node* prev;
>    Node* next;
> }
>
> // Usage
>
> elem.handle = list.insert(elem);
> list.remove(elem.handle);

You should be able to do this with dcollections:

struct Element(T) {
    T data;
    List!T.cursor handle;
}

elem.handle = list.insert(list.end, elem.data); // x is the value being  
inserted
list.remove(elem.handle);  // removes the element you inserted earlier.

Note, you have to specify an insertion point (this is similar to C++).   
But note that you can't exactly create a handle to a list of the Element  
type, because you need that cursor type to define Element.

> Now you have a double-linked list with O(1) removal, as long as you keep  
> the handle around. The limitation is, that the handle has to remain  
> constant. So a binary heap with the elements embedded in an array and no  
> indirection through a pointer would not work. As soon as elements are  
> reorganized, their handle (array index in this case) becomes invalid.
> But the point is, that you can reduce the time complexity for removal in  
> every data structure like this in an implementation agnostic way (unless  
> plain array of elements) and I think it is better than Java's approach  
> that just works, but may result in an O(n) lookup operation.
> Iterators with remove functionality overlap with this partially. (They  
> don't need an extra handle stored somewhere, but generally go over the  
> complete list.)

Definitely.  This is the benefit of iterators/cursors.  The ability to  
refer to exactly one element makes things much more straightforward.  It's  
why dcollections has cursors.

-Steve