Re: [boost] Ion Gaztañaga's Intrusive Library

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