Multi-dimensional array as a class member to be allocated on the heap

Question

I am programming a simulation for my bachelor's thesis and I'm not an expert in C++, and after having searched for quite some time now without finding a convenient answer, or question, for that matter, I resort to you guys.

My problem is as follows. I have some class that has a couple of member fields num_a and num_b besides others that can be stored on the stack. Now both these values are roughly of size 1000-2000. What I need now is another class member for SampleClass, namely a 2-dimensional boolean array of size num_a * num_b. Due to its size, it needs to be alloacted on the heap. It needs to be contiguous in memory, so storing a pointer to pointers to arrays does not work for me.

SampleClass : Object {
   public:
         uint16_t num_a;
         uint16_t num_b;
         ??? // some data structure for my 2d array

         // simple constructor
         SampleClass(num_a, num_b);

}

I declare my classes in a header file .h and implement the functions and the constructor in a source file .cc.

As you see, the values of both num_a and num_b are not pre-determined and thus not const. My question is, how do I (in a simple way) declare this thing in the header file, and how do I initialize it in the constructor in the source file?

A thing that I have found that uses vector is the following:

// header file
std::vector<std::vector<bool>> *coverage_matrix;

// source file
coverage_matrix = new std::vector<std::vector<bool>>();
coverage_matrix->push_back(something); // do something with it

Does this last approach work and more importantly, is it as efficient as a solution that does not rely on std::vector would be?

Thanks for your answers.

You don't need *pointer* on `vector`, `vector` would be enough. — Jarod42, Jun 05 '19 at 13:25
2d vectors should be avoided as they have no guaranteed memory locality. If you need a matrix, either get a good matrix library, or write your own using a flat vector and fake that it has multiple dimensions. — NathanOliver, Jun 05 '19 at 13:25
I would like to not use a `std::vector`, if possible. I have two entities A and B, and just need a large matrix where I can read whether A is covered by B, which will be updated very often during the course of the simulation. — Jens Eirik Sæthre, Jun 05 '19 at 13:29
@Jarod42 I have learned Systems Programming in C where there are no classes, that's why I'm not sure about how instances of classes are layout in memory. If I were to use no pointer, how would the compiler know that `coverage_matrix` is to be stored on the heap and not on the stack? Or does it even need to know? — Jens Eirik Sæthre, Jun 05 '19 at 13:33
internal of vector has pointer(s), but you don't need to have pointer to use it. — Jarod42, Jun 05 '19 at 13:34
@JensEirikSæthre Vector store it's data on the "heap". The vector itself is only a couple pointers in size. — NathanOliver, Jun 05 '19 at 13:34
[Heap allocate a 2D array (not array of pointers)](//stackoverflow.com/a/10116675) — 001, Jun 05 '19 at 13:35
@Jarod42 okay. well, thanks! but I only have to take care of the deletion of a vector myself if I explicitly allocate it with the `new` keyword, am i right? — Jens Eirik Sæthre, Jun 05 '19 at 13:38
For a 2d array then you can do something like this https://stackoverflow.com/a/53038618/3807729 — Galik, Jun 05 '19 at 13:38
@JohnnyMopp This would work if one of the dimension was known to be `const`, but I explicitly stated that it isn't. Hence the declaration will not work. — Jens Eirik Sæthre, Jun 05 '19 at 13:38
There is no point in allocating a `std::vector` using `new` because it already allocates its internal data on the heap. — Galik, Jun 05 '19 at 13:39
@JohnnyMopp That answer is for C, not C++. They are distinct language which favor different kinds of solutions. — François Andrieux, Jun 05 '19 at 13:39
@JensEirikSæthre "_but I only have to take care of the deletion of a vector myself if I explicitly allocate it with the new keyword_" Why would you need to allocate `std::vector` with `new`? You don't need to do that.. — Algirdas Preidžius, Jun 05 '19 at 13:39
Beware if you need consecutive `bool` elements use a `vector` and definitely not a `vector` which is a highly optimized programmer trap (it stores 8 booleans in a byte) — Serge Ballesta, Jun 05 '19 at 13:43
@AlgirdasPreidžius Okay. So the `coverage_matrix` vector itself will be on the stack. however, the data that it holds is allocated on the heap? So as soon as `coverage_matrix` goes out of the scope, will the allocated space for the data be freed? — Jens Eirik Sæthre, Jun 05 '19 at 13:51
@JensEirikSæthre Short answer: yes. Long answer: Consider learning from a [good C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Algirdas Preidžius, Jun 05 '19 at 13:52

score 3 · Accepted Answer · edited Jun 20 '20 at 09:12

2-dimensional ... array ... of size num_a * num_b ... Due to its size, it needs to be alloacted on the heap. It needs to be contiguous in memory
std::vector<std::vector<bool>>

In a vector of vectors, rows are contiguous within themselves, but not in relation to each other. This is the same as an array of pointers. So, this does not satisfy your need for contiguous layout.

 new std::vector<std::vector<bool>>()

There is hardly ever a need to dynamically allocate a vector like this. It is best to be avoided for benefit of correctness, and performance.

The only solution to allocating a contiguous array of dynamic size is to allocate a 1-dimensional array, where the rows are flatly one after the other. Like this for example:

std::vector<bool> matrix(num_a * num_b);

You can access the element [a][b] at index a + num_a * b.

Note that std::vector<bool> is very special and different from other vectors. It does not contain any bool objects, but rather the bits are packed, and accessed through masking and shifting ¹. This makes the data structure very cache friendly, but operations more complicated. Whether this is good or bad for performance depends on what you do with it as well as the CPU arcitecture.

More importantly than the performance consideration, this means that some guarantees that you can rely on with other arrays don't apply to std::vector<bool>. For example, you cannot take the address of an element, nor can you modify different elements in different threads without synchronisation. And regarding your particular case since there are no guarantee of bool objects, there certainly aren't guaranteed to be contiguous bool objects in the vector.

So, if you need a regular array of bool, you need to work around the specialization when using a vector. For example:

enum boolean : bool {no, yes};
std::vector<boolean> matrix;

¹ Technically, there is no guarantee of any particular representation. It is implementation defined.

@Bob__ I read that as not a contiguous array of bool because it's compressed into less space. Note the condition on n. Although that and all other details of its optimization (or not) are implementation defined. — Kenny Ostrom, Jun 05 '19 at 13:57
@KennyOstrom I added an addendum mentioning the implementation definedness. — eerorika, Jun 05 '19 at 13:59

Multi-dimensional array as a class member to be allocated on the heap

1 Answers1