Say I have a unit class which is essentially a player character.
Now I want to give this unit an item.
class unit{
private:
item m_item;
}
Seems simple, but how would I allow for the unit to hold an unlimited amount of items without declaring something like. (items carrying capacity is limited only by weight of the item)
class unit{
private:
item* m_items[500000];
}
Would it be best to use a vector? What exactly does the vector datatype do when you ask it to dynamically increase during execution.
For example, if I had a vector of size 5 and needed to add a 6th element, does it copy the array of 5 into a location where an array of 6 can fit? Is this slow? If the vector has space for 100 elements, does it consume 100 elements worth of memory?
Dynamic item allocation to a unit
a std::vector has two main traits you are worried about in your post: std::vector::size() and std::vector::capacity(). If, when you call push_back, there is capacity left, the item is just added. Otherwise, it tends to double the capacity copy the old items over, free the old memory, and then add the new item.
If you need std::vector to do something more specific with its memory, you can std::vector::reserve() to set the capacity. For instance, if you know you are going to add another 100 items, you might call itemlist.reserve( itemlist.size() + 100 ); to make sure there is room before you call push_back. Otherwise, it might resize a few times (can get expensive) while you are pushing items.
If you need std::vector to do something more specific with its memory, you can std::vector::reserve() to set the capacity. For instance, if you know you are going to add another 100 items, you might call itemlist.reserve( itemlist.size() + 100 ); to make sure there is room before you call push_back. Otherwise, it might resize a few times (can get expensive) while you are pushing items.
A vector sounds what you need, yes.
I guess you are talking about the STL vector? The exact details depend on the implementation, as far as I know, though I guess what you really want to know by reading your example is this:
A STL vector has a size and a capacity. The size is the number of elements currently contained in the vector, the capacity is the number of elements for which memory is reserved. So when you push_back a new element, and the size reached the capacity, the capacity will be increased, which seems to be usually n times - implementation dependant, too. And yep, the increasing should involve copying. I don't know about your definition of "slow", but it should be O(n). If this is a problem for you, you can increase/set the capacity yourself. (And if memory is a problem, you can use pointers. Or ptr_vector, for the matter.)
Stuff that might interest you:
http://www.cplusplus.com/reference/stl/vector
http://stackoverflow.com/questions/2625006/how-is-push-back-implemented-in-stl-vector
edit: Too slow, hu.
Quote:What exactly does the vector datatype do when you ask it to dynamically increase during execution.
I guess you are talking about the STL vector? The exact details depend on the implementation, as far as I know, though I guess what you really want to know by reading your example is this:
A STL vector has a size and a capacity. The size is the number of elements currently contained in the vector, the capacity is the number of elements for which memory is reserved. So when you push_back a new element, and the size reached the capacity, the capacity will be increased, which seems to be usually n times - implementation dependant, too. And yep, the increasing should involve copying. I don't know about your definition of "slow", but it should be O(n). If this is a problem for you, you can increase/set the capacity yourself. (And if memory is a problem, you can use pointers. Or ptr_vector, for the matter.)
Stuff that might interest you:
http://www.cplusplus.com/reference/stl/vector
http://stackoverflow.com/questions/2625006/how-is-push-back-implemented-in-stl-vector
edit: Too slow, hu.
Yes, a vector would be best.
I believe it is implementation dependent what vector does when you try to go over its size, but the common implementations (iirc) double their storage when you exceed their capacity. And yes they'll copy the contents. Yes it's slow, but not as much as you think, and even then you can ameliorate that by pre-setting capacity or by not keeping the object in the vector, only (smart) pointers to them.
I believe it is implementation dependent what vector does when you try to go over its size, but the common implementations (iirc) double their storage when you exceed their capacity. And yes they'll copy the contents. Yes it's slow, but not as much as you think, and even then you can ameliorate that by pre-setting capacity or by not keeping the object in the vector, only (smart) pointers to them.
Quote:Original post by Telastyn
I believe it is implementation dependent what vector does when you try to go over its size, but the common implementations (iirc) double their storage when you exceed their capacity.
push_back() has to be amortized constant time, so the capacity has to increase by a factor, not by a fixed amount. Common multiples seem to be between 1.5 and 3.
Quote:Original post by SiCraneQuote:Original post by Telastyn
I believe it is implementation dependent what vector does when you try to go over its size, but the common implementations (iirc) double their storage when you exceed their capacity.
push_back() has to be amortized constant time, so the capacity has to increase by a factor, not by a fixed amount. Common multiples seem to be between 1.5 and 3.
Care to clarify that? I might be a little burnt out at the end of the week, but I'm not understanding how that's different than what I said.
..unless you mean that my use of 'implementation dependent' was too broad? Yes, I perhaps should've clarified that it was implementation dependent so long as they satisfy the implementation requirements (which does iirc specify complexity requirements on the standard containers).
Yes, it was the part where you left out the complexity guarantee. A vector's capacity can't increase by just one or two or any fixed amount when it resizes; an implementation can't choose that as behavior and be compliant.
Author
Secondary question-
Adding to the vector is quite simple with pushback()
Removing is a little more difficult.
Here is my current remove function, although I think it may be better to shift the contents of the vector instead of just placing the last element in the removed element.
Is there a simple use of iterators that would allow me to shift the contents without a large time cost?
Adding to the vector is quite simple with pushback()
Removing is a little more difficult.
Here is my current remove function, although I think it may be better to shift the contents of the vector instead of just placing the last element in the removed element.
bool unit::RemoveWeapon(int index){ if(index < (int)vwTable.size()) { carried-=vwTable[index].weight; vwTable[index] = vwTable[vwTable.size()-1]; vwTable.pop_back(); return true; } else return false;}Is there a simple use of iterators that would allow me to shift the contents without a large time cost?
Vectors have erase(), which allows you to use an iterator to specify which element should be removed. The rest are then shifted to their new positions. When you talk about time cost, though, what kind of performance are you looking for? It's true that erase() is slow compared to its equivalent for containers like lists, but unless you're doing huge amounts of removals constantly (many thousands per second), it's not going to interfere with an interactive framerate.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
