Thread: Ways to redimension an array ?

  1. #1
    Registered User Zeeshan's Avatar
    Join Date
    Oct 2001
    Location
    London, United Kingdom
    Posts
    226

    Ways to redimension an array ?

    Hi,
    I'm writing a 3D game. I need to be able to save variable no. of polygons in every sector. Hence, I think I will be storing them in some kind of list.
    Any recommendations/ideas?
    or may I create my own list class, for which i require to know how to redimensionalize an array/dynamically or whatever, without destroying the data it already contains?

    for e.g.

    if i have an array which has got five integers in it.

    int *a=new int [5];
    fill_all_elements_of_a();

    now if i want to store another integer in the same array ??? what do i do ?

    the proposed way should b quick .... plz help

  2. #2
    Ethereal Raccoon Procyon's Avatar
    Join Date
    Aug 2001
    Posts
    189
    You can use realloc() in C:

    Code:
    char * astring;
    astring = malloc(10);
    astring = realloc(astring, 20);
    I'm not sure how you'd do this in C++, other than simply copying the array contents to a different array and reallocating from scratch.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    One possibility is to do something like this:

    Use an array of pointers which begins at, say, 20 elements MORE than you initially need. Each element can be marked as "used" or "unused".

    So, you start off with an x+20 sized array -- x of these elements are used, and 20 are unused. To stop displaying an object, simply flag it unused. To add, search for an unused, delete the object (the whole array is pointers to objects which exist, even the unused ones) and set the pointer to point at your added object.

    If there are no unused elements remaining (i.e. you've filled all the array) expand the array by 20 elements; you then still have 19 more additions you can make before you need to expand it again.

    Rerember, array resizing is slow, so try to minimize how much of it you do.

    The other possibility is a doubly linked list, because so long as you have a pointer to the element to delete, you can do it very very fast, by simply altering the "next" pointer of the previous element, the "previous" pointer of the next element, and then delete the object you unlinked.

    Resizing an array is an O(N) operation -- so its speed is proportional to the number of elements. Resizing a doubly linked list, assuming you don't have to search the list for the element to remove, is constant time, so no matter how large your list is, it's equally fast.

    I'd recommend a doubly linked list. For searches, it's equally fast as an array, and for deletions and additions, it's much better. The only way a linked list is slower is in random access -- that is, it takes longer to access a particular element of a linked list if you're just choosing an element at random. For sequential access (i.e. accessing element 0, then element 1, then element 2, then element 3, etc.) each is equally fast.

    Being as you're probably going to want to iterate through all elements sequentially, it's equally fast.

  4. #4
    Former Member
    Join Date
    Oct 2001
    Posts
    955
    well, they said it, but you could also do a ReDim in VB, some people would want to kill me, but it's another way of doing it..

    Oskilian

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    164
    Who cares about VB?
    // Gliptic

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    If you're doing this in C++, then I think you need to look into the Standard Template Library (STL) vectors.

    I seem to remember someone mention that they act like arrays, and are extendable.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    But a caveat -- many Vector templates are NOT written with performance in mind. Each of them must be implemented in some fashion, usually as either an array or linked list, and some of them can be quite slow.

    Some, too, can be DECEPTIVELY slow, in that they may have tricks which makes it appear fast under certain conditions, but you may find the performance varies wildly in real usage.

    I recommend making your own classes if you're going to need high-performance operations -- it's the best way to understand exactly what speed/performance issues you will have in the final product.

    And, *any* implementation of a variable sized array has areas in which it gives good performance, and areas it has poor performance. Using one solution for all needs is a bad idea, because there is no single solution that is always optimal. Sometimes linked lists are the best way to do this, sometimes arrays are, and it all depends on HOW it will be used, as certain operations are faster/slower in certain implementations.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > many Vector templates are NOT written with performance in mind
    This might be true, it's certainly something to be aware of.
    What's worse is, changing compiler (or upgrading the same compiler) might change the balance.

    One of the advantages of C++, is that you can hide the detail of the implementation. For development, any implementation which works is good enough - in fact you might pick a slow one if it maximises the debug capabilities.

    > but you may find the performance varies wildly in real usage.
    Until the real use has been established by the implementation, and some performance measurements taken, its impossible to say what the best approach is.

    It might be the case that the existing STL is perfectly good enough for the actual use. Even if it isn't the best, it still might not be the performance hot spot. Either way, you've saved time and effort by not doing your own thing.

    But if this is a purely academic / hobby exercise, then no doubt implementing your own thing would be an interesting exercise in its own right.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    The one reason I still prefer to do most of this myself (unless I'm given the appropriate details of the underlying implementation) is that it is often hard to accurately test the performance of a system without knowing under what conditions it yields the poorest results.

    For example, I've implemented dynamically resizing arrays for which the first, second, ... , thirtieth additions all happened in constant time, and fast, but the 31st, 61st, 91st, etc. additions were much slower. For the application, in which I never expected to need 31 additions, this was fine -- but if I was adding hundreds of elements in standard usage, this implementation would have been quite poor.

    Now, if someone else happened to use this implementation of mine, it might be quite hard for them to identify whether this implementation was adequate for their needs. Had they tested only 20 additions, they'd think that the performance was high -- had they tested 200, they'd have a lower estimate of performance.

    The benefit of writing your own code is that you can adjust the implementation until the inefficient parts of the implementation become rarely used. You also have more direct control of the memory usage of the program. I could always have adjusted that implementation until I could add 2,000 elements before I'd come to a "slow step", but the memory usage would have been higher also.

    Canned solutions often work just fine for most cases, but you will rarely get the performance out of a canned solution that you can when you implement it yourself, because you know exactly what constraints you are operating under and can tailor the implementation to maximize performance.

    And, if you need performance, you have to test canned solutions especially carefully, and test them over the whole range of inputs that you expect, because sometimes you may find that a canned solution will work well over certain regions (like my array with 1-30 additions) but won't work as well over others.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. Inserting new member into array of structs
    By cathym in forum C Programming
    Replies: 6
    Last Post: 04-17-2005, 07:10 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM