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