Re: [boost] [Review] [Intrusive]

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-04-11 11:39:34

Hi Rei,

Rei Thiessen wrote:
> Hello,
>  
> This is not a formal review of the Intrusive library, but from what I
> briefly gathered, the design, implementation, and documentation is
> excellent.
> 
> However I have one suggestion for the documentation:
> iunordered_set, iunordered_multiset, and islist containers expect the same
> slist_algorithms interface for its node.  Also the slist_algorithms
> interface is a subset of the list_algorithms interface.  So a type with any
> one of the iunordered_set/iunordered_multiset/islist/ilist hooks is
> compatible with iunordered_set/iunordered_multiset/islist containers.  I
> think this interchangeability should be mentioned in the same section that
> describes iunordered_set/iunordered_multiset/islist/ilist hooks, since this
> is a very desirable and powerful feature.

In practice yes, because the hash table uses singly linked lists. But 
what if for any reason boost users decide that a doubly linked list is 
more useful because offers reverse iterators? The unordered containers 
are a bit complicated because they have no node algorithms and they are 
usually implemented using linked lists (but we could have used a 
balanced tree, for example). I might decide to add the hash value to the 
hook as a policy to obtain faster rehashing if the keys are expensive to 
hash (imagine long strings or containers as keys).

On the other hand, it's nice to have just a hook that can be used for 
more than one container, so that we can save some space. I have no plans 
to change the hashtable implementation, maybe I will add an additional 
doubly linked list new hash containers if they are considered useful.

You can definitely define your own hook that does this, but that's too 
advanced. Maybe Intrusive might have an utility that we could use to 
define a hook compatible with several hooks. Something like:

typedef union_base_hook<islist_base_hook<>, iunordered_base_hook<>, 
ilist_base_hook<> >::type union_hook;

union_hook could be used to define an type that can be inserted in a 
list, an unordered set, a doubly linked list, but not at the same time 
(the safe mode would detect such errors). I don't know if the 
implementation of union_hook is easy or not, but I think its an 
interesting feature to safe some space in our classes.

If this fails, I would choose to remove unordered_xxx_hook and just use 
slist_xxx_hook.

Thanks for the suggestion and for your positive comments about the library.

Regards,

Ion