On Sat, 05 Nov 2011 17:28:34 -0400, Marco Leise <marco.le...@gmx.de> wrote:
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);
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
