Sign in to follow this  

Dynamic item allocation to a unit

This topic is 2665 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
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
The standard way of doing this is to just pass your iterator to std::vector::erase(). Take note that doing so invalidates active iterators. So, if you are doing this in a loop, you need something like

std::vector< foo > myvec;

for( std::vector< foo >::iterator i = myvec.begin(); i != myvec.end(); )
{
if( !i->active() )
i = myvec.erase(i);
else
++i;
}




erase removes the element, and for a vector will preserve order and copy all the other elements up one. A list on the other hand would just pop the element out of the list without having to copy anything.

Your other option is to make a predicate function for std::remove_if along with std::erase

bool isInActive( const foo &f )
{
return !f.Active();
}
myvec.erase( std::remove_if( myvec.begin(), myvec.end(), isInActive ), myvec.end() );




remove_if does your swap-to-end trick for all values that isInActive returns true. Then it gives you an iterator to the begining of the segment to erase.

Share this post


Link to post
Share on other sites
If you are using std::vector, swapping the last entry with the removed entry is definitely the fastest way to go.

You should also take a look at http://www.cplusplus.com/reference/stl/list (std::list). It has the property of constant time removal of elements at any position, which may be useful if your list of items is large.

Take a look at the remove method in particular.

Share this post


Link to post
Share on other sites
That's somewhat contradictory advice. std::list<>::remove() is an O(n) function; it iterates over the entire list to find the elements to remove. It would defeat the purpose of moving to a list in the first place.

Keep in mind that a std::list<>, or any linked list, tends to have poor performance characteristics for common operations such as iteration, as the node based structure tends to not play nicely with memory and cache. In many cases, even with functions with worse big-O characteristics, a std::vector<> will outperform a std::list<>.

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
That's somewhat contradictory advice. std::list<>::remove() is an O(n) function; it iterates over the entire list to find the elements to remove. It would defeat the purpose of moving to a list in the first place.


I has assumed that he would already be iterating over the elements in order to determine the index which he is passing to this function. Just trying to put some different options out there =)

Having said that, depending on what you want to do with your list of items, YMMV. std::vector is definitely hard to beat in terms of speed, especially if you don't care about the order of your items.

[Edited by - 1863 on August 28, 2010 9:31:41 PM]

Share this post


Link to post
Share on other sites

This topic is 2665 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.

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