Re: [patch] libstdc++/29988 Rb_Tree reuse allocated nodes

[Jonathan Wakely <jwakely at redhat dot com>]

> > -  template<typename Tp>
> > +  template<typename Tp, typename _Alloc = std::allocator<Tp> >

Also, there's no need to uglify the name "Alloc" in our testsuite
code, it doesn't have to use the implementation namespace.

> >    class uneq_allocator
> > -    : private uneq_allocator_base
> > +    : private uneq_allocator_base,
> > +      public _Alloc
> >    {
> >    public:
> > -      typedef std::size_t                         size_type;
> > -      typedef std::ptrdiff_t                      difference_type;
> > -      typedef Tp*                                 pointer;
> > -      typedef const Tp*                           const_pointer;
> > -      typedef Tp&                                 reference;
> > -      typedef const Tp&                           const_reference;
> > -      typedef Tp                                  value_type;
> > +      typedef typename _Alloc::size_type	size_type;
> > +      typedef typename _Alloc::difference_type	difference_type;
> > +      typedef typename _Alloc::pointer		pointer;
> > +      typedef typename _Alloc::const_pointer	const_pointer;
> > +      typedef typename _Alloc::reference	reference;
> > +      typedef typename _Alloc::const_reference	const_reference;
> > +      typedef typename _Alloc::value_type	value_type;

Also, you should check here that is_same<Tp, _Alloc::value_type>.

That check should work for C++03 too (so can't use is_same or
static_assert) so maybe:

 template<typename T, typename Alloc,
          typename T2 = typename Alloc::value_type>
 struct check_value_type;

 template<typename T, typename Alloc>
 struct check_value_type<T, Alloc, T>
 {
   typedef T value_type;
 };

Then use 

 typedef typename check_value_type<Tp, Alloc>::value_type value_type;

Alternatively, you could redefine the uneq_allocator and
propagating_allocator to take an allocator as their first parameter:

 template<typename Alloc>
   class uneq_allocator : public Alloc
   {
     typedef Alloc inner_allocator;
     typedef __gnu_cxx::__alloc_traits<Alloc> inner_traits;

   public:
     template<typename U>
       struct rebind
       {
         typedef typename inner_traits::template rebind<U>::other
           other_inner;
         typedef uneq_allocator<other_inner> other;
       }

     ...
   };

But that would require a lot of changes to the testsuite, so I think
having the value_type and an allocator as template parameters is
better (as long as there's a check that the types agree).