Sign in to follow this  
Kest

Deallocating std::vector reserve

Recommended Posts

Kest    547
Is there a full-proof way to put std::vector back into it's construction state or to reduce the size of reserved memory? I've seen people mention using swap() with a temporary stack vector to completely deallocate it. Is that the only method available? I've also heard that some implementations cause clear() to deallocate reserve memory, but the use of the word 'some' seems pretty alarming. Thanks for information

Share this post


Link to post
Share on other sites
iMalc    2466
Quote:
Original post by Kest
Is there a full-proof way to put std::vector back into it's construction state or to reduce the size of reserved memory? I've seen people mention using swap() with a temporary stack vector to completely deallocate it. Is that the only method available?
Yes, and Yes, afaik.
Quote:


I've also heard that some implementations cause clear() to deallocate reserve memory, but the use of the word 'some' seems pretty alarming.
There's no need to be alarmed. It simply means that the standard doesn't enforce one way or the other with regards to the behaviour. Either implementation will suffice. Some simply do extra above and beyond what is required of them, in an attempt to furthur increase performance.

Share this post


Link to post
Share on other sites
Kest    547
Quote:
Original post by iMalc
Quote:
Original post by Kest
Is there a full-proof way to put std::vector back into it's construction state or to reduce the size of reserved memory? I've seen people mention using swap() with a temporary stack vector to completely deallocate it. Is that the only method available?
Yes, and Yes, afaik.

I appreciate your time. Are you saying yes to all three questions? I'm guessing yes to the first and last?

If I need to temporarily increase the capacity of a vector by a huge amount, but know that such capacity will be wasted afterwards, is there a way to force a reallocation to reduce the capacity to a reasonable amount?

Thanks

Share this post


Link to post
Share on other sites
Kest    547
Thanks much for the link.

There is a big problem with the "right way to Shrink-To-Fit" approach that the author left out. A normal vector memory reserve() allocation resize doesn't create copies, call any constructors, or call any destructors. But his method with swap() does all three. Instead of moving memory from one buffer to another, it creates new objects, copies the old objects, then destroys the old objects. It would become very ugly with complex objects that allocate a lot of data themselves. It would even become dangerous for objects that are designed to exist one at a time.

Will a vector memory shrink even be possible without creating copies of the objects? I would hate to have to do an ugly manual memcpy on the elements.

Thank you again

Share this post


Link to post
Share on other sites
JohnBolton    1372
Quote:
Original post by Kest
There is a big problem with the "right way to Shrink-To-Fit" approach that the author left out. ... It would become very ugly with complex objects that allocate a lot of data themselves. ...

Since both resize() and reserve() may copy all the elements, this problem is not restricted to swap(). The solution to the problem is a vector of pointers rather than a vector of objects.

Quote:
Original post by Kest
... It would even become dangerous for objects that are designed to exist one at a time.

You cannot use these types of objects in an STL container anyway.

Quote:
Original post by Kest
Will a vector memory shrink even be possible without creating copies of the objects? I would hate to have to do an ugly manual memcpy on the elements.

No, since there is no generic way of reallocating memory (bigger or smaller) while guaranteeing that the memory space does not move.

Share this post


Link to post
Share on other sites
Kest    547
Quote:
Original post by JohnBolton
Quote:
Original post by Kest
There is a big problem with the "right way to Shrink-To-Fit" approach that the author left out. ... It would become very ugly with complex objects that allocate a lot of data themselves. ...

Since both resize() and reserve() may copy all the elements, this problem is not restricted to swap(). The solution to the problem is a vector of pointers rather than a vector of objects.

I'm pretty sure that's incorrect. Or at least it doesn't match what I read from STL documentation. reserve() resizes do not call constructors, destructors, or copy operators. It only copies vector memory, and does not copy the object's dynamically created memory. swap() is not the problem. He's copying the entire list of elements before swap is called.

Quote:
Quote:
Original post by Kest
... It would even become dangerous for objects that are designed to exist one at a time.

You cannot use these types of objects in an STL container anyway.

Of course you can. What if I create a vector of maps, where each map loads a certain file for it's coordinates, deleting that file to mark the fact that the coordinate state is now dynamic in memory?

Quote:
Quote:
Original post by Kest
Will a vector memory shrink even be possible without creating copies of the objects? I would hate to have to do an ugly manual memcpy on the elements.

No, since there is no generic way of reallocating memory (bigger or smaller) while guaranteeing that the memory space does not move.

Of course it's necessary to copy the generic reserved vector memory. By "creating copies of the objects", I'm referring to copying the vector elements through a function or operator.

Share this post


