Background
I implemented the historic std::dynarray according to the specification under the name dynamic_array in C++17. dynamic_array doesn't attempt to get allocated on stack storage.
The most interesting part is the allocator support. Unlike other containers, dynamic_array does not take an allocator as a template parameter. But it supports construction from an arbitrary allocator, and it has to call the appropriate allocator on destruction. As such, the allocator has to be stored with the help of type erasure.
At first I thought of using std::any to hold the allocator. However, there is a problem: std::any does not have a visit functionality, we can't get the type of the allocator back, thus unable to call std::allocator_traits<A>::destroy.
As such, my approach is to use a std::function. A lambda is generated for each construction from an allocator, which captures the allocator by copy and calls the correct destroy function. Admittedly, this is one of the few times I find a meaningful usage for mutable lambdas.
Code
Here's the header dynamic_array.hpp:
// C++17 fixed-size dynamic array
#ifndef INC_DYNAMIC_ARRAY_HPP_akMQiHuI0M
#define INC_DYNAMIC_ARRAY_HPP_akMQiHuI0M
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <type_traits>
namespace LF_lib {
template <class T>
class dynamic_array {
public:
using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using reference = T&;
using const_reference = const T&;
using pointer = T*;
using const_pointer = const T*;
using iterator = T*;
using const_iterator = const T*;
using reverse_iterator = std::reverse_iterator<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
// default-initializes the elements
explicit dynamic_array(std::size_t n)
:dynamic_array{n, std::allocator<T>{}}
{
}
template <class A>
dynamic_array(std::size_t n, const A& a)
:count{n}
{
if (count == 0) {
register_empty_cleanup();
return;
}
A alloc = a;
elems = std::allocator_traits<A>::allocate(alloc, count);
T* p = begin();
try {
register_cleanup(alloc);
for (; p != end(); ++p)
std::allocator_traits<A>::construct(alloc, p);
} catch (...) {
for (T* q = begin(); q != p; ++q)
std::allocator_traits<A>::destroy(alloc, q);
std::allocator_traits<A>::deallocate(alloc, elems, count);
throw;
}
}
dynamic_array(std::size_t n, const T& value)
:dynamic_array{n, value, std::allocator<T>{}}
{
}
template <class A>
dynamic_array(std::size_t n, const T& value, const A& a)
:count{n}
{
if (count == 0) {
register_empty_cleanup();
return;
}
A alloc = a;
elems = std::allocator_traits<A>::allocate(alloc, count);
T* p = begin();
try {
register_cleanup(alloc);
for (; p != end(); ++p)
std::allocator_traits<A>::construct(alloc, p, value);
} catch (...) {
for (T* q = begin(); q != p; ++q)
std::allocator_traits<A>::destroy(alloc, q);
std::allocator_traits<A>::deallocate(alloc, elems, count);
throw;
}
}
dynamic_array(const dynamic_array& other)
:dynamic_array{other, std::allocator<T>{}}
{
}
template <class A>
dynamic_array(const dynamic_array& other, const A& a)
:count{other.size()}
{
if (count == 0) {
register_empty_cleanup();
return;
}
A alloc = a;
elems = std::allocator_traits<A>::allocate(alloc, count);
T* p = begin();
try {
register_cleanup(alloc);
for (const T* q = other.cbegin(); p != cend(); ++p, ++q)
std::allocator_traits<A>::construct(alloc, p, *q);
} catch (...) {
for (T* q = begin(); q != p; ++q)
std::allocator_traits<A>::destroy(alloc, q);
std::allocator_traits<A>::deallocate(alloc, elems, count);
throw;
}
}
dynamic_array(std::initializer_list<T> init)
:dynamic_array{init, std::allocator<T>{}}
{
}
template <class A>
dynamic_array(std::initializer_list<T> init, const A& a)
:count{init.size()}
{
if (count == 0) {
register_empty_cleanup();
return;
}
A alloc = a;
elems = std::allocator_traits<A>::allocate(alloc, count);
T* p = begin();
try {
register_cleanup(alloc);
for (const T* q = init.begin(); p != end(); ++p, ++q)
std::allocator_traits<A>::construct(alloc, p, *q);
} catch (...) {
for (T* q = begin(); q != p; ++q)
std::allocator_traits<A>::destroy(alloc, q);
std::allocator_traits<A>::deallocate(alloc, elems, count);
throw;
}
}
~dynamic_array()
{
cleanup(elems, count);
}
dynamic_array& operator=(const dynamic_array&) = delete;
dynamic_array& operator=(dynamic_array&&) = delete;
T& at(std::size_t index) { check(index); return elems[index]; }
const T& at(std::size_t index) const { check(index); return elems[index]; }
T& operator[](std::size_t index) { return elems[index]; }
const T& operator[](std::size_t index) const { return elems[index]; }
T& front() { return elems[0]; }
const T& front() const { return elems[0]; }
T& back() { return elems[count - 1]; }
const T& back() const { return elems[count - 1]; }
T* data() noexcept { return elems; }
const T* data() const noexcept { return elems; }
iterator begin() noexcept { return elems; }
const_iterator begin() const noexcept { return elems; }
const_iterator cbegin() const noexcept { return begin(); }
iterator end() noexcept { return elems + count; }
const_iterator end() const noexcept { return elems + count; }
const_iterator cend() const noexcept { return end(); }
reverse_iterator rbegin() noexcept { return end(); }
const_reverse_iterator rbegin() const noexcept { return end(); }
const_reverse_iterator crbegin() const noexcept { return rbegin(); }
reverse_iterator rend() noexcept { return begin(); }
const_reverse_iterator rend() const noexcept { return begin(); }
const_reverse_iterator crend() const noexcept { return rend(); }
bool empty() const noexcept { return size != 0; }
std::size_t size() const noexcept { return count; }
std::size_t max_size() const noexcept
{
return SIZE_MAX / sizeof(T);
}
void fill(const T& value)
{
std::fill(begin(), end(), value);
}
private:
T* elems = nullptr;
std::size_t count;
std::function<void(T*, std::size_t)> cleanup;
void register_empty_cleanup()
{
cleanup = [](T*, std::size_t) {};
}
template <class A>
void register_cleanup(A& alloc)
{
cleanup = [alloc](T* elems, std::size_t count) mutable {
T* it = elems;
for (std::size_t i = 0; i < count; ++i)
std::allocator_traits<A>::destroy(alloc, it++);
std::allocator_traits<A>::deallocate(alloc, elems, count);
};
}
void check(std::size_t index) const
{
if (index >= count)
throw std::out_of_range{"LF_lib::dynamic_array out of range"};
}
};
template <class T>
bool operator==(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs)
{
return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}
template <class T>
bool operator!=(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs)
{
return !(lhs == rhs);
}
template <class T>
bool operator< (const dynamic_array<T>& lhs, const dynamic_array<T>& rhs)
{
return std::lexicographical_compare(lhs.begin(), lhs.end(),
rhs.begin(), rhs.end());
}
template <class T>
bool operator<=(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs)
{
return !(rhs < lhs);
}
template <class T>
bool operator> (const dynamic_array<T>& lhs, const dynamic_array<T>& rhs)
{
return rhs < lhs;
}
template <class T>
bool operator>=(const dynamic_array<T>& lhs, const dynamic_array<T>& rhs)
{
return !(lhs < rhs);
}
}
namespace std {
template <class T, class A>
struct uses_allocator<LF_lib::dynamic_array<T>, A>
:std::true_type { };
}
#endif
And here's an example on its usage, showing how the allocators work under the hood:
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <type_traits>
#include "dynamic_array.hpp"
using LF_lib::dynamic_array;
template <typename T>
class Tracing_alloc :private std::allocator<T> {
using Base = std::allocator<T>;
public:
using value_type = T;
T* allocate(std::size_t n)
{
std::cerr << "allocate(" << n << ")\n";
return Base::allocate(n);
}
void deallocate(T* ptr, std::size_t n)
{
std::cerr << "deallocate(" << static_cast<void*>(ptr) << ", "
<< n << ")\n";
Base::deallocate(ptr, n);
}
template <typename... Args>
void construct(T* ptr, Args&&... args)
{
std::cerr << "construct(" << ptr << ", args...)\n";
std::allocator_traits<Base>::construct(*this, ptr, args...);
}
void destroy(T* ptr)
{
std::cerr << "destroy(" << ptr << ")\n";
std::allocator_traits<Base>::destroy(*this, ptr);
}
};
template <typename T>
bool operator==(const Tracing_alloc<T>&, const Tracing_alloc<T>&)
{
return true;
}
template <typename T>
bool operator!=(const Tracing_alloc<T>&, const Tracing_alloc<T>&)
{
return false;
}
class Construct_throw {
public:
Construct_throw()
{
static int i = 0;
if (i++ > 3)
throw std::exception{};
}
};
void test(std::size_t n)
{
dynamic_array<std::string> arr{n, Tracing_alloc<std::string>{}};
for (auto& x : arr)
x = "a";
std::inclusive_scan(arr.begin(), arr.end(), arr.begin(), std::plus<>{});
for (const auto& x : arr)
std::cout << std::quoted(x) << " ";
std::cout << "\n";
dynamic_array<std::string> arr2{arr, Tracing_alloc<std::string>{}};
for (const auto& x : arr2)
std::cout << std::quoted(x) << " ";
std::cout << "\n";
dynamic_array<std::string> arr3{{"foo", "bar", "baz"},
Tracing_alloc<std::string>{}};
for (const auto& x : arr3)
std::cout << std::quoted(x) << " ";
std::cout << "\n";
dynamic_array<Construct_throw> arr4{n, Tracing_alloc<Construct_throw>{}};
}
int main()
try {
test(0);
test(10);
} catch (...) {
return 1;
}
Here's the output I got: (the initial empty lines are intentional)
allocate(3) construct(000001CE3ADE8F60, args...) construct(000001CE3ADE8F80, args...) construct(000001CE3ADE8FA0, args...) "foo" "bar" "baz" destroy(000001CE3ADE8F60) destroy(000001CE3ADE8F80) destroy(000001CE3ADE8FA0) deallocate(000001CE3ADE8F60, 3) allocate(10) construct(000001CE3ADEC130, args...) construct(000001CE3ADEC150, args...) construct(000001CE3ADEC170, args...) construct(000001CE3ADEC190, args...) construct(000001CE3ADEC1B0, args...) construct(000001CE3ADEC1D0, args...) construct(000001CE3ADEC1F0, args...) construct(000001CE3ADEC210, args...) construct(000001CE3ADEC230, args...) construct(000001CE3ADEC250, args...) "a" "aa" "aaa" "aaaa" "aaaaa" "aaaaaa" "aaaaaaa" "aaaaaaaa" "aaaaaaaaa" "aaaaaaaaaa" allocate(10) construct(000001CE3ADEDED0, args...) construct(000001CE3ADEDEF0, args...) construct(000001CE3ADEDF10, args...) construct(000001CE3ADEDF30, args...) construct(000001CE3ADEDF50, args...) construct(000001CE3ADEDF70, args...) construct(000001CE3ADEDF90, args...) construct(000001CE3ADEDFB0, args...) construct(000001CE3ADEDFD0, args...) construct(000001CE3ADEDFF0, args...) "a" "aa" "aaa" "aaaa" "aaaaa" "aaaaaa" "aaaaaaa" "aaaaaaaa" "aaaaaaaaa" "aaaaaaaaaa" allocate(3) construct(000001CE3ADE8F60, args...) construct(000001CE3ADE8F80, args...) construct(000001CE3ADE8FA0, args...) "foo" "bar" "baz" allocate(10) construct(000001CE3ADE8CC0, args...) construct(000001CE3ADE8CC1, args...) construct(000001CE3ADE8CC2, args...) construct(000001CE3ADE8CC3, args...) construct(000001CE3ADE8CC4, args...) destroy(000001CE3ADE8CC0) destroy(000001CE3ADE8CC1) destroy(000001CE3ADE8CC2) destroy(000001CE3ADE8CC3) deallocate(000001CE3ADE8CC0, 10) destroy(000001CE3ADE8F60) destroy(000001CE3ADE8F80) destroy(000001CE3ADE8FA0) deallocate(000001CE3ADE8F60, 3) destroy(000001CE3ADEDED0) destroy(000001CE3ADEDEF0) destroy(000001CE3ADEDF10) destroy(000001CE3ADEDF30) destroy(000001CE3ADEDF50) destroy(000001CE3ADEDF70) destroy(000001CE3ADEDF90) destroy(000001CE3ADEDFB0) destroy(000001CE3ADEDFD0) destroy(000001CE3ADEDFF0) deallocate(000001CE3ADEDED0, 10) destroy(000001CE3ADEC130) destroy(000001CE3ADEC150) destroy(000001CE3ADEC170) destroy(000001CE3ADEC190) destroy(000001CE3ADEC1B0) destroy(000001CE3ADEC1D0) destroy(000001CE3ADEC1F0) destroy(000001CE3ADEC210) destroy(000001CE3ADEC230) destroy(000001CE3ADEC250) deallocate(000001CE3ADEC130, 10)
Of course, you may get completely different addresses.
