How will the Memory behave in this C++ program?

Question

So I am not used to hardware-close programming, pointers and ram always were done for me but because I want to learn C++, I wanted to try a 2d array, that didn't work because of unknown size, so i decided to go with a 2d list.

The problem I have now though is I have no idea how the program will behave, and before I can test it I want to know if values will be copied, overwritten etc.

#include "board.h"
#include "list"
using namespace std;

void Board::initiate_board()
{
    list<list<int>> list_of_rows;
    for (int rows = 0; rows++; rows < Board::rows) {
        list<int> new_row;
        for (int columns = 0; columns++; columns < Board::columns) {
            new_row.push_back(0);
        }
        list_of_rows.push_back(new_row);
    }
}

What this is supposed to do is create a 2d list filled with 0s. I don't know though what will happen in storage and I have no way to visualise RAM and know what is were (and if I could I'd be overwhelmed) so I was hoping someone could clear this up for me.

What I think this code does is create a list of 0s, puts it into the other list and then starts a new list, deleting the old one automatically as it will not be referenced or it will be overwritter (no clue though which one). So with rows and columns at 4 it will look like

|0|0|0|0|    =>   ...   =>   |0|0|0|0|
                             |0|0|0|0|
                             |0|0|0|0|
                             |0|0|0|0|

The 2 things i am uncertain of are A: will a new list be created? Or will the old one just be increased like:

|0|0|0|0|
|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|0|0|0|
|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|

The second question is: Will the list be copied or the reference be stored? So will it after saving the 4-long-list into the first list increase the original list and as only a reference is saved increase the list[0] also to be 8 long, so that if i changed the 2nd value in the list it would be changed in every row?

|0|0|0|0|  =>   |0|0|0|0|0|0|0|0|
                |0|0|0|0|0|0|0|0|

I know this question might be very basic for someone who knows C++ but as I come from dart and python with C# being the hardware-closest language I somewhat know, this is just confusing to me. Is there a way to know what will happen other than trying it out with printing the list of lists or just guessing?

And if I wanted to save a reference and not a copy to the list, how would I then do that?

_"I wanted to try a 2d array, that didn't work because of unknown size, so i decided to go with a 2d list."_ — Why 2D list? It will be quite memory-inefficient. Why not 2D _vector_ instead? — Daniel Langr, Nov 05 '20 at 18:05
There's no such thing as a 2D `vector`. All `vector`s are 1D, but that one dimension can be a dimension of more `vector`s making it look 2D. But it's not 2D and you'll see it in the caching performance. Consider [using something like this](https://stackoverflow.com/a/2076668/4581301) to make a 1D `vector` behave like a 2D `vector` instead. — user4581301, Nov 05 '20 at 18:23
@DanielLangr i did not vektors existed and thats why i was confused ill look into it, thanks! — Maritn Ge, Nov 06 '20 at 09:39
@user4581301 2D vector is just a short term for a vector of vectors (the same as OP uses 2D list for a list of lists). I guess that everyone understands what we are talking about. BTW, your solution is not universal. It can be used basically only if you know the sizes of inner vectors in advance. I would, of course, always use a 1D vector in such a case in performance-aware applications. You should address OP with your suggestion. — Daniel Langr, Nov 06 '20 at 10:02

Human-Compiler · Accepted Answer · 2020-11-05T18:37:08.623

I recommend you pick up a good book on the basics of modern C++. C++ is a challenging language with a steep learning curve and long legacy. There is a lot to learn regarding object lifetimes, different types of construction and initialization, etc -- and it will be easier to start with a good book covering these topics.

To answer your question: the code will work the way you expect it to work; you will create a std::list containing rows std::lists that each contain columns 0s.

That is, you will produce a container of containers that logically^[1] looks like:

      <--columns-->
  ^   |0|0|...|0|0|
  |   |0|0|   |0|0|
  |    .  .      .
 rows  .    .    .
  |    .      .  .
  |   |0|0|   |0|0|
  V   |0|0|...|0|0|

Variables in C++ have lifetimes associated to them, often tied to the scope they are in. new_row starts its life where it is defined in the for loop, and is destroyed at the closing brace of the loop for each iteration.

More generally, all objects are destroyed in the reverse order declared by the end of scope; and a loop is simply a scope that occurs multiple times.

So in your above code, what is happening is:

A list called new_row is created with 0 elements
columns 0s are pushed into it (the inner loop)
list_of_rows makes a copy of new_row
new_row is destroyed (end of scope).
Repeat to step 1 for rows times

^{Technically, because list_of_rows isn't used, this gets destroyed at the end of the function scope -- though I assume that its use was omitted for brevity}

^[1] I recommend that you look into using std::vector instead of std::list, which is probably closer to what you intend to use.

std::vector is a dynamic array type (contiguous storage), whereas std::list is actually a doubly-linked list implementation. This means you can't simply index into a std::list (e.g. list_of_rows[1][2]) because access requires traversal of the list. std::vector does not have this issue.

What your list<list<...>> implementation does is actually much closer to:

             <--------columns-------->
 ^   |*| --> |0| <-> |0| ... |0| <-> |0|
 |    ^
 |    |
 |    V
 |   |*| --> |0| <-> |0| ... |0| <-> |0|
 |    .
rows  .
 |    .
 |   |*| --> |0| <-> |0| ... |0| <-> |0|
 |    ^
 |    |
 |    V
 V   |*| --> |0| <-> |0| ... |0| <-> |0|

Whereas a vector<vector<...>> implementation will be:

           <--columns-->
  ^ |*| -> |0|0|...|0|0|
  | |*| -> |0|0|   |0|0|
  |         .  .      .
 rows       .    .    .
  |         .      .  .
  | |*| -> |0|0|   |0|0|
  V |*| -> |0|0|...|0|0|

You missed the step #6: the `list_of_rows` will be destroyed on exit of that functions, so the whole thing was for nothing :) — Vlad Feinstein, Nov 05 '20 at 18:07
@VladFeinstein Fair point -- though I was assuming that `list_of_rows` would be used after this, and that its use was only omitted for the sake of asking this question. — Human-Compiler, Nov 05 '20 at 18:09
Understand. Just wanted to point out that `list_of_rows` (or `vector-of-rows`) should be a class member, and not a local variable — Vlad Feinstein, Nov 05 '20 at 18:10
@VladFeinstein in my actual code `list_of_rows` would be copied into the class member in basically the constructor — Maritn Ge, Nov 06 '20 at 09:41
@Human-Compiler thanks a lot for the detailed answer! i didn't even know vectors were a thing, i think i'll implement this! also: 'a good book' there are probably more c++ books than there are people using c++, do you have any personal recommendatoins? — Maritn Ge, Nov 06 '20 at 09:43
There's actually a really great community wiki answer here for C++ book recommendations: [The Definition C++ Book Guide and List](https://stackoverflow.com/a/388282/1678770). I would start with this since it gives suggestions based on your backgrounds and what you're looking for. Most likely something like "A Tour of C++ " is what you'd be looking for, since you indicated previous programming experience — Human-Compiler, Nov 06 '20 at 14:49

How will the Memory behave in this C++ program?

1 Answers1