Implementation for std::make_contiguous_objects proposal

This proposal intends to add support to allocate adjacent objects of different types.

If you want to create a char next to an int, next to a long, you can do:

struct Struct { char c; int i; long l; };
auto* s = new Struct;

However, if you want to allocate an arbitrary number of chars next to several ints, next to multiple longs, there is no easy way to do so. In practice, developers will resort to splitting up the layout:

struct Struct { std::vector<char> cs; std::vector<int> is; std::vector<long> ls; };
auto* s = new Struct{numC, numI, numL};

Or, if performance is a requirement, developers will write by hand the code to allocate a blob of memory and place each object in the desired place.

With this proposal, it would be possible to write:

tuple<span<char>, span<int>, span<long>> s =
    std::make_contiguous_objects<char, int, long>(numC, numI, numL);

Data structures that optimize for performance often use "contiguous objects" as a way to avoid multiple allocations and improve the memory locality.

One of the simplest examples is std::make_shared<T[]> which creates a std::shared_ptr<T[]> where the control block is adjacent to the T array. This simple operation involves a large amount of non-trivial code to:

1. Calculate the exact amount of memory to allocate to hold the control block and Ts
2. Find the correctly-aligned memory addresses where the control block and Ts will live
3. Construct them while being aware that should exception be thrown, all objects must be destroyed in the reverse order of construction.

If a developer attempts to write such code for the first time, it will be either a multi-day task or many details will be overlooked. Generally, even experienced developers will avoid going into this realm due to the complexity of writing and maintaining this code.

For more details, see the libc++ implementation

Containers often need to store metadata adjacent to a group of elements.

• Abseil flat_hash_set
• std::hive

• LLVM User class
• C Flexible Array Members
• new T[] for non trivially destructible types, in some compilers, also store the size of the array together with the data.

template<class... Args, class... Initializers>
auto make_contiguous_objects(Initializers... args) -> std::tuple<std::span<Args>...>

template<class Alloc, class... Args, class... Initializers>
auto make_contiguous_objects(Alloc&, Initializers... args) -> std::tuple<std::span<Args>...>

(1) Construct arrays of objects adjacent to each other in a single allocation.

(2) Same as (1) but using the allocator to allocate the storage and construct each object.

Initializers can be:

1. size_t The number of elements in the array of that type
2. std::arg(std::uninit_t, size_t count) Number of elements to be left uninitialized if trivially destructible. Note: In this case, the allocator won't be invoked.
3. std::arg(std::ctor_t, size_t count, Args...) Number of elements and initialization parameters.
4. std::arg(std::aggregate_t, size_t count, Args...) Number of elements and initialization parameters for aggregate init {}.
5. std::arg(std::input_iterator_t, size_t count, InputIterator) Number of elements and an input iterator to provide values for the array
6. std::arg(std::functor_t, size_t, Functor) Number of elements and a functor to provide values for the array

See an example of each being used

The return type is a tuple of std::span<T> pointing to each array.

template<class... Args>
void destroy_contiguous_objects(const std::tuple<span<Args>...>&);
template<class Alloc, class... Args>
void destroy_contiguous_objects(Alloc&, const std::tuple<span<Args>...>&);

(1) Call the destructor on all elements of all spans in the tuple in reverse order.

(2) Same as (1) but use the allocator to destroy objects and deallocate the storage

template<class T, class U>
auto get_adjacent_address(U* u) -> T*;

Returns a pointer to T that is the next position after u that is suitable to hold such object. (Perhaps could be called realign_cast. I did not chose that option because I don't think the user should have to know about alignment to write code.)

It's guaranteed that get_adjacent_address of the end of a span returned by make_contiguous_objects match the begin of the next span.

Simplification of libc++ machinery for std::shared_ptr<T[]>

Simple shared ptr initial implementation

This API returns a tuple of spans and the caller is responsible for calling std::destroy_contiguous_objects passing that same tuple to destroy all objects and release the storage. It's obvious there is an opportunity for returning an object that manages the lifetime of the whole structure.

The current paper does not propose that because:

1. It can easily be built on top of the raw API
2. The author does not expect users of the API to store the whole result very frequently.

In most use-cases, the return value (tuple<span<Args>...>) will contain redundant information. For example, in a case where the arrays have the same size:

auto t = std::make_contiguous_objects<Metadata, Element>(numElements, numElements);

Users will generally store only the first pointer and derive the other arrays from that and numElements. See the application of this library on libc++ shared_ptr<T[]> in the section "Applying the proposed API in real code".

The main reason for this distinction (as far as I can tell) in shared_ptr API is the lack of a type dispatching mechanism to choose which constructor to use. So make_shared<T> allows passing multiple arguments that will be used for the construction of T inplace. make_shared<T[]> allows either passing nothing (new T()) or a single argument (new T(arg)). And finally make_shared_for_overwrite<T[]> gives the new T constructor, that leaves trivial types uninitialized.

This proposal intends to use the std::arg mechanism with type dispatching to choose any of those options, and others like input iterator constructor.

It's something we don't have in any other function in the standard and can be a very "open" API. Might bring a lot of controversy. Other options are:

1. Chaining 1:

auto r = std::make_contiguous_objects<string, int, float>()
    .arg(std::ctor, 15, a, b,c)
    .arg(std::input_iterator, 10, it)
    .arg(std::uninit, 12);

2. Chaining 2:

auto r = std::make_contiguous_objects()
    .arg<string>(std::ctor, 15, a, b,c)
    .arg<int>(std::input_iterator, 10, it)
    .arg<float>(std::uninit, 12);

3. Limiting to always call the default constructor: std::make_contiguous_objects<int, float>(10, 20);

Either 1 or 2 should be viable options, while 3 could be too limited.

• std::make_objects
• std::new_objects
• std::allocate_objects
• All of the above with adjacent_objects instead of objects
• All of the above with arrays instead of objects