beginner question about arrays in structs in C++

Question

I would like to create a struct and use it inside an other struct as an array. My problem is that I don't know how big array I would like to allocate, I will only know once I am in a function. I mean I would like to use [] instead of a pre-determined constant, like 10000.

I think if you look at my code it would be self-explanatory. Can you help me how to make this code work? Moreover it would help me a lot if you could tell me what is the name of the topic I am asking about (is it dynamic arrays?) and that where can I find articles/tutorials about this topic.

Here is the code with my broken way of thinking about arrays in structs.

#include <iostream>

using namespace std;

struct keyframe {
    bool a;
    int b;
    int c;
};


struct keyframe_file {
    const int num_views;
    const int num_keyframes;
    keyframe keyframes[];
};


int main() {

    keyframe_file my_file;

    my_file.num_views = 1;
    my_file.num_keyframes = 6;

    my_file.keyframes = new keyframe[my_file.num_keyframes];

    my_file.keyframes[0].a = true;
    my_file.keyframes[0].b = 5;
    my_file.keyframes[0].c = 9;

    return 0;

}

Answer 1

Use a std::vector.

struct keyframe_file {
    const int num_views;
    const int num_keyframes;
    std::vector<keyframe> keyframes;
};

int main() {
    keyframe_file frame;
    frame.keyframes.resize(...);
}

Answer 2

If it suits your purpose, an STL container (std::vector) is easily one of the best options - the less memory management you have to worry about, the better.

In any case, look at the struct definition Nawaz posted above - that's exactly how it should be. Dynamic arrays in C++ are simply pointers. You have, however, allocated the memory properly in your code, but you haven't freed it (so it's leaking). Since you allocated with new [] you will need to

delete [] my_file.keyframes;

in order to free the memory properly.

Resizing is another issue: with a smart implementation, array resizing can be an amortized O(1) operation which is nice. When you resize, it will always take you O(n) since you need to copy all the elements into a new array of different size, but if you do it half as much, it becomes O(1). That is, double the array each time you need to resize. Here is a very quick example

void resize()
{
  if(numOfElementsInArray == sizeOfArray)
  {
    ArrayType * arr = new ArrayType[sizeOfArray*2]; // Allocate a double size array
    for(int i=0;i<sizeOfArray;++i)
      currentArray[i] = arr[i];
    delete [] currentArray; // Free memory in old array
    currentArray = arr; // Set the array to our new one
    sizeOfArray *= 2; // Double the size
  }
}

NOTE: The example above does not take into account space complexity; that said, if you have 5000 elements, and remove all but 5, this method with not shrink it (which is probably what you will want to do for all practical purposes)

Answer 3

Your code appears to be almost correct, except for two things:

1. keyframes needs to be a keyframe* rather than a keyframe[]
2. You forgot to delete the memory you allocated

Answer 4

That is incomplete type. In C++, array must be provided with size, and the size must be known at compile time itself.

You're using new, with which you should be using pointer.

struct keyframe_file {
    const int num_views;
    const int num_keyframes;
    keyframe *keyframes;
};

But std::vector<keyframe> is still a better choice, as @DeadMG already suggested.

By the way, the first two members are const in the struct, that means, they cannot be assigned value, as you're doing in your code. They must be initialized with values you want them to hold. That implies, now with vector, you've to include a constructor, to initialize the struct, as the struct is no more a POD.

struct keyframe_file {
    const int num_views; //const member
    const int num_keyframes; //const member
    std::vector<keyframe> keyframes;

    keyframe_file(int nviews, int nkeyframes) 
    : num_views(nviews), num_keyframes(nkeyframes), keyframes(nkeyframes){}
};


keyframe_file my_file(1,6); //done!

Answer 5

The suggested "Vector" is they safest way to do it.
But if it is only about making your code work (without resizing and stuff) the following should be working:

#include <iostream>

using namespace std;

struct keyframe {
    bool a;
    int b;
    int c;
};


struct keyframe_file {
    const int num_views;
    const int num_keyframes;
    keyframe* keyframes;
};


int main()
{
    keyframe_file my_file = {1, 6};  // initialization needed bcause of 'const int'

    my_file.keyframes = new keyframe[my_file.num_keyframes];

    for (int i = 0; i < my_file.num_keyframes; i++)
    {
        my_file.keyframes[i].a = true;
        my_file.keyframes[i].b = 5 + i;
        my_file.keyframes[i].c = 9 - i;
    }
    return 0;
}

somewhere in your code, when you are done using the array you have to call delete [] my_file.keyframes; as already mentioned.

Answer 6

Use pointers and apply to your structure!

int *p;
p = new int;

---

#include <iostream>
using namespace std;

struct keyframe {
    bool a;
    int b;
    int c;
};


struct keyframe_file {
    const int num_views;
    const int num_keyframes;
    keyframe *keyframes;
};


int main() {
    keyframe_file my_file;
    my_file.num_views = 1;
    my_file.num_keyframes = 6;

    for (int i = 0; i < my_file.num_keyframes; i++){
         my_file.keyframes = new keyframe; //<---
    }

    my_file.keyframes[0].a = true;
    my_file.keyframes[0].b = 5;
    my_file.keyframes[0].c = 9;

    return 0;

}

Answer 7

There's a basic rule when using dynamic arrays in c++, especially when using it inside structs or classes, and it's to delete what you no longer need.

If you want to make your struct dynamic, it's easy, just replace the [] with * and the array will become dynamic, but it's not over yet, there is a lot of work.

You have to construct the array and destroy it, and destroying it is possible and useful only with destructors, like this:

struct keyframe_file
{
    const int num_views;
    const int num_keyframes;
    keyframe* keyframes;

    ~keyframe_file() // this is the destructor
    {
        delete[] keyframes;
    }
};

Yet even that code isn't going to work at all, since you are assigning values to constants in variable my_file after creating it, it's illegal in c++, you should then use classes instead.

Using classes with dynamic arrays is very easy and interesting and makes your code very good, you don't have to know too much to do that, just learn what is a constructor, an initializer, destructor, private and public and go on with the following code:

#include <iostream>

using namespace std;

struct keyframe
{
    bool a;
    int b,c;
};

class keyframe_file
{
public:
    keyframe_file(int NV, int NKF):num_keyframes(NKF),num_views(NV)
    {
        keyframes = new keyframe[num_keyframes];
    }
    ~keyframe_file()
    {
        delete[] keyframes;
    }
private:
    const int num_views;
    const int num_keyframes;
    keyframe* keyframes;
};

int main()
{
    keyframe_file my_file(1,6);
    return 0;
}

This code works very well, it allows you to assign value to the constants num_views and num_keyframes for one time when creating the object (variable) my_file.

Remember, you are a C++ programmer, be proud of that, and use classes instead of structs and dynamic arrays instead of static ones.

Hope that's useful.