Extending dynamic memory allocation?
Here's an example situation I think would best describe what it is I want to do:
Allocate a dynamic array of size i (some int). Then, when that capacity is reached, double the size of that array. I am interested in some kind of "in-place" allocation solution so the old array could simply have more memory allocated to it rather than having to create a new array, copy all the elements over, then deleting the old array.
Is this possible? I know there is a vector class, but I think it doesn't do this kind of size extension, and if it does, I'd still be interested in how it worked.
thanks in advance!
Allocate a dynamic array of size i (some int). Then, when that capacity is reached, double the size of that array. I am interested in some kind of "in-place" allocation solution so the old array could simply have more memory allocated to it rather than having to create a new array, copy all the elements over, then deleting the old array.
Is this possible? I know there is a vector class, but I think it doesn't do this kind of size extension, and if it does, I'd still be interested in how it worked.
thanks in advance!
I don't believe it can be done. When you allocate a new array you have no choice but to delete the old one and redirect your old pointer to the new one after copying the elements over.
I would suggest you use vector. Vectors are infinitely expandable (in theory of course; nobody has infinite memory). Elements in a vector can be added onto it at will. Arrays are a fixed size.
Review the references on vectors in this website and you will see a rundown of the function (I believe it was push_back?) to perform this task. In general vectors are more efficient than arrays and easier to work with (although you still need to understand arrays to read other people's source code).
I would suggest you use vector. Vectors are infinitely expandable (in theory of course; nobody has infinite memory). Elements in a vector can be added onto it at will. Arrays are a fixed size.
Review the references on vectors in this website and you will see a rundown of the function (I believe it was push_back?) to perform this task. In general vectors are more efficient than arrays and easier to work with (although you still need to understand arrays to read other people's source code).
So does Vector dynamically grow the array by re-allocation, copy, then deleting the old array? Sigh... I was hoping there was a solution that allowed me to have a self-expanding array that didn't have to do that whole time consuming processes. Thanks for the reply!
Heavens no, that would be disastrously inefficient.
What vectors do has something to do with their implementation.
The advantage of a vector is that, like an array, it has random-access capabilities. To maximize the speed of random access, all the vector's elements are stored contiguously - next to each other - in memory. Therefore you can figure out where the elements are without needing to follow the elements in between (where as in the STL list class, you cannot perform random access).
Because the elements must be stored contiguously, a vector, upon creation, reserves some space in which it will instantiate the elements you create. Not all of this space is actually occupied by the vector, but all of it *can* be. At the point where the vector's current size would exceed the reserved space, the vector is forced to reallocate a larger amount of space (how much larger depends on the implementation) and move the entire set of elements into this space, plus the element(s) that pushed it over the brink, and then destroy the original vector. However, the strategy with which the vector "grows" is designed to render it as efficient as possible. This minimizes the memory-intensive task of reallocation, which overall makes the vector's contiguous storage and random-access speed worth that occasional incurrence of memory cost. (In general, of the sequential containers vector is the most useful and most suited to various tasks.)
As I noted above, you can add elements to a vector at will and it will manage the space for you. You do not need to personally reallocate the container (although you may if you so choose; there is a function for that purpose) to make sure it has room for the elements you will instantiate.
What vectors do has something to do with their implementation.
The advantage of a vector is that, like an array, it has random-access capabilities. To maximize the speed of random access, all the vector's elements are stored contiguously - next to each other - in memory. Therefore you can figure out where the elements are without needing to follow the elements in between (where as in the STL list class, you cannot perform random access).
Because the elements must be stored contiguously, a vector, upon creation, reserves some space in which it will instantiate the elements you create. Not all of this space is actually occupied by the vector, but all of it *can* be. At the point where the vector's current size would exceed the reserved space, the vector is forced to reallocate a larger amount of space (how much larger depends on the implementation) and move the entire set of elements into this space, plus the element(s) that pushed it over the brink, and then destroy the original vector. However, the strategy with which the vector "grows" is designed to render it as efficient as possible. This minimizes the memory-intensive task of reallocation, which overall makes the vector's contiguous storage and random-access speed worth that occasional incurrence of memory cost. (In general, of the sequential containers vector is the most useful and most suited to various tasks.)
As I noted above, you can add elements to a vector at will and it will manage the space for you. You do not need to personally reallocate the container (although you may if you so choose; there is a function for that purpose) to make sure it has room for the elements you will instantiate.
Last edited on
That's what I mean, when the vector capacity is reached it must re-allocate a new block of memory that's bigger. It doesn't just allocate memory at the end of the vector assigned memory block and "append" it to that vector.
Well of course it can't, that defeats the purpose of the vector.
The idea is that all the elements are stored in one block of memory, next to each other. That's why the random access is fast. If you just slapped some block of memory onto the end why not just go use an std::list and slap another block of memory on for every element?
The idea is that all the elements are stored in one block of memory, next to each other. That's why the random access is fast. If you just slapped some block of memory onto the end why not just go use an std::list and slap another block of memory on for every element?
That's because, in general, you cannot just allocate more memory at the end of any existing array of memory. Memory tends to get very fragmented, especially so on modern OSes. You either allocate everything you could possibly need up front, or you deal with allocate/copy as it occurs in vector. Even with custom allocators, you have to, in essence, allocate everything you need and assign it to the allocator. Basically you are dealing with a fundamental reality of modern operating systems and how heap memory allocation works in general, rather than any language issue.
You might be interested in http://www.sgi.com/tech/stl/Vector.html , especially footnotes 2-5.
The wikipedia article on malloc is a pretty good place to start for understanding memory allocation schemes.
You might be interested in http://www.sgi.com/tech/stl/Vector.html , especially footnotes 2-5.
The wikipedia article on malloc is a pretty good place to start for understanding memory allocation schemes.
Sorry I didn't phrase my question very well, but I think you've answered my question with how allocators work. Thanks.
Topic archived. No new replies allowed.