Daniel James wrote:
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.
The allocator stuff is really a problem. Although I haven't seen any useful uses of address(), I agree that I could offer the possibility to store an object with address() and other related functions. But internally i need more than that because I also need a way to implement static_cast and const_cast for non-raw pointer. Currently I'm doing this converting the smart pointer to a raw pointer, doing the conversion, and going back. In Boost, even with Boost 1.34 cast functions (boost/pointer_cast.hpp) I contributed, there is no "official" generic way to do pointer casting. Another possibility is that the object I allow to be contained inside the intrusive container could have both allocator and casting functions. In general, current allocator approach is lacking in both pointer conversion and placement construction issues.
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.
That's another problem. And take in care that if we want to obtain no-throw move constructors and assignments and maintain the moved vector usable, storing the "end" node inside the container is a must. If we want: //Imagine list allocates the "end" node using the allocator std::list<MyObject> list; //If we want list to be usable after being moved //we must COPY the allocator and ALLOCATE a new //end node. Both operations might throw! std::list<MyObject> list2(std::move(list)); Howard can correct me if I'm wrong but I think the Metrowerks/Freescale implementation of std containers using move semantics store the end node inside the container to achieve no throw guarantee in default construction and move operations in node containers. I the standard requires that containers should have no throwing move operations (which would be really nice), then we have a big problem with allocators.
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.
In Interprocess I've reworked all the containers to so Intrusive. I've decided just support pointers that allow conversions to raw pointers. A limitation, but still more flexible than usual STL implementations.
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.
Nice comment. The bucket number is already calculated in the insert_check function so this wouldn't cost more than one extra word for insert_commit_data. I want to maintain insert_commit as a no-throw operation since I think it's a big advantage.
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?
Not for the moment. Another question: would you make irbtree and ihashtable implementation classes public? Normally vendors implementing set/multiset/map/multimap classes implement those using a common tree class. This tree class could be based in irbtree, so maybe this class could be offered as a new associative container: one that allows unique and multiple insertion functions. I'm really think that if I can make Intrusive a good tool to implement standard containers, that would mean that the library is complete a good enough for any task.
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.
I think Dinkumware used a doubly linked list in their old hash implementation. I don't know about TR1, though. This doubly linked list-based hash container would be also interesting to offer, since it has some advantages (a lightweight iterator, for example, and faster erasure functions for if we insert a lot of objects with the same key) comparing it to the classic, singly linked list array approach.
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.
Specially non-trivial functions like sorting, merging... A slist/list sorting that achieves the same performance as list::sort is not trivial to write. Regards, Ion