On Sat, 17 Mar 2007 15:18:59 -0000, Ion Gaztañaga <igaztanaga@gmail.com> 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