Am 02.11.2011, 12:48 Uhr, schrieb Steven Schveighoffer
<schvei...@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.)
