6
\$\begingroup\$

I've seen a few implementations of N-Dimensional arrays in C++. This is the first time I've worked with them and wanted to get some opinions on my implementation.

#include <iostream>
#include <memory>
#include <array>

template <typename T_DATA, std::size_t N>
class Nd_Array : public std::shared_ptr<Nd_Array<T_DATA, N - 1>[]> {
    Nd_Array() { }
    
    void setDimensions(const std::array<std::size_t, N> dimensions){
        for (std::size_t i =  0; i < N; i++){
            dimensions_c[i] = dimensions[i];
        }
    }

    Nd_Array(std::size_t dimensions [N]) {
        this = new Nd_Array< T_DATA, N - 1> [dimensions[0]];
        for (int i = 0; i < N; i++){
            this->get()[i] = Nd_Array<T_DATA, N - 1>(dimensions + 1);
        }
    }
public:
    std::size_t dimensions_c[N];
    
    Nd_Array( const std::array<std::size_t, N> dimensions) {
        setDimensions(dimensions);
        this->reset(new Nd_Array<T_DATA, N - 1>[dimensions[0]]);
        for (int i = 0; i < N; i++){
            this->get()[i] = Nd_Array<T_DATA, N - 1>(dimensions_c + 1);
        }
    }
};

template <typename T_DATA>
class Nd_Array < T_DATA, 1> : public std::shared_ptr<T_DATA[]> {
    friend Nd_Array < T_DATA, 2>;
    Nd_Array() {  }
    
    Nd_Array(std::size_t dimensions [1]) {
        dimensions_c [0] = dimensions[0];
        this->reset(new T_DATA[dimensions_c[0]]);
    }

 public:
    std::size_t dimensions_c[1];
    
    Nd_Array(const std::array< std::size_t, 1> dimensions) {
        dimensions_c [0] = dimensions[0];
        this->reset(new T_DATA[dimensions_c[0]]);
    }
};

int main() {
    Nd_Array < int, 2> arr ({2,3});
    arr[0][0] = 5;
    arr[1][3] = 3;
    std::cout << "\n" << arr[0][0];
    std::cout << "\n" << arr[1][3];
    return 0;
}
\$\endgroup\$

2 Answers 2

6
\$\begingroup\$

Check for Buffer Overflows

Always, always, always check for buffer overflows in C++.

If you need to skip the bounds checking for the sake of performance in an inner loop, ask yourself whether a map/reduce/foreach interface, or a filter iterator for range for, would in fact solve your problem more safely and elegantly.

If you really, truly, do need indexing with no bounds-checking, at least provide a safe API like .at() as an alternative.

The Constructors Do Not Work

If you try to construct one of these with a dimension greater than 2, using the public: constructor that takes a std::array, it will try to recursively call both the constructors

new Nd_Array<T_DATA, N - 1>[dimensions[0]]

which calls the default constructor on each element, and

Nd_Array<T_DATA, N - 1>(dimensions_c + 1);

However, both of these constructors are private: to a different class, with different template parameters. You only provide a friend declaration for the base < T_DATA, 1 > overload to be visible to the < T_DATA, 2 > overload. Construction therefore fails for any dimension greater than 2.

To fix this, add to the definition of Nd_Array< T_DATA, N > the declaration,

friend class Nd_Array< T_DATA, N+1 >;

Follow the Rule of 5

Since the type is both copyable and moveable, it should have a move constructor, copy constructor, move assignment operator, and copy assignment operator. The default ones will do, but you should declare them, so client code knows what part of the interface they are in, and an unexpected base-class implementation will not confuse the compiler.

explicit Nd_Array(const Nd_Array&) = default;
explicit Nd_Array(Nd_Array&&) = default;
Nd_Array& operator= (const Nd_Array&) = default;
Nd_Array& operator= (Nd_Array&&) = default;

Your Constructors Should Be explicit

You might want some additional ones, but you want to avoid unexpected or ambiguous matches.

You Could Shoot Yourself in the Foot with the Destructor

You inherit from std::shared_ptr and introduce a new data member, so you need to override the base class destructor. However, on most implementations, its destructor is not virtual. Therefore, if you delete a Nd_Array through a pointer to std::shared_ptr, it will silently call the wrong destructor.

This would not happen if the class contained a smart pointer, instead of being one. It could still use the default constructors, assignments, and destructor that way.

