std.container & ranges

[Marco Leise]

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

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