Subject: [Boost-users] [intrusive] first impression and constant-time removal
From: Erik Cassel (erik_at_[hidden])
Date: 2009-02-05 09:44:19
Hello,
I like the intrusive library. I'm refactoring my code to use it in many
places.
One of the benefits of boost::intrusive is the constant-time removal of
items from a collection. The documentation doesn't tell you how to remove an
element from a list in constant time, so I looked through the API.
At first, "remove" looked like a good idea, but this function removes all
instances that match a given value - so it is O(n). The unwary programmer
will inadvertently use this function, not realizing the huge waste of CPU
time.
>From what I can tell, the way to remove an element in constant time is this:
if (element.is_linked())
list.remove(list.iterator_to(element));
It requires 3 function calls. How about adding the something like the
following function to list?
void remove_member(reference value)
It might follow the same pattern as std::set's erase, which returns the
erasure count (0 or 1) as a size_t.
Summary:
1) I found the remove() function's name ambiguous. It isn't clear that the
complexity is linear time - that it compares elements to a value rather than
taking a reference to an actual element. The only hint is the
const_reference (rather than a reference) argument. Would
"remove_all_matches" would be a better name?
2) Removing an element from a list requires 3 function calls. Wouldn't an
std::set-style erase(reference) be a good addition to the API? It could be
called "remove_member" or simply "erase".
3) If nothing else, it might be wise to have a small section in the
documentation that demonstrates constant-time element removal and warns
against improper use of "remove".
-Erik