4
\$\begingroup\$

I am in need of a multidimensional array that can be initialized easily with arbitrary dimensions. I have found this code here, which is beautiful, however poses some difficulties for me. its hard to initialize with arbitrary size and also difficult to access since I have to input each index using a comma to seperate it.

In my application each array 'slot' has the same size. Furthermore it would be easy to work with, if I could index and access everything using an array, instead of having to input every index seperated by a comma. So I wrote the following code which provides something like that, however feels very heavy due to only using one large array. I am basically shifting the 'multidimensional' array layers into one huge array... abusing high valued indices. Is there a way to approve apon the code, making it faster, and using less memory and high value calculations?

#include <iostream>
#include <cmath>
#include <array>

using namespace std;


template <class T, size_t depth, size_t each_size>
class MultiArray
{
    array<T, static_cast<size_t>( pow(each_size, depth) )> multiArray;

public:
    MultiArray()
    { ; }

    void put(array<size_t, depth> indices, T thing_to_put)
    {
        size_t index = 0;
        int dimension_counter = 0;
        for (const size_t& i : indices)
        {
                index += i * nearbyint(pow(each_size, dimension_counter));
                dimension_counter++;
        }

        this->multiArray[index] = thing_to_put;
    }

    void get(array<size_t, depth> indices, T &thing_to_get)
    {
        size_t index = 0;
        int dimension_counter = 0;
        for (const size_t& i : indices)
        {
                index += i * nearbyint(pow(each_size, dimension_counter));
                dimension_counter++;
        }
        thing_to_get = this->multiArray[index];
    }
};

if you would like you can find a slightly longer version of the code above with some debugging, simple testing and very basic error handling here.

EDIT: I would like to find a very fast and efficiant way to do things! I would be happy about input on how to get a fast multidimensional array class :) Thank you all for your help!!!

\$\endgroup\$
2
\$\begingroup\$

pow is not constexpr

pow is not constexpr, and the current behavior relies on particular compiler. You'll need constexpr function to calculate the power.

Potentially dangerous implementation

Users of the class will need to store the MultiArray on free store to ensure they don't overflow the stack (I know some compilers extend it during runtime, but it is still non-standard). I recommend using vector instead.

Interface

When using std::vector, need for templated size arguments disappears. It would be possible to templatize on allocator instead, defaulting to std::allocator<T>. The sizes could be passed on constructor call.

Subscript operator

That's going to be an issue, but it is easily solvable. Just make it

T& operator[](const std::initializer_list<std::size_t> indices)
{
    //use math to calculate the index
}

You'll also need const version. Input type may be different, but it should also check if the number of elements inside match the dimension count. You could templatize sizes still, so that this one can be replaced with const std::array<std::size_t, DimensionCount>&.

\$\endgroup\$
  • \$\begingroup\$ thank you very much for you input! I put in your changes, please find the code here cpp.sh/6ngw2 I ran into some trouble: how can I put the new power function into my class (so everything stays one nice package?) Also could you please expand a little on the problem using array? also isn't the template the faster way to do things? \$\endgroup\$ – the.polo Aug 25 '17 at 10:17
  • \$\begingroup\$ continuing on my program, I now see the problem with using std::array here! especially when I don't know the size of MultiArray during runtime! thank you again for the input! How could I measure the performance gap between using std:array or std:verctor here? \$\endgroup\$ – the.polo Aug 26 '17 at 23:37
  • 1
    \$\begingroup\$ Use google benchmark. Or you could try to use my solution, but I'm unsure if it has dependencies to my library and in general it is a half baked solution compared to google benchmark. I recommend using google benchmark. About constexpr pow(): I don't think it should come with the class, because it is a good, useful standalone function. \$\endgroup\$ – Incomputable Aug 27 '17 at 3:24
  • 1
    \$\begingroup\$ And about templates: it doesn't matter. Having greater performance is side effect. The ultimate things that matter are generated assembly and current load on machine(s). Just benchmark, don't rely on intuition. \$\endgroup\$ – Incomputable Aug 27 '17 at 3:26
  • 1
    \$\begingroup\$ @the.polo, the array as index argument requires all of the parameters as they are present in the original question. I'm a bit out of my comfort zone these days, so I'm afraid some of my suggestions might miss the point. Please take with the grain of salt. \$\endgroup\$ – Incomputable Aug 27 '17 at 9:24
2
\$\begingroup\$

You don't need to call pow() and calculate powers "from scratch" within each loop iteration - it's probably cheaper to multiply the value calculated during previous iteration as you are calculating consecutive powers of each_size:

size_t temp = 1;
for (const size_t& i : indices)
{
    temp *= each_size;
    index += i * temp;
}

Maybe also come up with a better name for this temp variable than I did ;p

std::nearbyint() is also redunant since you are calculating integral powers of an integer, so your result is going to be an integer by definition.

Apart from this, if your array is really huge, consider using some other container that doesn't store data contiguously as with the fragmented memory there is a risk of not being able to allocate space for such a large object. std::deque might fit your needs, but it's certainly less efficient, so you have to weigh pros and cons. Another advantage would be dynamic size that adds more flexibility to the way your array is used (you can also get it with std::vector, but it's also a contiguous container).

Last but not least, there is no advantage to passing primitive types such as size_t by reference as the associated pointer that's copied is of similar size to the variable that would be copied by value.

\$\endgroup\$
  • \$\begingroup\$ Additionally there is usually no need for using 'const &' with built in types e.g. 'size_t' in this case \$\endgroup\$ – Harald Scheirich Aug 24 '17 at 17:33
  • \$\begingroup\$ I think that the last point depends on the platform. Usual gaming rigs these days have minimum of 8 GB, and they are slowly moving towards DDR4. Adding upcoming battle of Intel and AMD, I believe innovation will only increase. \$\endgroup\$ – Incomputable Aug 24 '17 at 18:33
  • \$\begingroup\$ Of course, that's why I mentioned weighing pros and cons. Everything depends on your application and who is your target user. For example for my daily routine 16 GB is often barely enough. \$\endgroup\$ – KjMag Aug 24 '17 at 20:48
  • \$\begingroup\$ @Harald Scheirich Thanks for pointing that out, updated my answer. \$\endgroup\$ – KjMag Aug 24 '17 at 20:58
  • \$\begingroup\$ The const size_t& is fine, and it's different to specifying such a reference in the prototype of a (non-inlined) function - any decent compiler can see the entire scope of i and hold it in a register, whether it's passed by reference or by value. That said, omitting the & makes it slightly easier to read. \$\endgroup\$ – Toby Speight Aug 25 '17 at 9:49
1
\$\begingroup\$

This is an interesting approach. It has nice sides, because as all dimensions are equally sized, everything is given with only 2 parameters. But it has downsides:

  • all dimensions must be equal and known at compile time
  • no easy way (at least not currently implemented) to see for example a 3D array as an array of 2D arrays.

For the second point, if you could add an operator [] that give a view on a MultiArray having one dimension less and same sizes, you could easily use it with a standard array interface. Still to implement: a MultiArrayView class and the operator[] on both classes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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