ICQ Number : 120585863
E-mail:
laextr@icqmail.comIs it possible?
Author
It is possible to enlarge your dynamic array without having to copy the data?
I mean like usually when you enlarge an array you had to create the larger array, copy all the values from the current array to the new array and delete the old array.
// Last Attacker \\---=( LA )=---// LA Extreme \\
Sometimes. Maybe. This depends on your compiler, how you allocated the memory, and the state of the heap at runtime.
For arrays allocated by malloc(), using _expand() will enlarge the array if there is free space surrounding the memory block without copying the data, but this only works for program that use the MSVC runtime. (edit: actually now that I think of it, I think Borland C++ also implements _expand(). )
If you use HeapAlloc() to allocate memory, you can use HeapReAlloc() with the HEAP_REALLOC_IN_PLACE_ONLY flag, to attempt to resize the memory block in place.
And I stress that neither of the mechanisms are guaranteed to succeed. If there is memory allocated right after the array you want to resize, then it's impossible to expand the memory block in place, and you'll have to copy the array.
[edited by - SiCrane on April 20, 2004 11:53:02 AM]
For arrays allocated by malloc(), using _expand() will enlarge the array if there is free space surrounding the memory block without copying the data, but this only works for program that use the MSVC runtime. (edit: actually now that I think of it, I think Borland C++ also implements _expand(). )
If you use HeapAlloc() to allocate memory, you can use HeapReAlloc() with the HEAP_REALLOC_IN_PLACE_ONLY flag, to attempt to resize the memory block in place.
And I stress that neither of the mechanisms are guaranteed to succeed. If there is memory allocated right after the array you want to resize, then it's impossible to expand the memory block in place, and you'll have to copy the array.
[edited by - SiCrane on April 20, 2004 11:53:02 AM]
Author
Ok, cool! I thought it might be something like that, but I don''t think I''ve heard of the _expand() function before.
Thanks
// Last Attacker \\---=( LA )=---// LA Extreme \\
Thanks
// Last Attacker \\---=( LA )=---// LA Extreme \\
ICQ Number : 120585863
E-mail:
laextr@icqmail.com
Try realloc().
e.g.
void *foo = malloc(100);
[ fill foo ]
foo = realloc(foo, 200);
...
[edited by - Nurgle on April 20, 2004 2:39:48 PM]
e.g.
void *foo = malloc(100);
[ fill foo ]
foo = realloc(foo, 200);
...
[edited by - Nurgle on April 20, 2004 2:39:48 PM]
Under C++ would something like placement new do the same thing?
"That''s not a bug, it''s a feature!"
--me
"That''s not a bug, it''s a feature!"
--me
Placement new just constructs an object in the memory location specified, doesn''t allocate memory.
Typically, this doesn't work. It doesn't depend on the compiler, or library, or phase of the moon: it depends on the layout of your heap.
If you malloc() a block of 6k, and the library then allocates the next block 8k from the start of the allocated block, then you'd have 2k of expansion room. If you try to expand more than that, it'll fail, or the library will move/copy the data (realloc() does this). If you allocate a smaller block (say, 1.5k), the library may fill in the gap between your 6k block and the next block, and suddenly there's no free space for you to expand into.
Thus, don't design anything that relies on being able to preserve the address of array elements, while growing the array. Instead, you can use a list of arrays, where, to get to the Nth element, you skip past sub-arrays until you get to the array that contains the index you want. If you make each sub-array twice the size of the previous sub-array at the point where you need to expand, then you'll quickly find the right item, so the time to index wouldn't be much worse than constant time anyway -- at the cost of wasting up to 67% of your space in the worst case.
You could also use an array of pointers, and remember the pointer value, rather than the address of the array element. Or, if you only need iteration, not indexing, you can use a linked list, where the objects don't move around.
Last, if you need objects that stay, and efficient indexing, and little storage waste, you can use some tree structure, such as a heap, an AVL tree, a skip list, or a std::map<> with the index as your key. This turns indexing into a O(log N) operation instead of O(N), but it solves all those other pesky problems. Ordered iteration is very efficient in these trees. If you don't need ordered iteration, just fixed items and fast indexing and little waste, you might also want to try a hash table, hashing index -> element, although that's not very different from an array-of-pointers.
[edited by - hplus0603 on April 20, 2004 7:03:57 PM]
If you malloc() a block of 6k, and the library then allocates the next block 8k from the start of the allocated block, then you'd have 2k of expansion room. If you try to expand more than that, it'll fail, or the library will move/copy the data (realloc() does this). If you allocate a smaller block (say, 1.5k), the library may fill in the gap between your 6k block and the next block, and suddenly there's no free space for you to expand into.
Thus, don't design anything that relies on being able to preserve the address of array elements, while growing the array. Instead, you can use a list of arrays, where, to get to the Nth element, you skip past sub-arrays until you get to the array that contains the index you want. If you make each sub-array twice the size of the previous sub-array at the point where you need to expand, then you'll quickly find the right item, so the time to index wouldn't be much worse than constant time anyway -- at the cost of wasting up to 67% of your space in the worst case.
You could also use an array of pointers, and remember the pointer value, rather than the address of the array element. Or, if you only need iteration, not indexing, you can use a linked list, where the objects don't move around.
Last, if you need objects that stay, and efficient indexing, and little storage waste, you can use some tree structure, such as a heap, an AVL tree, a skip list, or a std::map<> with the index as your key. This turns indexing into a O(log N) operation instead of O(N), but it solves all those other pesky problems. Ordered iteration is very efficient in these trees. If you don't need ordered iteration, just fixed items and fast indexing and little waste, you might also want to try a hash table, hashing index -> element, although that's not very different from an array-of-pointers.
[edited by - hplus0603 on April 20, 2004 7:03:57 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
