[Boost-users] [intrusive] first impression and constant-time removal

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