From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-04-11 11:39:34
Rei Thiessen wrote:
> This is not a formal review of the Intrusive library, but from what I
> briefly gathered, the design, implementation, and documentation is
> 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
Thanks for the suggestion and for your positive comments about the library.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk