Equivalent of C's realloc() in C++

[bintom]

Is there any equivalent of C's realloc() in C++?

Bintom

 

[Johannes Schaub (litb)]

Is there any equivalent of C's realloc() in C++?

If you ask about a class-aware realloc.

std::vector<string> a(100); // malloc(100*sizeof(string))
a.resize(200); // realloc(a, 200 * sizeof(string))

 

[bintom]

C++ inherits realloc() from C

/Leigh

OK, realloc() may be used, but then there would be no need for the
'new' operator when malloc() was already available.

Bintom

 

[Vladimir Jovic]

OK, realloc() may be used, but then there would be no need for the
'new' operator when malloc() was already available.

They are not doing the same thing. new is calling the constructor, while
malloc() doesn't

 

[James Kanze]

Is there any equivalent of C's realloc() in C++?

std::vector<>::resize. With the advantage, of course, that it
actually works, regardless of the object type.

 

[Juha Nieminen]

std::vector<>::resize. With the advantage, of course, that it
actually works, regardless of the object type.

Note that, depending on the underlying implementation and on the
current memory allocation layout, realloc() may in some cases be
much more efficient than resizing a vector because it may be able
to skip copying the existing data (by simply expanding the existing
memory block, if there is room).

There is no such functionality with 'new' in C++.

 

[Johannes Schaub (litb)]

Note that, depending on the underlying implementation and on the
current memory allocation layout, realloc() may in some cases be
much more efficient than resizing a vector because it may be able
to skip copying the existing data (by simply expanding the existing
memory block, if there is room).

There is no such functionality with 'new' in C++.

There is such functionality with `std::vector<>`. The capacity of a vector
is not required to be less than any specified number, as far as I know. So
if the capacity of a vector is N > size(), then resizing to M <= N does not
require copy constructor calls either

 

[Balog Pal]

"Johannes Schaub (litb)" <[email protected]

There is such functionality with `std::vector<>`. The capacity of a vector
is not required to be less than any specified number, as far as I know. So
if the capacity of a vector is N > size(), then resizing to M <= N does
not
require copy constructor calls either

And a good quality implementation certainly has special access to the memory
manager to ask 'expand in place or leave alone', and not limited to call
actual resize() like a handwritten array class would.

 

[Howard Hinnant]

"Johannes Schaub (litb)" <[email protected]



And a good quality implementation certainly has special access to the memory
manager to ask 'expand in place or leave alone', and not limited to call
actual resize() like a handwritten array class would.

Actually a good quality implementation has no such access. vector<T,
A> must get all of its memory from A, in general a user-supplied
allocator. So it can only get memory via the allocator API. You
might argue that at least vector<T, std::allocator<T>> could be
specialized to access a lower-level memory manager, but again we're
foiled. std::allocator<T> is required to get its memory via new. And
if it doesn't, that is detectable because new can also be user-
supplied. Now we're down to vector trying to detect at link time or
at run time if new has been overridden. It is at this point that
every implementor I know of has given up on this idea. At this time,
no implementation of vector I'm aware of has any magic under the hood
that can't be written in portable C++.

At least two people have attempted to adjust the allocator API to
allow vector to ask the right questions, but all attempts to date have
failed:

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html

So this functionality will not be in C++0x. The only way it will be
in C++1x is if there is an overwhelming number of people asking their
national body representatives for it, combined with a sufficient
number of volunteers to write the proposals, implement them, get real
world experience with them, and attend the standards meetings year
after year to champion the issue. It is not an impossible task. But
neither is it easy.

The first difficult task is just convincing C++ programmers that
vector::resize (as implementable today) actually is sufficiently sub-
optimal to matter.

-Howard

 

[Juha Nieminen]

The first difficult task is just convincing C++ programmers that
vector::resize (as implementable today) actually is sufficiently sub-
optimal to matter.

I'd say that the practical situations where realloc() can increase the
size of the allocated block in-situ (ie. simply by expanding the existing
allocated block, thus being able to skip copying any data) are really
rare. Perhaps if you need to call realloc() many times in succession,
and the memory block is (or ends up being, before the last realloc()
call) at the end of the current heap.

If such a situation is an essential part of some program, it might be
worth considering using std::deque instead (which expands without the
need to copy data around).

 

[Howard Hinnant]

  I'd say that the practical situations where realloc() can increase the
size of the allocated block in-situ (ie. simply by expanding the existing
allocated block, thus being able to skip copying any data) are really
rare. Perhaps if you need to call realloc() many times in succession,
and the memory block is (or ends up being, before the last realloc()
call) at the end of the current heap.

<shrug> My measurements show up to a factor of 2x increase in
performance. Note that is <em>up to</em>. You certainly don't always
get that. Whether that is significant or not depends on your
application. Some will few this opportunity as huge. For others the
benefit does not outweigh the considerable cost (changing allocator
API and getting 1 if not not 2 committees to agree). While I think C+
+ expand-in-place is a good idea, I'm afraid I fall into the latter
camp. Though if someone picks up the torch and brings it to a
committee vote, I'd most likely vote in favor of it, providing the
proposal had the necessary backwards compatibility built in (which is
entirely possible).

  If such a situation is an essential part of some program, it might be
worth considering using std::deque instead (which expands without the
need to copy data around).

std::deque is a very interesting data structure. For all but the
rarest of applications I consider it suboptimal. A circular buffer
that is capable of geometric reallocation when size exceeds capacity
nearly always beats an array of arrays in performance. It is only
when you need all of push_front, push_back and pointer/reference
stability that std::deque really shines. A circular buffer gives you
push_front/back without pointer/reference stability, and would also
benefit from inplace expansion. But still beats a deque even without
inplace expansion if the pointer/reference stability isn't required
(in my experience).

-Howard

 

[Martijn van Buul]

* James Kanze:

std::vector<>::resize. With the advantage, of course, that it
actually works, regardless of the object type.

With the disadvantage, of course, that it *always* copies, whereas realloc
may not have to.

Some people tend to get a bit short-sighted here. Yes, a std::vector<>::resize
will get the job done, but that's doesn't mean that realloc won't be missed.

 

[Marc]

std::deque is a very interesting data structure. For all but the
rarest of applications I consider it suboptimal. A circular buffer
that is capable of geometric reallocation when size exceeds capacity
nearly always beats an array of arrays in performance. It is only
when you need all of push_front, push_back and pointer/reference
stability that std::deque really shines. A circular buffer gives you
push_front/back without pointer/reference stability, and would also
benefit from inplace expansion.

You may still need to move most elements when doing inplace expansion
(just checking that I understand the data structure you describe).

But still beats a deque even without inplace expansion if the
pointer/reference stability isn't required (in my experience).

Something like the boost circular buffer, with on top insert operations
that compare size() to capacity() before a push_back and if necessary
double the capacity. Strange that boost doesn't provide such an adaptor.

 

[BGB / cr88192]

They are not doing the same thing. new is calling the constructor, while
malloc() doesn't

one can use malloc and manually call the constructor if they want...

although, presumably in cases where one was using malloc/realloc, would not
be the same as when using new.

 

[Howard Hinnant]

Howard Hinnant  wrote:

You may still need to move most elements when doing inplace expansion
(just checking that I understand the data structure you describe).

I believe you understand it. std::rotate would conveniently and
efficiently put the elements in the right place after an inplace
expansion:

std::rotate(begin_buffer_, first_element_, begin_buffer_ +
size());

-Howard