What is realloc() equivalent of new?
What is realloc() equivalent of new?
Learn C++ (C++ Books, C Books, FAQ, Forum Search)
Code painter latest version on sourceforge DOWNLOAD NOW!
Download FSB Data Integrity Tester.
Siavosh K C
There is none (not as directly, anyway). You could read Why doesn't C++ have an equivalent to realloc()?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
to the best of my knowledge, realloc() changes the size of the memory block pointed to by a pointer. Can you give an example case where "renew" can be used?
Exactly where realloc can be used.Can you give an example case where "renew" can be used?
If new is the replacement of malloc() it should has a replacement for realloc(). Example:
Good link laserlight!Code:int *intArr = new int [200]; //We need a bigger array; intArr = renew (intArr) [400];
Learn C++ (C++ Books, C Books, FAQ, Forum Search)
Code painter latest version on sourceforge DOWNLOAD NOW!
Download FSB Data Integrity Tester.
Siavosh K C
in that case I would use a std::vectorCode:int *intArr = new int [200]; //We need a bigger array; intArr = renew (intArr) [400];
Since "new" doesn't quite do the same thing as "malloc"[1], what do you expect "renew" to do?
If you consider something like this:
Should we call the constructor for blah 100 times or 200 times in the second instance? What do we do with the content of the first 100 instances of *a - allocate new ones, copy the existing ones or something else?Code:class blah { blah() { a = new int[20]; .... } private: int *a; }; ... class blah *p = new blah[100]; .... p = renew blah[200]; ....
If you have a need to "resize" your datablocks, why not allocate them in "chunks" so that you get some spare size left over, and then fill that out until you get to the "size" and then do your own "renew" by using allocating a new array (or whatever it is you're dealing with) and then copying the old content into the new one.
As for how to pick a "slightly larger size", perhaps picking the next (1 << n) that is bigger than the reuqested size.
Using a fixed addition works well if you often only add a little bit, but if you don't know what size you're going to grow the block of memory to, then you may find that a "double it each time" is a better way [2].
[1] It's certainly possible to implement "malloc" by calling "new", but not the other way around.
[2] A collegue of mine worked on a project where someone used the method of "adding a fixed size more" (I think 4K) each time the buffer was too small. It started out at 4K and grew to 16MB in his case. Growing that at 4K at a time is PAINFULL (lots of memory copying). By using the "double the size when it's not large enough", he could reduce the runtime of that particular app by a factor of 10 or so.
--
Mats
If that is exactly what you're doing in your code (or at least something that is just a plain array of some data with no "class" or "complex content"), then you could actually just use malloc/realloc. Unless of course where you're using this code FORBIDS use of classic C-functionality. Just remember to NOT use "delete" when you de-allocate the memory, use free instead.
As I explained in the previous post, "renew" isn't quite so easy to implement for the more complex scenarios. For trivial "stuff", you could implement something like this:
But this is NOT the same as using new at all. Note also that we're assuming that it's GROWING - allowing the reducing of size is needs more code.Code:void *renew(void *ptr, size_t origsize, size_t newsize) { // no error checking here - it should be done. void *p = new char[newsize]; memcpy(p, ptr, origsize); return p; }
--
Mats
This is exactly why renew would be useful. Renew would only reconstruct the objects that it needs to. This would be like vector, except that resizing the vector beyond capacity does not necessarily require the vector to copy elements if the operating system can spare the extra space after the internal dynamic array. It leaves the task of whether to copy the element in the bigging over or not up to the operating system, which knows more about the available memory than the program.
Becomes sometimes you need sequential memory. Vectors are sometimes preferred over deques. Vector and vector like objects would benefit from renew.If you have a need to "resize" your datablocks, why not allocate them in "chunks" so that you get some spare size left over, and then fill that out until you get to the "size" and then do your own "renew" by using allocating a new array (or whatever it is you're dealing with) and then copying the old content into the new one.
That's the problem. Increasing the capacity of the vector by a little bit should not require copying every element over most of the time.As for how to pick a "slightly larger size", perhaps picking the next (1 << n) that is bigger than the reuqested size.
Using a fixed addition works well if you often only add a little bit, but if you don't know what size you're going to grow the block of memory to, then you may find that a "double it each time" is a better way [2].
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
Most operating systems don't do realloc natively - it's done in the C-library, and it's done by looking at the internal data in the heap, to see if there's enough space to expand it [e.g. we asked for a block of 4K, but the heap contained one that is bigger, so the "rest" of that block is free - realloc can just change the size of the block. If it's unable to expand "in situ", it does a fresh malloc and copies the data anyways].
It's just a case of "where do you solve the problem" as well as "how do you know what needs to be done". I'm not clued up enough about how vector is implemented, but I'm pretty sure it doesn't specifically say that you couldn't allocate "spare area" whenever it needs to grow, and thus only actually grow it when it runs out of spare area - selecting increasingly larger spare area when it's growing larger. Not saying this is how vector is implemented at the moment, but that it COULD BE done. And it certainly can be done without using "renew".
Becomes sometimes you need sequential memory. Vectors are sometimes preferred over deques. Vector and vector like objects would benefit from renew.
That's the problem. Increasing the capacity of the vector by a little bit should not require copying every element over most of the time.
--
Mats
What I am curious about is whether it is possible to write an allocator for vector that tries to grow the vector without copying existing elements to a newly allocated block unless absolutely necessary, keeping in mind that the vector's elements are expected to be contiguous. It does not sound possible to me, but then I am a beginner at allocators and sophisticated memory management in general.This is exactly why renew would be useful. Renew would only reconstruct the objects that it needs to. This would be like vector, except that resizing the vector beyond capacity does not necessarily require the vector to copy elements if the operating system can spare the extra space after the internal dynamic array. It leaves the task of whether to copy the element in the bigging over or not up to the operating system, which knows more about the available memory than the program.
That is precisely what vector is expected to do, hence the member functions capacity(), reserve(), resize() and size(). I believe some existing implementations do double the capacity when it is maxed out.I'm pretty sure it doesn't specifically say that you couldn't allocate "spare area" whenever it needs to grow, and thus only actually grow it when it runs out of spare area - selecting increasingly larger spare area when it's growing larger.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
Right, that's what realloc does. A renew function/operation would do the same thing but with constructors.
The OS may allocate 4K to the program. But the c++ code cannot directly access that 4K; it relies on calls to malloc, calloc, new, ext. Thus if you have a size 100 dynamic array, which uses objects with nontrivial constructors, and you want to increase the size by 1, there is currently no way to do it without copying the entire array over and deleting the old array. This is inefficient.
Vector itself can be implemented to work like realloc because there is no requirement that vector is written in c++ (as long as it behaves like it's written in c++). More to the point is how to write an more specialized version vector that uses realloc like functionality in c++ for our own purposes.It's just a case of "where do you solve the problem" as well as "how do you know what needs to be done". I'm not clued up enough about how vector is implemented, but I'm pretty sure it doesn't specifically say that you couldn't allocate "spare area" whenever it needs to grow, and thus only actually grow it when it runs out of spare area - selecting increasingly larger spare area when it's growing larger. Not saying this is how vector is implemented at the moment, but that it COULD BE done. And it certainly can be done without using "renew".
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
It's not possible. There were proposals to make it possible, but I don't know about their status.
In fact, doubling the capacity is required behaviour for push_back if the vector is full, and no implementation I know does anything different for other insertion functions.That is precisely what vector is expected to do, hence the member functions capacity(), reserve(), resize() and size(). I believe some existing implementations do double the capacity when it is maxed out.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
I don't repeat King Mir.
Don't you ever thought how vector grows?In that case I would use a std::vector
It is not good. Example:Using a fixed addition works well if you often only add a little bit, but if you don't know what size you're going to grow the block of memory to, then you may find that a "double it each time" is a better way [2].
You need to get some numbers from input. Initially ou make space for 100 items. But there are 122 items! If you double the allocation, you will have room for 200 items. 200 - 122 = 78
78 unit of memory is wasted.
Of course I can do my own renew if I could write the realloc function by myself!...then do your own "renew" by using allocating a new array (or whatever it is you're dealing with) and then copying the old content into the new one.
renew should first look at the memory allocated by the last new. If it has more room at its tail then that space will be allocated. In this case the pointer does not change. Else it should find a continous free space at the size we want and copy the contents of our array to this new location, delete the old array, return the address of this new location.
Learn C++ (C++ Books, C Books, FAQ, Forum Search)
Code painter latest version on sourceforge DOWNLOAD NOW!
Download FSB Data Integrity Tester.
Siavosh K C
There's no guarantee that the "behind the scenes" allocation isn't larger than what you need anyways. It's obviously not necessary to DOUBLE the allocation either - adding 50% or some other proportion would work too. If you grow by 25% at "time to grow", you'd end up with 125 items on the growth, and only waste 3 items of memory if you have 122 items acutally in use - but then you get 4 times as many copies if you grow many times.
It is the usual tradeoff between "memory and processing power" - you either waste CPU-cycles, but save memory or use less memory-space, but use more CPU-cycles. If you want to know exactly how many items you need, you could read your file twice, once to figure out how many items you have, and the second time to actually fill it in - that's probably not a good idea, but it could be done.
realloc also copies the data sometimes, and it's only because of "overallocation" in the first place that realloc is successfull without copying (or that you ONLY have one set of malloc/realloc, so your entire heap is able to grow whenever you realloc - this is unlikely to be the case in any decent-size C++ project, since C++ is very much oriented towards using dynamic memory).
Also, if you want to, you can implement your own new operator - either for ALL objects or for certain object types. With that, you could perhaps also add a functionality to support "renew" for simple cases. The complex cases still needs more knowledge of the data than you have available at that point.
--
Mats
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"