Boost logo

Boost :

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

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at