Storing Data of Unkown Length

Discussion in 'Game Development (Technical)' started by Roberto Molvado, Apr 9, 2015.

  1. Roberto Molvado

    Roberto Molvado New Member

    Joined:
    Dec 21, 2014
    Messages:
    3
    Likes Received:
    0
    Something I frequently run into is the following: imagine that in your code you evaluate a list of data, but you initially do not know the amount of values. So when your preallocate your array, you cannot set the exact size. In some programming language that is not much of an issue, as arrays can be (efficiently) dynamically resized. However, in C++ for instance, resizing arrays at run-time is a don't (right?).

    For example, I'm working on a piece of code that gets the names of all the files in a certain folder. I want these names in a string array, but the amount of files is not known.
    I can come up with two solutions:
    1) Run the code twice, the first time without saving the codes and just counting.
    2) Create a ridiculously large array and save the names immediately. Afterwards, the array could be resized to remove the empty elements.

    Which method would be better, that is, more efficient?
    The first one seems pretty solid, considering that with method #2 you sill have the risk of overloading your array and you allocate unnecessary memory.


    Any ideas?
    Thanks in advance!
     
  2. Sade

    Sade New Member

    Joined:
    Dec 4, 2014
    Messages:
    43
    Likes Received:
    0
    You need neither.
    You can make an array with a variable size by using the 'new' keyword.
    This allocates an array on the heap. You are also responsible for the removal of this array when you no longer need it though.
    You can do that by using the 'delete' keyword.

    You can read more about it here or google around. This is pretty standard stuff.
     
  3. stan

    Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    188
    Likes Received:
    0
    Typically in C++ you’d use an STL vector or list. You can also make your own list structure easily (vector requires a bit more work).

    Edit: not sure if I understood the question correctly. If you just want to fill ONE string with all the file names, then method 1 seems appropriate… It requires doing the work twice, but you’re not going to do that one million times per frame I suppose :).
     
  4. Gallacy

    Gallacy New Member

    Joined:
    Jan 5, 2015
    Messages:
    66
    Likes Received:
    1
    Hi Roberto,

    You need to read a bit about data structures. Today you don't need to worry about array resizing (which is a perfectly YES-YES, by the way - it is a very-very fast operation). Find a book on STL, learn C++ data structures and understand their application, pros and cons.

    Basically the choice depends on what you are trying to do with your data - is it quick inserts? Quick look-ups? Sequential reads? Ordered data? After you learn the data structures the choice will be obvious.

    In your case of reading list of files in a folder - from performance perspective - it doesn't really matter what you do - as even if you stream it to a remote database and read it back - it is still too quick for the user to waste your time optimising.

    When in doubt - use std::vector. You can think of it as a "resizable array" but with a few twists.

    One can argue that in 2015 use of "new" and "C-style array" is a last resort when no alternatives are available for some reason (very old compiler, for example).

    Cheers
     
  5. Roberto Molvado

    Roberto Molvado New Member

    Joined:
    Dec 21, 2014
    Messages:
    3
    Likes Received:
    0
    Thank you all for your replies.

    @Shade
    I know about allocating memory. That is why this is a problem. A regular array with a size that is not 'const' is not even possible.

    Now I do remember option number 3:
    3) Create a new array with a size that is one element larger than the old one and delete the old array.
    But it seems like a bad idea to create and delete thousands of arrays in an instance.

    @Stan
    I'll look into the C++ vectors
    I could store them all in one string, but that might not be possible in other cases of this problem.
     
  6. stan

    Original Member Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    188
    Likes Received:
    0
    Indeed, which is why vectors will allocate an array that is for example 50% bigger than the original, instead of adding only one element every time (I don’t know the exact algorithm for STL vectors, but 50% should work fine in general).
     
  7. Sade

    Sade New Member

    Joined:
    Dec 4, 2014
    Messages:
    43
    Likes Received:
    0
    @Roberto
    You're right that you can't allocate a regular array that way.
    The keyword 'new' however makes it possible to use a variable for the length of the array.
    It's wiser to use the vector or list instead though. Those are basically wrappers around the dynamic array I suggested.
     

Share This Page

  • About Indie Gamer

    When the original Dexterity Forums closed in 2004, Indie Gamer was born and a diverse community has grown out of a passion for creating great games. Here you will find over 10 years of in-depth discussion on game design, the business of game development, and marketing/sales. Indie Gamer also provides a friendly place to meet up with other Developers, Artists, Composers and Writers.
  • Buy us a beer!

    Indie Gamer is delicately held together by a single poor bastard who thankfully gets help from various community volunteers. If you frequent this site or have found value in something you've learned here, help keep the site running by donating a few dollars (for beer of course)!

    Sure, I'll Buy You a Beer