How to Enable a Custom Container for the Scoped Allocator Model

Question

This is a long post, so I would like to write the sole question at the top:

It seems I need to implement "allocator-extended" constructors for a custom container that itself doesn't use an allocator, but propagates this to its internal implementation which is a variant type and whose allowed types may be a container like a std::map, but also a type which doesn't need an allocator, say a boolean.

Alone, I have no idea how to accomplish this.

Help is greatly appreciated! ;)

The "custom container" is a class template value which is an implementation of a representation of a JSON data structure.

Class template value is a thin wrapper around a discriminated union: class template variant (similar like boost variant). The allowed types of this variant represent the JSON types Object, Array, String, Number Boolean and Null.

Class template value has a variadic template template parameter pack Policies which basically defines how the JSON types are implemented. Per default the JSON types are implemented with std::map (for Object), std::vector (for Array), std::string (for JSON data string) and a few custom classes representing the remaining JSON types.

A type-machinery defined in value is used to create the recursive type definitions for the container types in terms of the given Policies and also value itself. (The variant class does not need to use a "recursive wrapper" for the implementation of the JSON containers when it uses std::map or std::vector for example). That is, this type machinery creates the actual types used to represent the JSON types, e.g. a std::vector for Array whose value_type equals value and a std::map for Object whose mapped_type equals value. (Yes, value is actually incomplete at this moment when the types are generated).

The class template value basically looks as this (greatly simplified):

template <template <typename, typename> class... Policies>
class value
{
    typedef json::Null                          null_type;
    typedef json::Boolean                       boolean_type;
    typedef typename <typegenerator>::type      float_number_type;
    typedef typename <typegenerator>::type      integral_number_type;
    typedef typename <typegenerator>::type      string_type;
    typedef typename <typegenerator>::type      object_type;
    typedef typename <typegenerator>::type      array_type;


    typedef variant<
        null_type
      , boolean_type
      , float_number_type
      , integral_number_type
      , string_type
      , object_type
      , array_type
    > variant_type;

public:

    ...

private:
    variant_type value_;
};

value implements the usual suspects, e.g. constructors, assignments, accessors, comparators, etc. It also implements forwarding constructors so that a certain implementation type of the variant can be constructed with an argument list.

The typegenerator will basically find the relevant implementation policy and use it unless it doesn't find one, then it uses a default implementation policy (this is not shown in detail here, but please ask if something should be unclear).

For example array_type becomes: std::vector<value, std::allocator<value>> and object_type becomes
std::map<std::string, value, std::less<std::string>, std::allocator<std::pair<const std::string, value>>>

So far, this works as intended.

Now, the idea is to enable the user to specify a custom allocator which is used for all allocations and all constructions within the "container", that is value. For example, an arena-allocator.

For that purpose, I've extended the template parameters of value as follows:

template <
    typename A = std::allocator<void>,
    template <typename, typename> class... Policies
>
class value ...

And also adapted the type machinery in order to use a scoped_allocator_adaptor when appropriate.

Note that template parameter A is not the allocator_type of value - but instead is just used in the type-machinery in order to generate the proper implementation types. That is, there is no embedded allocator_type in value - but it affects the allocator_type of the implementation types.

Now, when using a state-ful custom allocator, this works only half-way. More precisely, it works -- except propagation of the scoped allocator will not happen correctly. E.g.:

Suppose, there is a state-ful custom-allocator with a property id, an integer. It cannot be default-constructed.

    typedef test::custom_allocator<void> allocator_t;
    typedef json::value<allocator_t> Value;
    typedef typename Value::string_type String;
    typedef Value::array_type  Array;

    allocator_t a1(1);
    allocator_t a2(2);

    // Create an Array using allocator a1:
    Array array1(a1);
    EXPECT_EQ(a1, array1.get_allocator());

    // Create a value whose impl-type is a String which uses allocator a2:
    Value v1("abc",a2);

    // Insert via copy-ctor:
    array1.push_back(v1);

    // We expect, array1 used allocator a1 in order to construct internal copy of value v1 (containing a string):
    EXPECT_EQ(a1, array1.back().get<String>().get_allocator());
  --> FAILS !!

The reasons seems, that the array1 will not propagate it's allocator member (which is a1) through the copy of value v1 to its current imp type, the actual copy of string.

Maybe this can be achieved through "allocator-extended" constructors in value, albeit, it itself does not use allocators - but instead needs to "propagate" them appropriately when needed.

But how can I accomplish this?

Edit: revealing part of the type generation:

A "Policy" is a template template parameter whose first param is the value_type (in this case value), and the second param is an allocator type. The "Policy" defines how a JSON type (e.g. an Array) shall be implemented in terms of the value type and the allocator type.

For example, for a JSON Array:

template <typename Value, typename Allocator>
struct default_array_policy : array_tag
{
private:
    typedef Value value_type;
    typedef typename Allocator::template rebind<value_type>::other value_type_allocator;
    typedef GetScopedAllocator<value_type_allocator> allocator_type;
public:
    typedef std::vector<value_type, allocator_type> type;
};

where GetScopedAllocator is defined as:

template <typename Allocator>
using GetScopedAllocator = typename std::conditional<
    std::is_empty<Allocator>::value,
    Allocator,
    std::scoped_allocator_adaptor<Allocator>
>::type;

Answer 1

The logic for deciding whether to pass an allocator to child elements is called uses-allocator construction in the standard, see 20.6.7 [allocator.uses].

There are two standard components which use the uses-allocator protocol: std::tuple and std::scoped_allocator_adaptor, and you can also write user-defined allocators that also it (but it's often easier to just use scoped_allocator_adaptor to add support for the protocol to existing allocators.)

If you're using scoped_allocator_adaptor internally in value then all you should need to do to get scoped allocators to work is ensure value supports uses-allocator construction, which is specified by the std::uses_allocator<value, Alloc> trait. That trait will be automatically true if value::allocator_type is defined and std::is_convertible<value::allocator_type, Alloc> is true. If value::allocator_type doesn't exist you can specialize the trait to be true (this is what std::promise and std::packaged_task do):

namespace std
{
  template<typename A, typename... P, typename A2>
    struct uses_allocator<value<A, P...>, A2>
    : is_convertible<A, A2>
    { };
}

This will mean that when a value is constructed by a type that supports uses-allocator construction it will attempt to pass the allocator to the value constructor, so you do also need to add allocator-extended constructors so it can be passed.

For this to work as you want:

// Insert via copy-ctor:
array1.push_back(v1);

the custom_allocator template must support uses-allocator construction, or you must have wrapped it so that Value::array_type::allocator_type is scoped_allocator_adaptor<custom_allocator<Value>>, I can't tell from your question if that's true or not.

Of course for this to work the standard library implementation has to support scoped allocators, what compiler are you using? I'm only familiar with GCC's status in this area, where GCC 4.7 supports it for std::vector only. For GCC 4.8 I've added support to forward_list too. I hope the remaining containers will all be done for GCC 4.9.

N.B. Your types should also use std::allocator_traits for all allocator-related operations, instead of calling member functions on the allocator type directly.

Yes, value is actually incomplete at this moment when the types are generated

It is undefined behaviour to use incomplete types as template arguments when instantiating standard template components unless speficied otherwise, see 17.6.4.8 [res.on.functions]. It might work with your implementation, but isn't required to.