Link to post
Share on other sites
SiCrane    11839
Quote:
Original post by Kest
I'm pretty sure that's incorrect. Or at least it doesn't match what I read from STL documentation. reserve() resizes do not call constructors, destructors, or copy operators. It only copies vector memory, and does not copy the object's dynamically created memory.

If reserve is used to reserve a memory size greater than the current capacity, then the vector will allocate a new memory block of an appropriate size and then use the copy constructor to construct the elements in the new memory blocks from the current elements.

Quote:

Of course you can. What if I create a vector of maps, where each map loads a certain file for it's coordinates, deleting that file to mark the fact that the coordinate state is now dynamic in memory?

Then you're hosed when the copy constructor of the elements kick in.

Share this post


Link to post
Share on other sites
Kest    547
Wow, it's true. That really limits the types of objects that would work well with it. Even more, a normal list construction only calls the normal contructor for the first element, then calls copy constructors for the rest. Sort of odd behavior. I can't really understand why they wouldn't call the normal constructor for every element in the way operator new does.

Oh well, thanks for pointing that out for me.

Share this post


Link to post
Share on other sites
Conner McCloud    1135
Quote:
Original post by Kest
Of course you can.

All objects stored in standard containers are required to be assignable and copy-constructable. The requirement for an object to be assignable are that t=u results in t being equivilent to u. Note that having an assignment operator will almost certainly allow the code to compile, but that's not good enough: see auto_ptr for an example.

Yeah, its a limitation, but without it the containers would be horrendously crippled.

CM

Share this post


Link to post
Share on other sites
Kest    547
Doesn't this make buffer resizes completely impractical for complex objects? Could anyone explain why it's designed this way?

Vector is already allocating generic memory and manually calling constructors on it. I don't understand why it calls copy constructors and destructors when memory is expanded during a background resize. Why not simply copy the memory without disturbing the objects?

Is it because it's possible to break certain types of objects by moving them around in memory? The only situation I can imagine is one where the objects in the list own pointers to each other. Even then, all that needs done is to offset (+=) the pointers by the memory movement offset.

Share this post


Link to post
Share on other sites
DrEvil    1148
Most people use pointers to complex objects instead of the objects themselves.

When it resizes the new larger memory buffer is not in the same place, so it has to move existing elements to the new location. The only reliable way of doing it is with assignment/copy constructors. You can't just memcpy the objects, for the same reason you can't memcpy an std::string, or std::list, that would copy the internal pointer, meaning u then have multiple objects pointing to the same memory, and have a nice crash waiting for you when the 2nd one is destructed.

Share this post


Link to post
Share on other sites
Kest    547
Quote:
Original post by DrEvil
Most people use pointers to complex objects instead of the objects themselves.

I thought the major point of using standard library objects was to avoid these situations.

Quote:
Original post by DrEvil
The only reliable way of doing it is with assignment/copy constructors. You can't just memcpy the objects, for the same reason you can't memcpy an std::string, or std::list, that would copy the internal pointer, meaning u then have multiple objects pointing to the same memory, and have a nice crash waiting for you when the 2nd one is destructed.

Vector is already manually calling destructors for the generic memory. In order to prevent the situation you speak of, it only needs to avoid doing so for the old memory. It simply deletes that old memory in the same way it normally would and all is well. You only have one copy of each object, just moved to another location.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Kest
Quote:
Original post by DrEvil
Most people use pointers to complex objects instead of the objects themselves.

I thought the major point of using standard library objects was to avoid these situations.


1) It does help in the simple situations, and in a sufficiently complex situation, it might be that nothing really useful can be done, but it won't make things worse. And the simple situations are much more common than you might think. I would estimate that for every time I suggest changing a vector of objects into a vector of pointer-to-objects, I give the reverse advice at least ten times.

2) We're talking about a much different kind of use of pointers here. In particular, we're talking about pointers that *always* point to a *scalar* allocation (as opposed to an array allocation). We're not going to confuse delete with delete[], or worry about how many elements are pointed to (we know the answer: 1).

3) "complex" doesn't even necessarily mean what you think it does. Just because an object allocates its own memory, or has a large sizeof(), doesn't preclude it from being used in a container. You just have to make sure it's copyable and assignable. And if the *only* complication is "it allocates its own memory", then you should be doing that *anyway*. Actually, scratch that - you should usually have a std::vector as a data member of the object ;)

Quote:
Original post by DrEvil
The only reliable way of doing it is with assignment/copy constructors. You can't just memcpy the objects, for the same reason you can't memcpy an std::string, or std::list, that would copy the internal pointer, meaning u then have multiple objects pointing to the same memory, and have a nice crash waiting for you when the 2nd one is destructed.

Vector is already manually calling destructors for the generic memory. In order to prevent the situation you speak of, it only needs to avoid doing so for the old memory. It simply deletes that old memory in the same way it normally would and all is well. You only have one copy of each object, just moved to another location.[/quote]

Trust me, you're not as smart as you think. (Try searching the forums for discussion of "move constructors" that are being discussed for addition in the next version of the C++ standard.)

Share this post


Link to post
Share on other sites
Kest    547
Quote:
Original post by Zahlman
3) "complex" doesn't even necessarily mean what you think it does. Just because an object allocates its own memory, or has a large sizeof(), doesn't preclude it from being used in a container.

In the case of std::vector resizing, it results in unnecessary allocation, copying, and deallocation of the type's dynamic memory. In some cases, that is unacceptable. In the rest, it's still unnecessary.

Quote:
You just have to make sure it's copyable and assignable. And if the *only* complication is "it allocates its own memory", then you should be doing that *anyway*. Actually, scratch that - you should usually have a std::vector as a data member of the object ;)

Copy assignments being present is not my concern. Copy assignments being called is. Instead of moving a house onto the other side of the street, you're paying for the construction of a brand new house and then paying to destroy the old one. There's a big difference between size and complexity. Copying relies on both.

Quote:
Quote:
Quote:
Original post by DrEvil
The only reliable way of doing it is with assignment/copy constructors. You can't just memcpy the objects, for the same reason you can't memcpy an std::string, or std::list, that would copy the internal pointer, meaning u then have multiple objects pointing to the same memory, and have a nice crash waiting for you when the 2nd one is destructed.

Vector is already manually calling destructors for the generic memory. In order to prevent the situation you speak of, it only needs to avoid doing so for the old memory. It simply deletes that old memory in the same way it normally would and all is well. You only have one copy of each object, just moved to another location.


Trust me, you're not as smart as you think. (Try searching the forums for discussion of "move constructors" that are being discussed for addition in the next version of the C++ standard.)

What a horrible thing to say. Did I state something to warrant such a childish remark? If you could point it out, I'll try to be more careful in the future. I'm only trying to understand the reason behind the design choices.

Share this post


Link to post
Share on other sites
JohnBolton    1372
Quote:
Original post by Kest
In the case of std::vector resizing, it results in unnecessary allocation, copying, and deallocation of the type's dynamic memory. In some cases, that is unacceptable. In the rest, it's still unnecessary.

Sometimes, it is necessary (for example, std::string, as pointed out earlier). The containers are designed to work for any type of object (though there are restrictions). You are proposing an optimization that would further limit the types of objects they can contain, but an equivalent optimization can be done without doing that -- by using a container of pointers.

Furthermore, the concept of moving an object doesn't exist in C++, though someday it might (there are other cases where the ability to move an object would be useful). So, if you can't move objects in general, then you can't expect containers to move objects.

Quote:
Original post by Kest
Copy assignments being present is not my concern. Copy assignments being called is. Instead of moving a house onto the other side of the street, you're paying for the construction of a brand new house and then paying to destroy the old one. There's a big difference between size and complexity. Copying relies on both.

You can move a house, though you can't move a house with a basement without digging a new basement, and you can't move a skyscraper (because it has 100s of 20 m piles that are driven into the ground).

Share this post


Link to post
Share on other sites
Kest    547
Could anyone point out why std::string is unsafe to move? Does it contain pointers to it's own data? I'm not very familiar with it's internal operation. If it does contain pointers to it's own memory, that could have been avoided by using an offset from itself to begin with.

Thanks

Share this post


Link to post
Share on other sites
Kest    547
Quote:
Original post by JohnBolton
Sometimes, it is necessary (for example, std::string, as pointed out earlier).

DrEvil explained how std::string would have problems if you copied it and deleted both versions. But that's not what would happen. The old version would not be destructed. Unless std::string is pointing its string reference to one of its internal members, there's no danger that I'm aware of in moving it. If there are further dangers, it would be great if someone could point those out.

Quote:
The containers are designed to work for any type of object (though there are restrictions). You are proposing an optimization that would further limit the types of objects they can contain, but an equivalent optimization can be done without doing that -- by using a container of pointers.

You could also create a discontiguous array object that does this internally. The interface user could be completely unaware of it, except the impossibility of using pointer arithmetic on elements.

I'm not really proposing something. I'm just trying to understand why it isn't already designed this way. How would this further limit the types of objects they can contain? From what I understand of it, it would increase the number, not lower it. Objects that allocate a lot of data would work great. Only objects that do something such as this->Ptr = &this->Member would become invalid.

Quote:
You can move a house, though you can't move a house with a basement without digging a new basement, and you can't move a skyscraper (because it has 100s of 20 m piles that are driven into the ground).

If you could explain that analogy, it would help me greatly. How frequently do objects rely on their memory location?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this