Re: Yet Another Container: DynamicArray

From: Christian Mazakas (christian.mazakas_at_[hidden])
Date: 2020-01-24 01:59:12

> dynamic_array has run-time size, has semantics of std::array, contains
> pointer to dynamically allocated on the heap buffer of elements and
> therefore has O(1) move.

Yup! A static_vector would be an entirely different beast. That would be a
container with size modifiers which dynamic_array explicitly avoids.

> Wrong. The D in the unique_ptr<T, D> returned by allocate_unique()
> only stores the Allocator.
> The size for allocate_unique<T[]>()  is stored in D::pointer. i.e.
> D::pointer is a pointer-like type (detail::alloc_ptr) that stores
> A::pointer and size.

I apologize and thank you for the correction!

> Which means for arrays of sizes known at compile-time,:
> * dynamic_array<T, A> x(a, N); will store that extra size
> * auto x = allocate_unique<T[N]>(a); will not

Entirely accurate. This is due to the interface that dynamic_array attempted
to emulate which was std::vector and std::array. I'm not sure of a clean
way of
folding in this kind of storage optimization or what the general interface
would look like.

People naturally type out std::vector<int> so dynamic_array attempts to look
similarly. We could maybe try something like adding a non-type template
parameter representing the Extent where -1 is "dynamic" and the size must be
stored and all positive values have the optimization applied.

I'd love to explore this problem space and see if we can get some solutions
in
this regard.

> In addition to that, boost::allocate_unique() gives you almost
> everything else dynamic_array gives you:
> * Allocator aware
> * Supports construction from a value
> * Supports default-initialization (noinit)
> * Supports arrays of arrays

Sounds to me like dynamic_array learned from the best and took a few notes!

> > And while it is true that `boost::allocate_unique` enables all of this,
it still
> > lacks a few key semantics. Namely, `dynamic_array` is copyable. It's
also
> > copy assignable and move assignable,
>
> Yes, this is the only difference. The question is if anyone needs
> this.  i.e. When they reach for something lighter than vector<T, A> do
> they also want that type to be deep copyable/movable.

They would indeed! This is because dynamic_array aims to be a Container. In
these kinds of scenarios, if a user is reaching for a Container over a raw
array it's usually because they want the semantics of swap, reverse
iterators,
copyability, etc.

In many ways, dynamic_array is a natural extension of the classes already
provided to users today.

> But if they just want to 'copy or move elements from the result of
> allocate_unique() that's also not difficult.

Copying is straight-forward but is oftentimes annoying and cumbersome,
especially when compared to something as simple as x = y;.

Moving is trickier because of allocators not comparing equal.

In essence, if one uses allocate_unique with unequal allocators, they cannot
simply move the one pointer into the other one if they also wish to use the
original allocator. This is because non-equal Allocators can't deallocate
allocations made by the other.

This is actually a common case when using std::pmr::polymorphic_allocator
where
it's very likely that two allocator instances will not compare equal.

dynamic_array handles Allocators for users whereas allocate_unique does not,
nor should it aim to. That's what all the constexpr if is for in the
implementation of the class.

- Chris