From: Ion GaztaÃ±aga (igaztanaga_at_[hidden])
Date: 2007-03-18 08:10:19
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
//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!
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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk