Shrinking An Array After Creation

[Nick]

I have an array of, say, 3000 items created as such in C++:
int myArray[3000];

Is there a way, after creating this variable, to reduce the memory usage from 3000 ints to only 1500 or any other number? I thought maybe a delete function but those are for pointers, right? I couldn't think of a way to do this.

The reason I would like to do this is for a class I'm working on. The class holds the maximum number of items that are allowed to be stored. After initialization, it usually never needs all the spaces. I just want to free up the extra memory for use for other variables.

[BinarySpike]

In C: no

In C++: probably not

[Nick]

:) haha. Ok. That's what I figured. Oh well. Hopefully I don't waste too much memory. Hopefully I'll just figure out how to use fewer items in the array.

[Josh]

Why not just dynamically allocate it?

[LongJumper]

int yourSize = 100;
int* yourArray = new int[yourSize];
int resizeSize = 50;
int* tempArray = new int[resizeSize];

for(int i = 0;i<resizeSize;i++)
tempArray[i] = yourArray[i];
delete[] yourArray;
yourArray = new int[resizeSize];
for(int i = 0;i<resizeSize;i++)
yourArray[i] = tempArray[i];
delete tempArray;

doStuff(yourArray);

delete[] yourArray;

[Malarkey]

You can't use an STL vector?

[codemattic]

lets say at run time you determine you need "X" ints - use the "new" and "delete" operator:


int* myArray = new int[X]; // Allocate memory for the array
//
// do stuff with myArray
// dont access past myArray[X-1] or trouble ensues
//
// when you are done with the array
delete [] myArray;

[kelvin]

Once you exit the current function that array will be popped off the stack, automatically be resized to 0, and recycled for you! Twice as much work done for you and all you have to do is call 'return; ' :D Then, whenever you want to quit your program, just reference that array again and get a segmentation fault, the user doesn't even have to click quit. Oh modern technology, the utility never ends!

[Duane]

just create a pointer, then malloc it when you know the size, if that's what your looking for. If you have objects, just create a new array with the appropriate size, then memcp(is that right?)the old one into the new one.

[codemattic]

or if your array will grow and shrink use a STL vector.

[codemattic]

lol - looks like we all typed in the same answers at the same time.

[Dan Potter]

Heh, response-blitz :)

To directly answer your question, C++ objects have a fixed size at compile time and that can never change at runtime. You can cheat a little with structs in C by doing this:

struct foo {
int baz;
int bar[0];
}

And then allocate it with malloc(sizeof(foo) + sizeof(int)*numelems). That won't work with C++ objects (or structs with methods) because you have things like the vtable in there somewhere.

I second the STL (std::vector) recommendation :)

[Andrew]

You could also use a single or doubly linked list... depending on what you need to do.

Linked lists are more memory efficient than arrays, but at the expense of performance (since you need to iterate through the list to get to the item you want, and also have to make lots of malloc calls). So it all depends on what you intend to do with it.

Here's a doubly linked list:

typedef struct Hanger {
Hanger *prev;
Hanger *next;
int data; // could alternatively be a pointer to some malloc'ed data
} Hanger;

In this implementation, the first an last Hangers don't hold data. This makes the code much cleaner. Initially, the first Hanger in the linked list would have prev set to NULL, and next pointing to last Hanger. The last Hanger's prev would point to the first Hanger, and its next would be set to NULL.
To insert a new item, malloc a Hanger struct, iterate to where you'd like to put it in the list, the adjust its prev/next pointers, as well as those of the 2 adjacent Hangers.

Of course, the above leaves out a lot of implementation details, but the basic concept of a doubly linked list is there.

And remember, linked lists are built with plain C code, so they're compatible with C, C++, and objective-C :)

[OneSadCookie]

Linked lists are more memory efficient than arrays

I think you mean "much less memory-efficient than arrays".

By the time you've got the extra link pointers, and all the extra overhead of having many malloc blocks, you're looking at a /lot/ more memory than a correctly-sized array.

And that's before we start talking about the horrendous inefficiency and cache behavior in linked lists.

They do have their place, but it's a long, long time since I've found a home for them in any of my code.

[Steven]

I think the next obvious question here is: do you REALLY need to resize your array? Leaving half the array at worst will only waste a kilobyte or two for the duration of your function, and you can probably afford that with a modern computer :p

[Nick]

When I originally posted, it was while developing my mesh class where some models could have 5000 vertices and others only 20. I wanted to be able to get rid of those extra 4980 vertices (each containing three floats) to free up memory in the computer. I'm getting into BlitzMax more now so I may just use that where I can use slices to shrink arrays like this:
myArray = myArray[..myArray.length-1]

[Dan Potter]

Your mesh class could also have had this:

std::vector<Vertex> vertices;

On init you could specify the exact number of vertices you'd need, or you could max it out to begin with:

vertices.resize(5000);

And when you want to chop off the extras:

vertices.resize(vertices.size() - 1);

STL is hella nice. :)

(disclaimer: that's all off the top of my head, I think the method names are right...)

[TomorrowPlusX]

Allow me to second STL. If you're writing in C++ and aren't using STL, you're wasting your time, and are probably creating more subtle bugs than you can shake a stick at.

[Andrew]

I think you mean "much less memory-efficient than arrays".

I mean that if you know you're going to have somewhere between 0 and 10000 items, and you end up with only 100 items, a linked list will have a smaller memory footprint than an array of length 10000.

[OneSadCookie]

That's certainly true, but if you want an array with somewhere between 0 and 10000 items the last thing you would do would be allocate space for 10000 and waste 99% of it.

As others have pointed out, C++ provides std::vector, but doing something in C with realloc is dead easy too.