Allocator for type that allocates itself

Question

So I got this recursive variant that holds the types std::vector and std::unordered_map which again hold the type itself.

Now this should work according to the standard because:

1. std::unordered_map is basically a smart pointer holding only references and at the point of definition it will not need to know the size of the types.
2. self referential std::vectors were accepted into the standard as of N4510 as mentioned in this other topic.

Here's what I have:

Demo

#include <variant>
#include <unordered_map>
#include <vector>
#include <string>
#include <memory> /* allocator */

template <typename StringType, typename Allocator>
class JSON;

template <typename StringType = std::string, typename Allocator = std::allocator</* map and vector */>>
class JSON : public std::variant<std::monostate,
                        std::unordered_map<StringType, JSON<StringType, Allocator>, std::hash<JSON<StringType, Allocator>>, std::equal_to<StringType>, Allocator>,
                        std::vector<JSON<StringType, Allocator>, Allocator>>
{ };

The problem is indeed not the self-similarity of this class object, but its allocator. It would work if the allocator satisfies the allocator-completeness-requirements:

An incomplete type T may be used when instantiating vector if the allocator satisfies the allocator-completeness-requirements (17.6.3.5.1). T shall be complete before any member of the resulting specialization of vector is referenced.

But I can't fulfill those as the type is not incomplete BUT a template template!

template <typename StringType = std::string,
    typename Allocator = std::allocator<JSON<StringType,
                            std::allocator<JSON<StringType,
                                std::allocator<JSON<StringType,
                                    ... >>>>>>>

Meaning, I can't really describe the type. What am I to do in this situation? Could I maybe help myself out with a custom allocator?

Simplified:

This works:

struct A {
    std::vector<A> subAs;
};

This doesn't:

template <typename Allocator>
struct A;

template <typename Allocator = std::allocator<A /* <-- unfortunately a template template parameter */>>
struct A {
    std::vector<A<Allocator>, Allocator> subAs;
};

But I wonder since the allocator is implicit in the first example, making it explicit should also work imho?

Answer 1

std::unordered_map's allocator doesn't actually allocate memory for unordered_map::value_type elements, but for an internal node structure. This is done by rebinding the allocator.

You can do similarly by accepting any allocator (here, void is used as a dummy) then rebinding it:

template <typename Allocator = std::allocator<void>>
struct A {
private:
    using alloc_traits = typename std::allocator_traits<Allocator>::template rebind_traits<super_vector<Allocator>>;
    using allocator = typename alloc_traits::allocator_type;
public:
    std::vector<A<Allocator>, allocator> vec_;
};

That way you need an allocator for A<std::allocator<void>>, which is std::allocator<A<std::allocator<void>>> with no "cycle".

Applied to your JSON struct:

template <typename StringType = std::string, typename Allocator = std::allocator<void>>
class JSON : public std::variant<std::monostate,
    std::unordered_map<StringType, JSON<StringType, Allocator>, std::hash<JSON<StringType, Allocator>>, std::equal_to<StringType>, typename std::allocator_traits<Allocator>::template rebind_alloc<std::pair<const StringType, JSON<StringType, Allocator>>>>,
    std::vector<JSON<StringType, Allocator>, typename std::allocator_traits<Allocator>::template rebind_alloc<JSON<StringType, Allocator>>>>
{ };

But note that std::unordered_map does needs to have a complete type as its mapped type when you instantiate the class. See here: How to have an unordered_map where the value type is the class it's in?. You will need to do something else (I believe boost's unordered_map supports incomplete types, and boost's recursive_variant does something to allow it to be used as a mapped type of a regular unordered_map)