Is there a way to make a dynamic two-dimensional array in C++?

Question

So I wanted to create a game with a square world.

When starting the game, the user should be able to specify the size of the world.

The world is saved as a two-dimensional array of shorts.

const short gameSize = 4;
short world[gameSize][gameSize];

The short gameSize must be const, otherwise, I can't put gameSize as the size of world[][].

However, this won't allow me to set gameSize to the player-wished size.

I thought of something simple like

short gameSize = 0;
cout << "World size?" << endl;
cin >> gameSize;
short world[gameSize][gameSize];

As stated, this won't work.

In the game, it won't be possible to change the value of gameSize later on.

How could I make this happen?

Does this answer your question? [How to create a dynamic array of integers](https://stackoverflow.com/questions/4029870/how-to-create-a-dynamic-array-of-integers) — Kitswas, Jun 03 '21 at 13:11
Does this answer your question? [How do I declare a 2d array in C++ using new?](https://stackoverflow.com/questions/936687/how-do-i-declare-a-2d-array-in-c-using-new) — yaodav, Jun 03 '21 at 13:11
Once the matrix is created, do you need to resize it dynamically during runtime? I am asking once 2D array is created dynamically will you need to change its size later? If yes, then you can not use new operator. As memory allocated using new is not resizable and hence you will need to use malloc/calloc and realloc. — Pandav Patel, Jun 03 '21 at 13:12
@Edex, while the linked question is technically the correct answer to your question, it's almost certainly not what you want to do in your specific circumstance. — , Jun 03 '21 at 13:23
@yaodav Almost all answers to that question are *terrible*. It’s a very bad canonical duplicate. In fact, that question should probably be nuked from orbit. — Konrad Rudolph, Jun 03 '21 at 13:25
@KonradRudolph Well, at least *that* question is explicitly about `new`, so the only bad thing is linking to it from the wrong place. — , Jun 03 '21 at 13:31
@Frank The original question is indeed fine, as a theoretical C++ language question. The problem with that question is that, based on its views and activity, it has become the canonical link target for all kinds of questions, and that’s actively harmful. — Konrad Rudolph, Jun 03 '21 at 13:39
@KonradRudolph Now here's what you could do then: post a draft of a self-answered Q&A on meta, proposing to nuke the linked one from orbit and replace it with a community wiki. Or well, close the bad one as dupe to the new community wiki. Normally one could just go ahead and do that with a dupe hammer, but I'd rather ask on meta before clobbering a 800+ upvoted post. Also there's this new "outdated question status" experiment, not sure where that one landed. — Lundin, Jun 03 '21 at 13:51

score 6 · Answer 1 · 2021-06-28T16:58:05.700

6

Don't use new as the linked questions/answers would lead you to do. It's unnecessary in your case and will increase the risk of potential bugs for no good reason.
Use std::vector<short> to manage an indexable chunk of memory storing the world values.
Convert 2D coordinates into an index as needed.
(optional) Encapsulate it all in a class so it's hidden

#include <vector>
#include <cassert>
#include <iostream>

class GameWorld {
  std::size_t world_size_;
  std::vector<short> data_;

public:
  GameWorld(std::size_t size) 
    : world_size_(size) 
    , data_(size * size) {}

  short& operator()(std::size_t x, std::size_t y) {
    assert(x < world_size_ && y < world_size_);

    return _data[y + x * world_size_];
  }

  const short& operator()(std::size_t x, std::size_t y) const {
    assert(x < world_size_ && y < world_size_);

    return _data[y + x * world_size_];
  }
};


int main() {
  short gameSize = 0;
  std::cout << "World size?" << std::endl;
  std::cin >> gameSize;
  GameWorld world(gameSize);

  // Set the value of [0, 0] to 4
  world(0, 0) = 4;
}

There's a few things happening here:

Using vector<short> will give you a dynamic size as well as memory safety. i.e. Things will get cleaned up "automatically" as appropriate.
You might be tempted to use vector<vector<short>>, so that world[x][y] "just works". But that's not great because the memory will be all over the place, packing it tightly into a one-dimensional array gives you a bunch of performance benefits in general.
You might "think" that calling a function and doing math on indices is expensive, but it's actually the exact same thing the compiler does when you call world[x][y] in your previous code, so no additional cost is incurred here.
The assert()s will catch potential bugs when building in debug mode, and disappear entirely in release/NDEBUG mode. So you have an additional "free" safety net .

Bonus: If you want to start dipping your toes into template programming, this is a great starting point to learn. Templating GameWorld so that it can be a world of float, int, or some struct Cell instead of always being a world of short is useful, easy to do, and not disruptive to the rest of the code.

edited Jun 28 '21 at 16:58

answered Jun 03 '21 at 13:06

Re (1): OP does not mention `new`. It’s extremely unfortunate that the chosen duplicate does. – Konrad Rudolph Jun 03 '21 at 13:17
@KonradRudolph The question was marked as a duplicate of something specific to `new`. I felt like specifying that this is a bad idea in OP's case is warranted. so I updated the answer with step 1. – Jun 03 '21 at 13:18
In your answer, you wrote: `"packing it tightly into a one-dimensional array gives you a bunch of performance benefits"` -- That will mainly increase performance when accessing one dimension contiguously, but not so much when accessing the other dimension contiguously. Therefore, the game Factorio instead divides the game world into "chunks" of 32*32 tiles (total 1024 tiles), which are each stored in memory contiguously, so that CPU cache performance is good for both dimensions. – Andreas Wenzel Jun 03 '21 at 13:52
@AndreasWenzel It's true that there exists scenarios where alternate memory layouts for dense matrices can outperform row (or column) major tight packing, but that's a property of the algorithm consuming the matrix. Without a specific algorithm being targeted (e.g. assuming random access), lowering the memory footprint and minimizing the distance between cells is pretty much the best you can do. (not to mention the initialization and resizing costs) – Jun 03 '21 at 13:56
Or in case you just expect the coordinates to be a few 100 items, you could simply do a `std::array` with "max" size and then keep track of how much that is used. Such code will be running in circles around std::vector, pointing fingers at it. We're almost talking C performance. – Lundin Jun 03 '21 at 14:06
@Lundin Why should `std::array` code (or C code) be more efficient *for access* than `std::vector`? The dynamic allocation happens *once*. The rest of the performance will be determined, almost exclusively, by whether the relevant data is in cache. And the code generated for the accessor by a modern GCC using `-O2` is identical (for `std::vector`, `std::array` and statically sized C-style array). – Konrad Rudolph Jun 03 '21 at 14:13
@KonradRudolph No, dynamic allocation happens once or as soon as std::vector runs out of space. Ok if you don't resize it, that only happens once. Yet the actual heap allocation takes considerable time. Now suppose some dummy creates a static storage duration object of the class. That heap allocation time then keeps piling up on the time it takes to start your program. And if that initial constructor call was only a default constructor, then you get the heap allocation once more when you call it "for real" in the application code. – Lundin Jun 03 '21 at 14:19
@Lundin I don’t understand your comment: there is no reallocation happening in the `GameWorld` class. *Ever*. The only difference here is that `std::vector` heap-allocates (once), and `std::array`/C array stack-allocates. *Theoretically* there might be an additional indirection from the `vector` instance to the heap memory but in practice compilers elide this. Once again, the generated code is *identical*. – Konrad Rudolph Jun 03 '21 at 14:20
rephrasing my previous comment (since I've given it more that 20 seconds): If you apply the `max_world_size` optimization to the the vector-based solution, it's *hella close*, but it **is** faster on account of one less indirection: https://gcc.godbolt.org/z/q7Ga36YeM – Jun 03 '21 at 14:22
@Frank What you’re seeing (both in this and your previous example) is the difference between passing the array directly *vs* having it inside a class. It’s unrelated to `std::vector` *vs* `std::array`. You can verify this by changing the vector type inside your class. – Konrad Rudolph Jun 03 '21 at 14:23
@KonradRudolph Not in this specific example, but in a general use-case. You can't prevent someone from creating a `static GameWorld` or a file scope one. – Lundin Jun 03 '21 at 14:25
@KonradRudolph It IS related because you need to lookup the base pointer in the `vector` case wherease `this` IS the base pointer with `array` – Jun 03 '21 at 14:25
@Frank As I mentioned previously, *this does not impact codegen*. GCC at least (but I’m sure this is also true for clang/MSVC/ICC) manages to generate the same code regardless. – Konrad Rudolph Jun 03 '21 at 14:26
@Lundin What does the scope have to do with this? The `GameWorld` class simply *cannot* reallocate. It has no corresponding function in its public API. `std::vector` isn’t magically slower than `std::array`. – Konrad Rudolph Jun 03 '21 at 14:26
@KonradRudolph Having the array as a member of GameWorld is practically indistinguishable from just passing the array, which is why I didn't bother out of lazyness. The codegen sure seems different to me: https://gcc.godbolt.org/z/Y186z9K4z – Jun 03 '21 at 14:29
@KonradRudolph No magic involved. Heap allocation is slower than stack or data/bss allocation. It sets off various OS API calls underneath the hood. Just benchmark _the whole execution time_ of a program using std::vector vs std::array. – Lundin Jun 03 '21 at 14:34
1

@Lundin Personally, while you are technically correct, I think overfocusing on the allocation cost for a class that is clearly meant to ever be allocated once in a blue moon is grasping a straws, especially when your alternative only works for "small" allocations when used on the stack. The removed indirection benefit is much more real. – Jun 03 '21 at 14:39
1

@Frank Good point. My own attempt was looking at the codegen for a loop, and the codegen in that case is identical since the accessor inside the loop is inlined and thus doesn’t need the added indirection (except once, at the very beginning). – Konrad Rudolph Jun 03 '21 at 14:58
@KonradRudolph If you want to get pedantic about it, inlining has nothing to do with it. The indirection is simply cached at the start of the loop. – Jun 03 '21 at 15:06
@Frank The indirection can only be cached/computed once at the start of the loop *because* the `operator()` calls are inlined. – Konrad Rudolph Jun 03 '21 at 15:11

Is there a way to make a dynamic two-dimensional array in C++?

1 Answers1

Linked