A fixed-size dynamic array

Question

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.

Answer 1

Note: although the question is tagged C++17, I'm going to use some C++20 or later features in my review, as this simplifies the code. Many of my suggestions can be written in C++17, but at the expense of clarity.

---

I get some compilation warnings:

g++-14 -std=c++23 -fPIC -gdwarf-4 -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wmissing-braces -Wconversion -Wuseless-cast -Weffc++ 221719.cpp -o 221719 221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(std::size_t, const A&) [with A = Tracing_alloc<std::__cxx11::basic_string<char> >; T = std::__cxx11::basic_string<char>; std::size_t = long unsigned int]’: 221719.cpp:349:65: required from here 349 | dynamic_array<std::string> arr{n, Tracing_alloc<std::string>{}}; | ^ 221719.cpp:41:5: warning: ‘LF_lib::dynamic_array<std::__cxx11::basic_string<char> >::cleanup’ should be initialized in the member initialization list [-Weffc++] 41 | dynamic_array(std::size_t n, const A& a) | ^~~~~~~~~~~~~ 221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(const LF_lib::dynamic_array<T>&, const A&) [with A = Tracing_alloc<std::__cxx11::basic_string<char> >; T = std::__cxx11::basic_string<char>]’: 221719.cpp:357:68: required from here 221719.cpp:41:5: warning: 357 | dynamic_array<std::string> arr2{arr, Tracing_alloc<std::string>{}}; 221719.cpp:41:5: warning: | ^ 221719.cpp:99:5: warning: ‘LF_lib::dynamic_array<std::__cxx11::basic_string<char> >::cleanup’ should be initialized in the member initialization list [-Weffc++] 99 | dynamic_array(const dynamic_array& other, const A& a) | ^~~~~~~~~~~~~ 221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(std::initializer_list<_Tp>, const A&) [with A = Tracing_alloc<std::__cxx11::basic_string<char> >; T = std::__cxx11::basic_string<char>]’: 221719.cpp:363:35: required from here 221719.cpp:99:5: warning: 363 | Tracing_alloc<std::string>{}}; 221719.cpp:99:5: warning: | ^ 221719.cpp:128:5: warning: ‘LF_lib::dynamic_array<std::__cxx11::basic_string<char> >::cleanup’ should be initialized in the member initialization list [-Weffc++] 128 | dynamic_array(std::initializer_list<T> init, const A& a) | ^~~~~~~~~~~~~ 221719.cpp: In instantiation of ‘LF_lib::dynamic_array<T>::dynamic_array(std::size_t, const A&) [with A = Tracing_alloc<Construct_throw>; T = Construct_throw; std::size_t = long unsigned int]’: 221719.cpp:368:74: required from here 221719.cpp:128:5: warning: 368 | dynamic_array<Construct_throw> arr4{n, Tracing_alloc<Construct_throw>{}}; 221719.cpp:128:5: warning: | ^ 221719.cpp:41:5: warning: ‘LF_lib::dynamic_array<Construct_throw>::cleanup’ should be initialized in the member initialization list [-Weffc++] 41 | dynamic_array(std::size_t n, const A& a) | ^~~~~~~~~~~~~ 

These are easily suppressed with std::function<⋯> cleanup = {};, making the default-initialisation explicit.

---

The test program is Valgrind-clean, but does exit with failure status:

==1410317== HEAP SUMMARY: ==1410317== in use at exit: 0 bytes in 0 blocks ==1410317== total heap usage: 13 allocs, 13 frees, 75,735 bytes allocated ==1410317== ==1410317== All heap blocks were freed -- no leaks are possible ==1410317== ==1410317== For lists of detected and suppressed errors, rerun with: -s ==1410317== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) make[1]: *** [Makefile:74: 221719.run] Error 1 

