1

I've been trying to create a variable length multidimensional array. As I understand, you can't create variable length arrays on the stack, but you can create 1D variable length arrays in C++ using dynamic allocation. Correct me if this is a compiler extension, but it seems to work fine on clang and gcc with --pedantic set.

int size = 10;
int *ary = new int[size]();

I tried to extend the concept to multidimensional arrays. Here are my results. The problem with possiblity 1 and 2 is that they require a constexpr and do not work with variable sizes. Is it possible to make either of them accept a variable as its size? I put possibility 3 as I am aware of it, but it lacks [][] access, which is what I'm looking for.

constexpr int constSize = 10;

//Possibility 1: Only works in C++11
//Creates CONTIGUOUS 2D array equivalent to array[n*n], but with [][] access

int (*ary1)[constSize] = new int[constSize][constSize]();
delete [] ary1;

//Possibility 2:
//Really horrible as it does NOT create a contiguous 2D array
//Instead creates n seperate arrays that are each themselves contiguous
//Also requires a lot of deletes, quite messy

int **ary2 = new int*[constSize];
for (int i = 0; i < n; ++i)
    ary2[i] = new int[constSize];
for (int i = 0; i < n; ++i)
    delete [] ary2;
delete [] ary2;

//Possibility 3:
//This DOES work with non-constexpr variable
//However it does not offer [][] access, need to access element using ary[i*n+j]

int *ary3 = new int[size*size];
delete [] ary3;
9
  • 1
    int *ary = new int[size](); is not a compiler extension, that's a 1D variable length array via dynamic allocation. I'm pretty sure it's the most common reason to have dynamic allocation. Mar 11, 2015 at 17:31
  • 4
    You can provide [][] access for the last version if you wrap the pointer in a class and use overloaded operators and a proxy class. Or you just overload operator() to get a ary3(x, y) syntax. And get rid of the new[] and use std::vector. Mar 11, 2015 at 17:33
  • 1
    Why do you believe the vector solution is slower? It should not do anything which makes it slower than a raw dynamically allocated array; if anything, it should be slightly faster for certain operations, and it's more flexible because it uses placement new, not new[]. You can make it contiguous exactly the same way as a dynamically allocated array (i.e. your third solution here). Mar 11, 2015 at 17:54
  • I'm copying what I said below but basically I created an array and vector of size 100,000,000 and then did a for loop with container[i] = i; The time for the vector was 0.269s and for the array was 0.004s.
    – JamesLens
    Mar 11, 2015 at 18:19
  • 1
    @JamesLens: This should certainly not happen. Perhaps you left bounds checking in? But even then the difference should not be so big IMO. You could post your exact test case as a separate question. Mar 11, 2015 at 18:21

2 Answers 2

1

This will create a dynamically allocated 2D variable-length array, with dimensions w and h:

std::vector<std::vector<int>> ary4(w, std::vector<int>(h));

It can be accessed with [][]:

ary4[x][y] = 0;

However, it's not contiguously allocated. To get a contiguous array, here's one solution:

template<typename E>
class Contiguous2DArray
{
public:
    Contiguous2DArray(std::size_t width, std::size_t height)
    : array(width * height), width(width) {}

    E& operator()(std::size_t x, std::size_t y)
    { return array[x + width * y]; }

private:
    std::vector<E> array;
    std::size_t width;
}

It can be used like this:

Contiguous2DArray<int> ary5(w, h);
ary5(x, y) = 0;
7
  • Does not meet the contiguous-memory requirement (although that requirement may be overrated anyway with regards to execution speed). Mar 11, 2015 at 17:39
  • This is an array of arrays, not a 2D array.
    – user1804599
    Mar 11, 2015 at 17:49
  • @JamesLens You say a vector is non-contiguous but that's not true. Also the operator[] will be inlined by the compiler, so in the end there will be little to no difference in performance compared to a raw array. Also, remember the quote about premature optimization. Btw made an edit, check it out.
    – Emil Laine
    Mar 11, 2015 at 18:04
  • You know that you can overload operator[]
    – Motti
    Mar 11, 2015 at 19:11
  • 1
    @zenith ary5[x][y] is possible if you write a helper class for Contiguous2DArray::operator[] to return which has its own overloaded operator[] . ary5[x, y] would be using the built-in comma operator which isn't appropriate here.
    – M.M
    Mar 11, 2015 at 20:03
1

The number of dimensions is fixed, because the type of what [] returns changes based on the number of dimensions. Access is through both repeated [] and (...). The first mimics C-style array lookup. The (...) syntax must be complete (it must pass N args to an N dimensional array). There is a modest efficiency cost to support both.

Uses C++14 features to save on verbosity. None are essential.

Using an an n_dim_array with 0 dimensions will give bad results.

template<class T, size_t N>
struct array_index {
  size_t const* dimensions;
  size_t offset;
  T* buffer;
  array_index<T,N-1> operator[](size_t i)&&{
    return {dimensions+1, (offset+i)* *dimensions, buffer};
  }
  template<class...Is, std::enable_if_t<sizeof...(Is) == N>>
  T& operator()(size_t i, Is...is)&&{
    return std::move(*this)[i](is...);
  }
};
template<class T>
struct array_index<T,0> {
  size_t const* dimension;
  size_t offset;
  T* buffer;
  T& operator[](size_t i)&&{
    return buffer[i+offset];
  }
  T& operator()(size_t i)&&{
    return std::move(*this)[i];
  }
};

template<class T, size_t N>
struct n_dim_array {
  template<class...Szs, class=std::enable_if_t<sizeof...(Szs)==N>>
  explicit n_dim_array( Szs... sizes ):
    szs{ { static_cast<size_t>(sizes)... } }
  {
    size_t sz = 1;
    for( size_t s : szs )
      sz *= s;
    buffer.resize(sz);
  }
  n_dim_array( n_dim_array const& o ) = default;
  n_dim_array& operator=( n_dim_array const& o ) = default;


  using top_level_index = array_index<T,N-1>;
  top_level_index index(){return {szs.data(),0,buffer.data()};}
  auto operator[]( size_t i ) {
    return index()[i];
  }
  using const_top_level_index = array_index<const T,N-1>;
  const_top_level_index index()const{return {szs.data(),0,buffer.data()};}
  auto operator[]( size_t i ) const {
    return index()[i];
  }
  template<class...Is,class=std::enable_if_t<sizeof...(Is)==N>>
  T& operator()(Is...is){
    return index()(is...);
  }
  template<class...Is,class=std::enable_if_t<sizeof...(Is)==N>>
  T const& operator()(Is...is) const {
    return index()(is...);
  }
private:
  n_dim_array() = delete;
  std::array<size_t,N> szs;
  std::vector<T> buffer;
};

live example

Does not support for(:) loop iteration. Writing an iterator isn't that hard: I'd do it in array_index.

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.