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

Subject: Re: [Boost-users] [intrusive] first impression and constant-time removal
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2009-02-05 13:11:03

Erik Cassel wrote:
> Hello,
> 
> I like the intrusive library. I'm refactoring my code to use it in many
> places. 

Thanks.

> 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. 

Just like you erase it in std::list: erase(), you need an iterator. From 
the documentation:

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/intrusive/list.html#id3017662-bb

iterator erase(const_iterator i) ;

Effects: Erases the element pointed by i of the list. No destructors are 
called.

Returns: the first element remaining beyond the removed element, or 
end() if no such element exists.

Throws: Nothing.

Complexity: Constant.

Note: Invalidates the iterators (but not the references) to the erased 
element.

>>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));

If you have a reference to an element:

list.erase(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)

I think it's redundant.

> It might follow the same pattern as std::set's erase, which returns the
> erasure count (0 or 1) as a size_t. 

That can be a good idea, since many lists have no constant-time size, so 
the user should be informed of how many elements have been erased. It's 
not std compliant but it does not break any code, since the function 
returned nothing.

> 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".

You need to know if the element is linked or not. is_linked is not 
enough because the element could be linked in another list. The 
programmer must be sure that the element is in the list to form a 
correct iterator.

> 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".

Ok. That's a good idea.

> -Erik

Regards,

Ion