Why does this allocator not work with `std::allocate_shared`? Bizarre template substitution errors

Question

Demo

foo_allocator is a working allocator for stl containers. It wraps over a base allocator type and forwards allocate(), deallocate(), operator==, operator!=, etc to the base.

#include <iostream>
#include <string>
#include <vector>
#include <memory>

template <typename T>
class bar_allocator : public std::allocator<T> {};

template <typename T, typename base=bar_allocator<T>>
class foo_allocator {
public:
    typedef typename std::allocator_traits<base>::value_type value_type;

    template <typename U, typename A> friend class foo_allocator;

    template<class U>
    struct rebind {
        typedef foo_allocator<U,
                typename std::allocator_traits<base>::template rebind_alloc<U>> other;
    };

    // Construct a dummy allocator from another dummy allocator with the same base_allocator but with different type.
    template <typename U>
    foo_allocator(
            const foo_allocator<U,
                    typename std::allocator_traits<base>::template rebind_alloc<U>>& other) noexcept :
            alloc(other.alloc) {}

    foo_allocator() = default;

    template<typename... Args>
    foo_allocator(Args &&... args) requires (std::is_constructible_v<base, Args...>) : alloc(std::forward<Args>(args)...) {}

    T* allocate(std::size_t n) {
        T* p = alloc.allocate(n);
        return p;
    }

    void deallocate(T* p, std::size_t size) noexcept {
        alloc.deallocate(p, size);
    }

private:
    base alloc;
};

template <typename T, typename U, typename base_allocator>
inline bool operator == (const foo_allocator<T, base_allocator>& a,
        const foo_allocator<U, typename std::allocator_traits<base_allocator>::template rebind_alloc<U>>& b)
{
    return a.alloc == b.alloc;
}

template <typename T, typename U, typename base_allocator>
inline bool operator != (const foo_allocator<T, base_allocator>& a,
        const foo_allocator<U, typename std::allocator_traits<base_allocator>::template rebind_alloc<U>>& b)
{
    return a.alloc != b.alloc;
}


int main()
{
    // Works fine
    std::vector<int, foo_allocator<int>> v;
    for (int i = 0; i < 100; i++)
        v.push_back(i);

    // Breaks!    
    // foo_allocator<int> foo;    
    // std::shared_ptr<int> ptr2 = std::allocate_shared<int>(foo);
}

However, it doesn't work with allocate_shared. If you try to allocate_shared with this allocator, you get a compiler error of the following:

In file included from /usr/local/include/c++/9.2.0/bits/shared_ptr.h:52,
                 from /usr/local/include/c++/9.2.0/memory:81,
                 from main.cpp:4:
/usr/local/include/c++/9.2.0/bits/shared_ptr_base.h: In instantiation of 'std::__shared_count<_Lp>::__shared_count(_Tp*&, std::_Sp_alloc_shared_tag<_Alloc>, _Args&& ...) [with _Tp = int; _Alloc = foo_allocator<int>; _Args = {}; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]':
/usr/local/include/c++/9.2.0/bits/shared_ptr_base.h:1344:71:   required from 'std::__shared_ptr<_Tp, _Lp>::__shared_ptr(std::_Sp_alloc_shared_tag<_Tp>, _Args&& ...) [with _Alloc = foo_allocator<int>; _Args = {}; _Tp = int; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic]'
/usr/local/include/c++/9.2.0/bits/shared_ptr.h:359:59:   required from 'std::shared_ptr<_Tp>::shared_ptr(std::_Sp_alloc_shared_tag<_Tp>, _Args&& ...) [with _Alloc = foo_allocator<int>; _Args = {}; _Tp = int]'
/usr/local/include/c++/9.2.0/bits/shared_ptr.h:701:14:   required from 'std::shared_ptr<_Tp> std::allocate_shared(const _Alloc&, _Args&& ...) [with _Tp = int; _Alloc = foo_allocator<int>; _Args = {}]'
main.cpp:71:62:   required from here
/usr/local/include/c++/9.2.0/bits/shared_ptr_base.h:676:43: error: no matching function for call to 'foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >::foo_allocator(const foo_allocator<int>&)'
  676 |    typename _Sp_cp_type::__allocator_type __a2(__a._M_a);
      |                                           ^~~~
