Re: [boost] Ion Gaztañaga's Intrusive Library

From: Daniel James (daniel_james_at_[hidden])
Date: 2007-03-18 06:43:26

On Sat, 17 Mar 2007 15:18:59 -0000, Ion Gaztañaga <igaztanaga_at_[hidden]>  
wrote:

> Waiting for your comments. I would like to know if you consider
> Boost.Intrusive complete enough to be a valuable tool to build
> non-intrusive containers (like STL containers or TR1 unordered  
> containers).

Well, I think they could be useful for building non-intrusive containers  
in general but I'm not sure about STL containers, as they tend to have  
very demanding requirements.

If you want to fully support STL allocators then you'll need to use the  
allocator's address function to get a pointer object from a reference or  
pointer. I think you could add an extra function to do this to your node  
traits class, but it'd need some way to access the allocator - so the  
traits class would need to also be able to store an allocator.

And address can only be called with references to objects created with the  
allocator itself, in ilist you use node_ptr to point to the root node  
which wouldn't created with the allocator.

Of course, most STL implementations don't fully support allocators to this  
level so maybe it doesn't matter. But I'd imagine making the traits  
flexible enough to account for this kind of thing would be too complex.

Taking a quick look at iunordered_set, there would also be problems  
implementing an unordered_set with that. One problem is the exception  
requirement for insert:

> For unordered associative containers, if an exception is thrown
> by any operation other than the container’s hash function from
> within an insert() function inserting a single element, the
> insert() function has no effect.

This needs carefull implementation. All calls to the equality predicate  
and object construction need to be done before a rehash but, in your  
implementation, a rehash will invalidate insert_commit_data (actually, you  
should mention that in the documentation, or have I missed something?).  
You could change the implementation to support this - insert_commit_data  
would need to store the hash value, and then insert_commit would  
recalculate the bucket.

I suspect there are probably other similar problems and I'm not sure if  
it's worth the complication of fully supporting the STL. Although, if this  
is intended to be standardized. maybe it is?

An unfortunate problem is that in C++ today the implementation of template  
code is not hidden from the user - error messages will be made worse by  
the extra layer of abstraction. Although, concepts might help considerably  
and even negate that problem.

Implementors often use unusual data structures. I believe the dinkumware  
unordered containers use a skip list for the buckets. The data structure I  
use for unordered_multiset/unordered_multimap isn't directly supported  
(I'll document it soon - it's pretty unusual). A combination of intrusive  
containers and pointer manipulation could be used - but I think it'd get  
quite clumsy.

Having said all that, I do think they could be useful for creating  
containers. Even for seemingly trivial structures, such as a singly linked  
list, have their complications. Getting a ready made iterator is a  
definite plus.

Daniel