Adding a bit of diagnostic, we see that this is due to catching the exception from Construct_throw(), and it seems that the test program should expect this, and simply has its return statuses the wrong way around (i.e. the test should fail if we don't get the exception):

 Construct_throw() { static int i = 0; if (i++ > 3) throw std::runtime_error("Construct_throw"); } 

#include <cstdlib> #include <stdexcept> int main() try { test(0); test(10); return EXIT_FAILURE; } catch (const std::exception& e) { std::cerr << e.what() << '\n'; return EXIT_SUCCESS; } 

---

The first two constructors can easily be combined into a single one by defaulting the allocator. And since we just copy it to alloc, we can accept it by value:

 template <class A = std::allocator<T>> explicit dynamic_array(std::size_t n, A alloc = {}) 

Similarly:

 template <class A = std::allocator<T>> dynamic_array(std::size_t n, const T& value, A alloc = {}) 

and

 template <class A = std::allocator<T>> dynamic_array(std::initializer_list<T> init, A alloc a = {}) 

But not

 template <class A = std::allocator<T>> dynamic_array(const dynamic_array& other, A alloc = {}) 

because this is no longer a copy constructor.

---

When constructing contents throws an exception, I think we're supposed to destroy in reverse order of construction:

 } catch (...) { while (p-- != begin()) std::allocator_traits<A>::destroy(alloc, p); std::allocator_traits<A>::deallocate(alloc, elems, count); throw; 

A similar change is required in register_cleanup():

 cleanup = [alloc](T* elems, std::size_t count) mutable { T* it = elems + count; while (it-- > elems) std::allocator_traits<A>::destroy(alloc, it); std::allocator_traits<A>::deallocate(alloc, elems, count); }; 

As far as I can make out, there's nothing to stop allocator traits' destroy() or deallocate() from throwing, so perhaps we ought to handle any exceptions, especially in register_cleanup()'s stored function which is called from within noexcept context (specifically, in a destructor).

---

Also in register_cleanup(), we could eliminate the need to store the allocator in the common case of a stateless allocator. If the traits tells us that all instances are equivalent, we may be able to create a new one for cleanup rather than capturing this one:

 using traits = std::allocator_traits<A>; if constexpr (traits::is_always_equal::value && std::is_default_constructible_v<A>) { cleanup = [](T* elems, std::size_t count) { A alloc; for (T* it = elems + count; it-- > elems; ) traits::destroy(alloc, it); traits::deallocate(alloc, elems, count); }; } else { cleanup = [alloc](T* elems, std::size_t count) { for (T* it = elems + count; it-- > elems; ) traits::destroy(alloc, it); traits::deallocate(alloc, elems, count); }; } 

---

There's a lot of commonality among the different constructors. I think we can refactor that out into a private utility method.

 // allocate and populate content (for constructors) template<class A> void copy_content(std::ranges::input_range auto&& other, A alloc) { if (count == 0) { register_empty_cleanup(); return; } using traits = std::allocator_traits<A>; elems = traits::allocate(alloc, count); T* p = begin(); try { for (auto q = other.begin(); p != end(); ++p, ++q) traits::construct(alloc, p, *q); } catch (...) { while (p-- != begin()) traits::destroy(alloc, p); traits::deallocate(alloc, elems, count); throw; } } 

We can then use that for most of the constructors:

 template <class A = std::allocator<T>> dynamic_array(std::size_t n, const T& value, A alloc = {}) :count{n} { copy_content(std::views::repeat(value), alloc); } dynamic_array(const dynamic_array& other) :dynamic_array{other, std::allocator<T>{}} { } template <class A = std::allocator<T>> dynamic_array(const dynamic_array& other, A alloc) :count{other.size()} { copy_content(other, alloc); } template <class A = std::allocator<T>> dynamic_array(std::initializer_list<T> init, A alloc = {}) :count{init.size()} { copy_content(init, alloc); } 

We can't as easily use it for the first constructor (which default-constructs elements) because in that case T might be non-copyable.

The helper function prompts a possibility of one or two additional constructors - we could accept a sized_range (possibly of rvalues, thanks to std::views::as_rvalue, helping us move values from other containers).

---

We can get rid of register_empty_cleanup(), just by declining to call an unassigned std::function:

 ~dynamic_array() { if (cleanup) // or, "if (elems)" cleanup(elems, count); } 

---

I don't see any reason to disable move-assignment or move-construction. We could use copy-and-swap idiom for the latter.

---

The rbegin() and rend() look wrong to me:

using reverse_iterator = std::reverse_iterator<iterator>; using const_reverse_iterator = std::reverse_iterator<const_iterator>; reverse_iterator rbegin() noexcept { return end(); } const_reverse_iterator rbegin() const noexcept { return end(); } reverse_iterator rend() noexcept { return begin(); } const_reverse_iterator rend() const noexcept { return begin(); } 

I'm not sure how we're getting away with this, since the std::reverse_iterator constructor here is explicit - I don't see any exception that applies to bare pointers.

---

The set of relational operators can be replaced with <=> and std::lexicographical_compare_three_way() (there's no ranges version of this algorithm, likely due to it appearing after the ranges algorithms were written).

---

In the test program's allocator, we have

 template <typename... Args> void construct(T* ptr, Args&&... args) { std::cerr << "construct(" << ptr << ", args...)\n"; std::allocator_traits<Base>::construct(*this, ptr, args...); } 

We ought to std::forward() the arguments there.

---

We could improve the Construct_throw test with a constructor that only throws every n invocations. That could help us ensure that we destruct the correct elements, in the correct order.