Use Base-Class Initializers Where Appropriate

Currently, you have statements such as

this = new Nd_Array< T_DATA, N - 1> [dimensions[0]];

Which is meant to use the shared_ptr assignment. This would be better as adding to the initializer list

Nd_Array(std::size_t dimensions [N])
 : storage(new Nd_Array< T_DATA, N-1 >[dimensions[0]])

or, keeping the current inheritance hierarchy,

Nd_Array(std::size_t dimensions [N])
  : std::shared_ptr<Nd_Array< T_DATA, N-1 >[]>(new Nd_Array< T_DATA, N-1 >[dimensions[0]])

You could replace several of the nested constructors with expressions such as this.

The Implementation is Inefficient

This does what it does in a reasonable way, including support for the array[i][j][k] syntax and for passing around dangling rows. If you actually need that functionality, changing the implementation would remove some of it. It does so at the cost of efficiency.

Let’s write a somewhat verbose, but lean, test driver and see the code we get. The slightly-tweaked header looks like so:

#include <memory>
#include <array>

template <typename T_DATA, std::size_t N>
class Nd_Array : public std::shared_ptr<Nd_Array<T_DATA, N - 1>[]> {  
    friend class Nd_Array< T_DATA, N+1 >;

    Nd_Array() = default;

    Nd_Array(std::size_t dimensions [N])
      : std::shared_ptr<Nd_Array< T_DATA, N-1 >[]>(new Nd_Array< T_DATA, N-1 >[dimensions[0]])
    {
        for (size_t i = 0; i < N; i++){
            this->get()[i] = Nd_Array<T_DATA, N - 1>(dimensions + 1);
        }
    }

    void setDimensions(const std::array<std::size_t, N> dimensions){
        for (std::size_t i =  0; i < N; i++){
            dimensions_c[i] = dimensions[i];
        }
    }

public:
    std::size_t dimensions_c[N];

    Nd_Array(const Nd_Array&) = default;
    Nd_Array(Nd_Array&&) = default;
    Nd_Array& operator= (const Nd_Array&) = default;
    Nd_Array& operator= (Nd_Array&&) = default;
    ~Nd_Array() = default;

    Nd_Array( const std::array<std::size_t, N> dimensions) {
        setDimensions(dimensions);
        this->reset(new Nd_Array<T_DATA, N - 1>[dimensions[0]]);
        for (size_t i = 0; i < N; i++){
            this->get()[i] = Nd_Array<T_DATA, N - 1>(dimensions_c + 1);
        }
    }
};

template <typename T_DATA>
class Nd_Array < T_DATA, 1> : public std::shared_ptr<T_DATA[]> {
    friend Nd_Array < T_DATA, 2>;
    Nd_Array() {  }
    
    Nd_Array(std::size_t dimensions [1]) {
        dimensions_c [0] = dimensions[0];
        this->reset(new T_DATA[dimensions_c[0]]);
    }

 public:
    std::size_t dimensions_c[1];
    
    Nd_Array(const std::array< std::size_t, 1> dimensions) {
        dimensions_c [0] = dimensions[0];
        this->reset(new T_DATA[dimensions_c[0]]);
    }
};

And the test driver:

#include <iostream>

int main() {
    std::cout << (Nd_Array< int, 5 >(std::array<size_t, 5>{2,4,6,8,16})[1][1][1][1][1])
              << '\n';
    return 0;
}

On Clang++ 15.0.0 with -std=c++20 -O3 -march=x86-64-v3, the first output statement compiles to:

        sub     rsp, 112
        vmovups ymm0, ymmword ptr [rip + .Lconstinit]
        vmovups ymmword ptr [rsp], ymm0
        mov     qword ptr [rsp + 32], 16
        lea     rdi, [rsp + 56]
        vzeroupper
        call    Nd_Array<int, 5ul>::Nd_Array(std::array<unsigned long, 5ul>) [base object constructor]
        mov     rax, qword ptr [rsp + 56]
        mov     rax, qword ptr [rax + 48]
        mov     rax, qword ptr [rax + 40]
        mov     rax, qword ptr [rax + 32]
        mov     rax, qword ptr [rax + 24]
        mov     esi, dword ptr [rax + 4]
        mov     rdi, qword ptr [rip + std::cout@GOTPCREL]
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)@PLT

