Hello
How can I create an array with changing size?
Shuo
Printable View
Hello
How can I create an array with changing size?
Shuo
You can't. Use std::vector instead.
you can usefor dynamically creating a buffer of any size on the fly.Code:Buffer = new char[szBuffer];
but you can't change the size of an existing buffer, at least not that I am aware of...
True. There's no way to change the size of an existing array. The only way is to dynamically allocate, free, reallocate to change size, which is exactly what std::vector does for you.
There is in C. realloc() is a function that will resize an array to a larger size. It will try to expand the memory without moving the array if it can. Pointers passed to realloc() must have been allocated with malloc or calloc, so this optimization can be intrusive in C++, unless it is wrapped in a container. std:vector can never do this, but even if it did, it wouldn't be much of an optimization.Quote:
Originally Posted by klipseracer
But most cases that you need the array size to change, you should use std::vector or std::deque. Use std::deque if the array can decrease significantly in size, as std::deque is able to decrease the size of it's buffer.
Do exactly what? Try to expand the array without moving the array? That's what the vector does all the time and it is an important optimization.Quote:
std:vector can never do this, but even if it did, it wouldn't be much of an optimization.
From what I see the C++ Standard makes no mention of this, so that is not what vectors do (though if it is technically feasible, a standard library implementor might implement the vector to do it).Quote:
Try to expand the array without moving the array? That's what the vector does all the time and it is an important optimization.
Isn't this what the amortized constant time push_backs mean?
No, it does not. That means that in the long run, the complexity is constant time since the occasional linear time allocation of memory and copying over of elements becomes more and more rare.Quote:
Isn't this what the amortized constant time push_backs mean?
I know vectors create a new block of memory and copy all their elements to the new one, then delete the old block; but wouldn't it be possible for a vector to use realloc() and in-place new to try to keep the same piece of memory?
As you know, realloc isn't safe for C++ memory. Copy constructors for classes aren't called, for example.
Plus from what I understand realloc just tries to allocate a new block of memory if it can't expand the current one and move the data over.
std::vector must use the methods of the Allocator template parameter for its memory management. Since these don't include something realloc-like, it cannot use realloc.
That's why I said realloc and in-place new.Quote:
Originally Posted by Elysia
How would you propose that? Once you use realloc, the damage is done.
Yeah, I guess it couldn't use realloc() & placement new (I got the name wrong before) by default since some objects might rely on their own memory address internally... But maybe a custom allocator that uses realloc() & placement new would work if you know how the objects stored in it will handle a change of address behind the scenes.Quote:
Originally Posted by Elysia
Erm, by default... By default you should never use realloc in C++ since it can destroy objects or make them not work the way they should.
But sure, if you know the objects will be fine after using realloc, you can use it. No one is forcing you not to.
But the ideal solution (at least on Windows) would be to simply expand the virtual memory beyond the end of the array so moving isn't necessary (as I did with my CArray experiment).
Sure, if you know ahead of time the max size your vector will need, you'd ideally want to call v.reserve().
BTW, how can realloc() destroy objects? It doesn't know anything about objects. If it can't expand the current memory, it allocates new memory somewhere else and does a memcpy() from the old location to the new one.
Obviously that could cause some objects to barf if they rely on pointers to themselves and those pointers don't get updated when they were moved...
In any case, I doubt the performance benefit would be noticable in most cases.
It wouldn't destroy them per se, but it can certainly mess things up.
Take boost's shared_ptr, for example. It uses a reference count, yes? That means every time the copy constructor is called, it adds one. But if you copy it using memcpy, then it won't update the reference count.
Another example might be when an object does a deep copy in the copy constructor.
So realloc would screw up both of those type of objects. That's why it would be dangerous.
Even that turns out not to work. The vector is written to acquire the new lot of memory, then copy stuff across, and then release the old bit of memory. An allocator using realloc wouldn't know which bit of memory to resize, and even if it did, the vector would still try and copy from itself to itself and then destruct the original items which would actually destroy the new ones instead, screwing it up entirely.Quote:
Originally Posted by cpjust
Regardless, if you could use realloc with a vector, it wouldn't make any useful speed improvement anyway.
It's true that the realloc semantics are simply not safe for C++. However, a slightly different function would be safe. This function, let's call it exalloc, has the following semantics:
bool exalloc(void *current, size_t newsize);
Tries to extend the allocated block at current to newsize. If it's not possible to extend the block, it does nothing.
Arguments:
current: A pointer previously returned by malloc() or calloc().
newsize: The desired size, in bytes, to extend the block to.
Returns:
True if the block could be extended. The block at current now points to newsize valid bytes. False if the block couldn't be extended. Nothing has changed. No memory has been allocated or freed. No memory has been copied.
Notes:
This function behaves like the first part of realloc(). However, if it fails to extend the block in-place, it will not allocate a new block and copy the memory there. This makes it safe for memory containing C++ objects.
With this function, a dynamic array's push_back could look like this (NOT exception-safe!):
Code:void push_back(const E &e)
{
if(m_last == m_memend) {
size_t newalloc = (m_memend - m_first) * 2;
if(!exalloc(m_first, newalloc)) {
E *tmp = malloc(newalloc);
if(!tmp) throw bad_alloc();
for(E *s = m_first, *t = tmp; s != m_last; ++s, ++t) {
new (t) E(*s);
s->~E();
}
swap(tmp, m_start);
m_last = m_start + (m_last - tmp);
m_memend = m_start + newalloc;
free(tmp);
}
}
new (m_last) E(e);
++m_last;
}
Yes, that's exactly what I'd like to use instead of realloc()! But how exactly would you implement exalloc()? Is there a portable way to do it, or would you have to rely on OS API calls?
There's absolutely no way to implement it aside from implementing the entire malloc family yourself. It needs internal knowledge of the data structures malloc uses.
You could take an open-source malloc implementation and adapt it.
I think you're right.Quote:
Originally Posted by CornedBee
I love a challenge, so I tried to implement my own C++ Realloc() (for Windows), but alas I failed... It seemed to be going pretty well until I tried deleting the old memory, since there's no Placement Delete, and no generic way of calling a destructor in a template.
Here's my attempt:
Code:template <typename T>
T* Realloc( T* ptr, size_t oldSize, size_t newSize )
{
T* pNew = (T*)HeapReAlloc( GetProcessHeap(),
HEAP_REALLOC_IN_PLACE_ONLY,
ptr,
newSize );
if ( pNew == NULL )
{
cout << "pNew is NULL!" << endl;
pNew = (T*)HeapAlloc( GetProcessHeap(), 0, newSize );
if ( pNew == NULL )
{
throw std::bad_alloc( "No memory!" );
}
for ( size_t i = 0; i < oldSize; ++i )
{
new( &pNew[i] ) T( ptr[i] ); // Copy old value to new location.
delete &ptr[i]; // Destroy old value ??? No Placement delete?
}
HeapFree( GetProcessHeap(), 0, ptr );
}
else if ( pNew == ptr )
{
cout << "pNew == ptr." << endl;
}
else
{
cout << "pNew != ptr!" << endl;
}
return pNew;
}
t.~T() ought to work for explicit destruction. And I didn't know HeapRealloc had the IN_PLACE_ONLY option.
That's what I tried the first time, but the compiler didn't know what I was talking about.Quote:
Originally Posted by CornedBee
I think it's literally looking for a destructor named "~T()" if you do that.
What compiler do you use? What's your exact code? Because that's exactly the syntax used in The C++ Programming Language. (Well, it uses indirect member access, of course.)
I'll try it again when I get home, but it was something like:Quote:
Originally Posted by CornedBee
But T is a typename, so how would the compiler know what ~T() means? Or does it just expand the name like some kind of macro and then figure out if what it expanded to makes sense?Code:ptr[i].~T();
A type identifier (even a template parameter) prefixed by the tilde means the destructor of that object. It's as simple as that.
The code looks like it ought to work.
You're right, ~T() does work.
I think before I was doing: ptr[i]->~T();
Now it seems to work fine.
I beefed up the code to act like new if ptr is NULL, and act like delete if newSize is 0.
Code:template <typename T>
T* Realloc( T* ptr,
size_t oldSize,
size_t newSize )
{
if ( oldSize == newSize )
{
return ptr;
}
HANDLE hHeap = GetProcessHeap();
T* pNew = NULL;
if ( ptr != NULL ) // If no memory yet, go straight to HeapAlloc().
{
// Try to expand array.
pNew = (T*)HeapReAlloc( hHeap,
HEAP_REALLOC_IN_PLACE_ONLY,
ptr,
(newSize * sizeof( T )) );
}
if ( pNew == NULL ) // Failed to expand array.
{
if ( newSize > 0 )
{
// Try to allocate new memory and copy old array to new one.
pNew = (T*)HeapAlloc( hHeap, 0, (newSize * sizeof( T )) );
if ( pNew == NULL ) // Not enough memory.
{
throw std::bad_alloc( "No memory!" );
}
}
// Copy all old values to new array and call each old elements destructor.
for ( size_t i = 0; i < oldSize; ++i )
{
if ( i < newSize ) // In case user wants to delete or shrink array.
{
new( &pNew[i] ) T( ptr[i] );
}
ptr[i].~T();
}
if ( ptr != NULL )
{
HeapFree( hHeap, 0, ptr ); // Release old memory.
}
}
// Fill the rest of the array with default T's.
for ( size_t i = oldSize; i < newSize; ++i )
{
new( &pNew[i] ) T();
}
return pNew;
}
What if ptr is null, but oldSize is non-zero? You're code does not seem to handle that case well.
That would be a violation of a class invariant. There should probably be an assert there to make sure the invariant holds, but no special handling code is required.
That's called User Error. ;)
If you lie to a function, expect bad things.
An assert would do the trick. But the objective is to work with the library client, not against him.
Undefined behavior is pretty harsh punishment.
assert() only works in debug mode, so unless they actually test with the debug build it won't help; but I'll add it anyways.Quote:
Originally Posted by King Mir
But then how do you stop the user from entering and oldSize that's bigger than it really is, or passing an invalid (not NULL) pointer?
Now if anyone has any ideas on how to do this on UNIX, that would be really cool!
I don't really understand this, though:
Doesn't that basically mean construct a new object instead of copying it? Or maybe that basically invokes the copy constructor, I think?Code:new( &pNew[i] ) T( ptr[i] );
I'm also rusty on that syntax... but new returns a pointer to an allocated object... but I'm guessing that it is just supposed to create an object in the allocated memory and invoke the (copy) constructor?
Just a thought: but your realloc function requires memory to be allocated with HeapAlloc to work. And if such is the case, you can use HeapSize to get size (no OldSize) and to see if it's a valid pointer.
Well, what do you think copying is? It's creating a new object equivalent to an existing one.Quote:
Doesn't that basically mean construct a new object instead of copying it?
new returns a pointer to the allocated object. But in the case of placement new, this pointer is equal to the one we passed to it, so keeping it is unnecessary.
I was confused about if it was copying the state of the object over, as well, since new would just invoke the constructor.Quote:
Originally Posted by CornedBee
So this is placement new then. I see.Quote:
new returns a pointer to the allocated object. But in the case of placement new, this pointer is equal to the one we passed to it, so keeping it is unnecessary.
It would invoke the constructor. The copy constructor.
I thought so.
Cool, thanks.Quote:
Originally Posted by Elysia