main.cpp:32:5: note: candidate: 'foo_allocator<T, base>::foo_allocator(Args&& ...) requires  is_constructible_v<base, Args ...> [with Args = {const foo_allocator<int, bar_allocator<int> >&}; T = std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>; base = std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> >]'
   32 |     foo_allocator(Args &&... args) requires (std::is_constructible_v<base, Args...>) : alloc(std::forward<Args>(args)...) {}
      |     ^~~~~~~~~~~~~
main.cpp:32:5: note:   constraints not satisfied
main.cpp:32:5: note: 'is_constructible_v<base, Args ...>' evaluated to false
main.cpp:29:5: note: candidate: 'constexpr foo_allocator<T, base>::foo_allocator() [with T = std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>; base = std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> >]'
   29 |     foo_allocator() = default;
      |     ^~~~~~~~~~~~~
main.cpp:29:5: note:   candidate expects 0 arguments, 1 provided
main.cpp:24:5: note: candidate: 'template<class U> foo_allocator<T, base>::foo_allocator(const foo_allocator<U, typename std::allocator_traits<_Alloc>::rebind_alloc<U> >&)'
   24 |     foo_allocator(
      |     ^~~~~~~~~~~~~
main.cpp:24:5: note:   template argument deduction/substitution failed:
In file included from /usr/local/include/c++/9.2.0/bits/shared_ptr.h:52,
                 from /usr/local/include/c++/9.2.0/memory:81,
                 from main.cpp:4:
/usr/local/include/c++/9.2.0/bits/shared_ptr_base.h:676:43: note:   mismatched types 'std::allocator<_CharT>' and 'bar_allocator<int>'
  676 |    typename _Sp_cp_type::__allocator_type __a2(__a._M_a);
      |                                           ^~~~
main.cpp:10:7: note: candidate: 'constexpr foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >::foo_allocator(const foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >&)'
   10 | class foo_allocator {
      |       ^~~~~~~~~~~~~
main.cpp:10:7: note:   no known conversion for argument 1 from 'const foo_allocator<int>' to 'const foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >&'
main.cpp:10:7: note: candidate: 'constexpr foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >::foo_allocator(foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >&&)'
main.cpp:10:7: note:   no known conversion for argument 1 from 'const foo_allocator<int>' to 'foo_allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, std::allocator<std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic> > >&&'

What I can gather from the error messages

1. std::shared_ptr does some rebinding to create a struct that wraps over the int we're trying to allocate. In particular, it tries to allocate the type std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>, which I'm guessing has the int but also other fields used to make sure shared_ptrs are threadsafe.
2. As a result, we have this really ugly struct that does some self-referencing with foo_allocator:

foo_allocator<
    std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>,
    std::allocator<
        std::_Sp_counted_ptr_inplace<int, foo_allocator<int>, __gnu_cxx::_S_atomic>
    > 
>

But wait! Why is std::allocator<> here? We never specified std::allocator<> as our base allocator! It should've been bar_allocator!

1. Later down the error log, we see the following bizarre line:

mismatched types 'std::allocator<_CharT>' and 'bar_allocator<int>'

Other than the std::allocator<> showing up again, where did _CharT come from? doesn't this template type usually show up in strings?

Any help would be greatly appreciated. I've scratched my head about this for a while and couldn't come up with any reasonable fixes.

Answer 1

Thanks to @Nicol Bolas and @Igor Tandetnik, I was able to figure out the reason. As they said, by inheriting an allocator you also inherit the rebind struct which is actually rebinding for the base class. This isn't what we want (allocators I guess don't work well with inheritance), so we'd have to add the following to get this to work:

template <typename T>
class bar_allocator : public std::allocator<T> {
public:
    bar_allocator() = default;

    template <typename U>
    bar_allocator(const bar_allocator<U>& other) : std::allocator<T>(other){
    }

    template<class U>
    struct rebind {
        typedef bar_allocator<U> other;
    };
};

Demo