Supporting non-standard pointer types in STL containers

[Bob Walters]

On Jul 7, 2008, at 6:08 AM, Paolo Carlini wrote:

> Hi,
>
> I quickly skimmed the patch and at the moment I'm mostly worried by  
> the change to _Rb_tree_iterator, I don't think we can change the  
> type (add a template parameter for the allocator) and keep the level  
> of binary compatibility that we want.

Is the problem that you are concerned about cases of libraries which  
expose map<> types externally, passing maps between a library built  
with one version of the code and a library built with another?  I had  
not thought of that.  I was concerned primarilly about the ABI between  
compiled instances of _Rb_tree and the libstdc++-v3 library itself.

> Additionally to that, which at the moment seems a show stopper to  
> me, I'm also concerned that, even assuming the other concerns (about  
> the layout of _Rb_tree_impl for example) turns out to be unfunded,  
> it looks like we are going to break binary compatibility with the  
> existing instantiations with Alloc != std::allocator, that seems  
> bad, after all the efforts we made in the past to clean the  
> containers to work also with stateful allocators (well, still not  
> optimally performance wise, but that is another binary compatibility  
> issue which must wait for the next break, unfortunately).

The following is true (I think):  If the allocator used with an  
instance of _Rb_tree uses a standard pointer type, then the resulting  
code which is compiled is binary-compatible with the code created by  
the prior version of std_tree.h.  A tree could be safely passed  
between object modules compiled with before/after versions of  
stl_tree.h, even when a non-standard allocator has been used.  This is  
because _Rb_tree_node_base_T<_Alloc> is in that case the binary  
equivalent to _Rb_tree_node_base, and the execution of the old  
_Rb_tree_node_base code against instances of _Rb_tree_node_base_T<>  
would work.   (Note that the _Alloc is not used as a member of the  
_Rb_tree_node_base_T<> - it is only used to decide the pointer type.)   
The same is true of the iterators.   I will have to write a test which  
confirms this, but from looking over the code, and what the new  
templatized iterator and node_base_T types instantiate into, I think  
this is true.  If not, I accept that I'll need to make it true.

I could strive to base the specialization on the pointer type of the  
_Alloc class, if that helps to address your concern.  i.e. Rather than  
specialize for the use of _Rb_tree_node_base for all cases of _Alloc  
== allocator<T>, I'll base that on all cases where _Alloc::pointer =  
T*.   That might make the code a little ugly.  If there was such a  
thing as rebind() for pointer types, I could have made this clearer in  
the implementation.

One area where ABI compatibility is definitely broken is in the case  
where existing code was passing an allocator which used a non-standard  
pointer type.  prior versions of stl_tree.h would effectively ignore  
that, but new versions would not, resulting in potentially different  
binary forms of the _Rb_tree nodes and iterators.  However, this is a  
side effect of the change I am trying to introduce, and it is  
impossible to maintain this level of ABI and introduce this change.   
Is this particular ABI incompatibility acceptable?

One specific request about the design:  Because of the difficulties  
making normal casts (const_cast<>, specifically) work in the resulting  
code, I had to adopt the convention of using  
cast_to<T>::using_const_cast(), so that the way casting works could be  
specialized for specific pointer types.  The implications of this is  
that any code which intends to support custom pointer types has to   
make use of the cast_to<> class, rather than normal C++ casts,  
throughout that code.  I was concerned about this, but have found it  
necessary.  It's a more intrusive approach than I had originally  
planned, and I want to make sure that introducing this convention into  
container implementations will be acceptable.

Bob