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;
JamesLens
  • 447
  • 6
  • 14
  • 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. – Mooing Duck Mar 11 '15 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`. – Christian Hackl Mar 11 '15 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). – Christian Hackl Mar 11 '15 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 '15 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. – Christian Hackl Mar 11 '15 at 18:21
  • Did not leave bounds checking in. Interestingly, I just tried this with gcc and the times for both vector and array were of the order 0.26s, while for clang as before vec time is about 0.26s and array time is 0.004s. You think this is worth asking seperately? – JamesLens Mar 11 '15 at 18:26
  • @JamesLens: As I said, it would probably make a good separate question if you can reproduce the problem. `std::vector` is designed to be a complete replacement for `new[]`, and it does not do any magic inside, it's just placement new and constructors (I suspect that in both cases the allocation takes longer than the iteration, by the way). – Christian Hackl Mar 11 '15 at 18:30
  • @JamesLens: Oh, and similar questions about vector performance may have been asked before, you better check that first! :) – Christian Hackl Mar 11 '15 at 18:31
  • @JamesLens: The following may give some insights: http://stackoverflow.com/questions/1461276/stdvector-reserve-and-push-back-is-faster-than-resize-and-array-index-w – Christian Hackl Mar 11 '15 at 18:34

2 Answers2

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;
Emil Laine
  • 41,598
  • 9
  • 101
  • 157
  • Does not meet the contiguous-memory requirement (although that requirement may be overrated anyway with regards to execution speed). – Christian Hackl Mar 11 '15 at 17:39
  • This is an array of arrays, not a 2D array. –  Mar 11 '15 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 '15 at 18:04
  • You know that you can overload `operator[] ` – Motti Mar 11 '15 at 19:11
  • @Motti Yes, but since `ary5[x][y]` is not possible and `ary5[x, y]` looks weird for element access imo, I prefer `operator()`. – Emil Laine Mar 11 '15 at 19:17
  • @райтфолд in C and C++, all "2-D" arrays are actually arrays of arrays – M.M Mar 11 '15 at 20:02
  • 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 '15 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.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524