Jump to content
  • Advertisement
Sign in to follow this  
guitarstar26

Dynamic item allocation to a unit

This topic is 2998 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?



Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
A vector sounds what you need, yes.

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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
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.


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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!