Where the [base object constructor] call has five levels of nested loops. Accessing an element required six nested lookups of heap-allocated memory, probably not in the cache because there is no locality of reference. When the array falls out of scope, the destructor loops through every nested row of the array, decrementing its reference count and recursively calling the destructor on all of its rows.

What Might You Do Instead?

Suppose you had a class Array3d<T> that you access by calling a3d( i, j, k ). Internally, it keeps its data in a flat std::vector or std::unique_ptr and implements the lookup with

 return storage[ dim[1]*dim[2]*i + dim[2]*j + k ];

(Or slightly refactored for the sake of optimization to nested form, dim[2]*(dim[1]*i + j) + k.)

All data is contiguous, for locality of reference. Construction consists of finding a product and making a single allocation. Destruction consists of deallocating a single block of memory. Accessing an element needs only to look up a single base pointer and index it. The object can still be moved efficiently.

This does give up the ability to pass around rows of the array or its subarrays as reference-counted objects that can outlive their parent, but that’s it. Also, making it N-dimensional would get much more complicated.

But I have found that a flat 2- or 3-dimensional array with contiguous storage is nearly always the type of array with multiple, variable dimensions that I want.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ Excellent answer - I was a bit rushed writing mine, but all the points I made are explained better here, plus several that I missed. \$\endgroup\$ Jan 8, 2023 at 10:48
  • \$\begingroup\$ Thank you very much for the detailed answer. I implemented it the way I did mostly to be able to passing around dangling rows in the interest of altering large sections of the array by simply reassigning a pointer. \$\endgroup\$ Jan 8, 2023 at 12:52
  • \$\begingroup\$ @mikeLundquist You’re correct. You can definitely swap out rows quickly with this implementation. However, unless the rows are very large, it’s likely that an operation on a slice of a flat array would be just as fast, because the memory is contiguous and will all be prefetched. \$\endgroup\$
    – Davislor
    Jan 8, 2023 at 14:00
  • 1
    \$\begingroup\$ Actually, going to N dimensions is not necessarily that complicated. If you take your formula for calculating the index access, you'll realize it's really just an accumulator. Add first index (i), multiply by dimension, add second index (j), multiply by dimension, add third index (k). For simplicity you could add a multiply for the last (by 1). \$\endgroup\$ Jan 8, 2023 at 14:04
  • \$\begingroup\$ @MatthieuM. Right, I do know about the nested formula, and you’re correct about that. I was thinking mainly of the template syntax to do things like make a 4-dimensional array take four indices and only four indices, etc. Especially if we start passing in higher-order functions. \$\endgroup\$
    – Davislor
    Jan 8, 2023 at 22:28
4
\$\begingroup\$

It's better to compose by aggregating standard library types rather than inheriting from them. Public inheritance certainly seems strange for the detail of how the data are represented.

If dimensions_c were a std::array, then we could simply copy from dimensions instead of copying an element at a time. And that isn't necessary, given std::copy() and more recently std::ranges::copy() (both in <algorithm>).

Similarly, we should be using std::fill() or std::ranges::fill() when we populate the array of Nd_Array<N-1> objects.

I'm surprised by this = in the constructor (using the operator= we inherited from std::shared_pointer). Why not value-initialise the base class, rather than default-initialising and then assigning?

I would suggest that a std::array or a std::vector will give better locality, and thus better performance, than all this indirection through shared pointers (and why is a shared pointer your choice in particular? If we need shared ownership, let the user select that with std::shared_pointer<Nd_Array> on a case-by-case basis). Ideally we want a single storage of size ...✕planes✕rows✕cols that can be indexed with something like "(( ... + planes) * z + rows) * x + y".

\$\endgroup\$
3
  • \$\begingroup\$ A std::array would only work for constexpr array dimensions, but std::vector would work. So would the array version of std::unique_ptr with variables storing the dimensions. \$\endgroup\$
    – Davislor
    Jan 8, 2023 at 12:18
  • \$\begingroup\$ However, a std::array implementation has the big advantage that it could be constexpr. Might indeed be worth considering. \$\endgroup\$
    – Davislor
    Jan 8, 2023 at 22:30
  • \$\begingroup\$ We might even want to provide a choice of implementations (sadly, I don't quite see that we can use the Strategy pattern to avoid code duplication, given that we'd want as much constexpr as possible). \$\endgroup\$ Jan 16, 2023 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.