• Advertisement
Sign in to follow this  

how to pop/erase/delete a vectorStuff * ?

This topic is 2776 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

Hello all,

I'm trying to figure out a way to release the memory from the Entities (as I call anything that moves in my game) that I won't use anymore.

-warning: bad design coming! some tips?-

As an example, my Player class has Bullets. When there is a Fire() event, I check if the ship is allowed to fire; if it is, a new bullet is put to the entities list and the game flux goes on merry on its gammy way.

The problem is that I'm not releasing the resources used by bullets that are already dead, i.e. out of screen or collided. Sometime soon it will bite me back.

So I tried to release it by popping the dead bullets out of the entities list using this code:



for ( std::vector<Entities*> iter = entities.begin();
iter != entities.size();
++iter) {
if( (**iter).checkIfDead() ) {
(*iter).pop_front;
}
}



I will call it a Pseudo code. After the "if" part I dunno what to do. I want to call each entities "checkIfDead()" function and them remove it from the container. I think it would be simple if it was a vector<Stuff> (not a vector of pointers), but I really need to use a vector of pointers.

hear from you!

Fabio

Share this post


Link to post
Share on other sites
Advertisement
You need to be careful when removing elements from a standard container, read the documentation to see when iterators are invalidated. std::vector<>::iterators are prone to being invalidated on any operation that affects the layout of the vector. But what you are looking for is "delete".

A standard erase loop looks like this:

std::vector<Entities*> iter = entities.begin();
while(iter != entities.end())
{
Entity *entity = *iter;
if(entity->checkIfDead())
{
iter = entities.erase(iter);
delete entity; // assuming all entites are allocated with "new"
}
else
{
++iter;
}
}


Because you are using raw pointers you need to be careful not to store pointers elsewhere, because delete will cause any other pointers sharing the same value to become invalid.

Share this post


Link to post
Share on other sites
I think this is right.

vector<Entities*> iter = entities.begin();
while( iter != entities.end() )
{
if( (*iter)->checkIfDead() )
{
delete *iter;
iter = entities.erase(iter);
} else iter++;
}


Ninja'd [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by Concentrate
This is where you would use smart pointers, to avoid these kinds of things.


You guys rule!
Later on I will try a solution using smart pointers. Actually, it was my first thought, but I decided to go the "usual" way.

Rip-off & Buckeye, thank you very much! I tried a solution similar to yours, but I forgot to let

iter = entities.erase(iter);


actually, I didn't even know that erase returned an address!

Share this post


Link to post
Share on other sites
Quote:
Original post by draconar
Quote:
Original post by Concentrate
This is where you would use smart pointers, to avoid these kinds of things.


You guys rule!
Later on I will try a solution using smart pointers. Actually, it was my first thought, but I decided to go the "usual" way.

Rip-off & Buckeye, thank you very much! I tried a solution similar to yours, but I forgot to let

iter = entities.erase(iter);


actually, I didn't even know that erase returned an address!


Technically it doesn't, it returns an iterator to the object after the erased element but considering an iterator is basically a pointer then technically it does return an address.

Since you are deleting through the container rather than just off the end I suggest you use a list instead of a vector as it will be a lot more efficient with larger numbers of enemies.

Share this post


Link to post
Share on other sites
Quote:
Actually, it was my first thought, but I decided to go the "usual" way.
As far as modern C++ goes, using smart pointers is the 'usual' way.

That said, a lot of C++ coders still manage their memory 'by hand', either to meet certain technical requirements, or just because it's what they're used to. For new code though, best practice (arguably) is to use smart pointers (or some other RAII container) for this sort of thing unless you have a good reason to do otherwise.

Share this post


Link to post
Share on other sites
Would not the following be more appropriate?

bool PredicateFunction (const Entities* e) { return e->checkIfDead(); }
void DeleteFunction (Entities* e) { delete e; }

std::vector<Entities*> iterator = std::remove_if(entities.begin(),entities.end(),PredicateFunction);
std::for_each(iterator,entities.end(),DeleteFunction);
entities.erase(iterator,entities.end());


That way he could still use a vector and not have to worry about invalidating the iterators/deleting items in the middle of a vector (and forcing them all to be copied). The delete could be done at the very end (after say, more items are removed due to other game logic). Not to mention you could add/remove items every frame and have very few memory allocations (as once the vector hit its working capacity, it'd stay there and there'd be no more allocations. A list on the other hand would have allocations every frame.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
Would not the following be more appropriate?

std::remove_if() doesn't partition. That is to say the removed elements are not guaranteed to be placed after the returned iterator. If you want to partition use the partition() function.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
Would not the following be more appropriate?

bool PredicateFunction (const Entities* e) { return e->checkIfDead(); }
void DeleteFunction (Entities* e) { delete e; }

std::vector<Entities*> iterator = std::remove_if(entities.begin(),entities.end(),PredicateFunction);
std::for_each(iterator,entities.end(),DeleteFunction);
entities.erase(iterator,entities.end());


That way he could still use a vector and not have to worry about invalidating the iterators/deleting items in the middle of a vector (and forcing them all to be copied). The delete could be done at the very end (after say, more items are removed due to other game logic). Not to mention you could add/remove items every frame and have very few memory allocations (as once the vector hit its working capacity, it'd stay there and there'd be no more allocations. A list on the other hand would have allocations every frame.


Yea, I would agree that is the best solution to use, using remove_if and erase in combination had crossed my mind but I forgot it's an efficient solution, with respect to the Vector, it's plausible for it to never require allocations if enough space to store all enemies is allocated at it's construction, but I guess that's down to the game itself.

Quote:
Original post by SiCrane
Quote:
Original post by Ryan_001
Would not the following be more appropriate?

std::remove_if() doesn't partition. That is to say the removed elements are not guaranteed to be placed after the returned iterator. If you want to partition use the partition() function.


Forgot about that, it wouldn't have been a problem if the container wasn't pointers to Entities, or it was using some form of reference counting handle.

Share this post


Link to post
Share on other sites
Am I misreading:

Quote:
Remove_if removes from the range [first, last) every element x such that pred(x) is true. That is, remove_if returns an iterator new_last such that the range [first, new_last) contains no elements for which pred is true. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged.


- http://www.sgi.com/tech/stl/remove_if.html

If they aren't guaranteed to be placed after the returned iterator, where are they placed? They can't possibly just be discarded can they? Granted I had never looked at partition before, it seems to do what I imagined Remove_if to do, so I'm certain you're correct, the question is... why?

That said, would:

std::vector<Entities*> iterator = std::parition(entities.begin(),entities.end(),PredicateFunction);
std::for_each(iterator,entities.end(),DeleteFunction);
entities.erase(iterator,entities.end());


be more appropriate?

Quote:
Yea, I would agree that is the best solution to use, using remove_if and erase in combination had crossed my mind but I forgot it's an efficient solution, with respect to the Vector, it's plausible for it to never require allocations if enough space to store all enemies is allocated at it's construction, but I guess that's down to the game itself.


From the way it was described I assumed he was adding/removing entities on the fly. But that was just a guess.

Share this post


Link to post
Share on other sites
This is more or less what std::remove() and std::remove_if() do:

If you had values like:

1 2 3 4 2 2 3

and told it to remove all the 2's, the algorithm would do something like:

1 2 3 4 2 2 3
^
|
Here's the first one. It's not a 2, let's move on.

1 2 3 4 2 2 3
^
|
Here's the next one. It is a 2, let's find the next non 2.

1 2 3 4 2 2 3
^ ^
| |
The next one is a 3. Ok, copy that on top of the 2.

1 3 3 4 2 2 3
^
|
Now we need to copy something on top of 3's old position. Let's find the next non 2.

1 3 3 4 2 2 3
^ ^
| |
This guy's a 4, that's not a 2. Let's copy that on top of the old 3.

1 3 4 4 2 2 3
^
|
Now we need to find something to copy on top of the old 4's position.

1 3 4 4 2 2 3
^ ^
| |
No good. That's a 2.

1 3 4 4 2 2 3
^ ^
| |
No good. That's another 2.

1 3 4 4 2 2 3
^ ^
| |
Ok that's not a 2. Copy it on top of the old 4's position.

1 3 4 3 2 2 3
^ ^
| |
Now we're out of inputs. So return the iterator after the last item we copied.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
Am I misreading:

Quote:
Remove_if removes from the range [first, last) every element x such that pred(x) is true. That is, remove_if returns an iterator new_last such that the range [first, new_last) contains no elements for which pred is true. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified. Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged.


- http://www.sgi.com/tech/stl/remove_if.html

If they aren't guaranteed to be placed after the returned iterator, where are they placed? They can't possibly just be discarded can they? Granted I had never looked at partition before, it seems to do what I imagined Remove_if to do, so I'm certain you're correct, the question is... why?

Because he is using pointers, as evidenced by SiCrane's example above a 3 is leftover at the end of the container, if you run delete on these you are potentially deleting things you don't intend upon doing and then in the next frame attempting to access a pointer which doesn't point to an object.

Quote:
That said, would:

std::vector<Entities*> iterator = std::parition(entities.begin(),entities.end(),PredicateFunction);
std::for_each(iterator,entities.end(),DeleteFunction);
entities.erase(iterator,entities.end());


be more appropriate?

Absolutely.

Quote:
Quote:
Yea, I would agree that is the best solution to use, using remove_if and erase in combination had crossed my mind but I forgot it's an efficient solution, with respect to the Vector, it's plausible for it to never require allocations if enough space to store all enemies is allocated at it's construction, but I guess that's down to the game itself.


From the way it was described I assumed he was adding/removing entities on the fly. But that was just a guess.


All of it really is a guess as nobody except for the OP knows what his game does ;)

As an example something like space invaders with a fixed number of enemies could require zero allocation for the enemies as you are only deleting them after instantiation (aside from the mothership).

Share this post


Link to post
Share on other sites
Ok, fair enough. I guess given the restriction of forward iterators that's about the best you can do. Though that would lead to alot of copies though.

If we have random iterators though we could swap any items that return false for their predicate with the last item in the container, then decrement the the 'last' iterator, continue checking, ect... Then when done return the 'last' iterator, the range begin() to last would all be items where the predicate returned true, and all items in last to end() would be items where the predicate returned false.

Is this how partition works? Because that's how I (naively) imagined remove_if to work.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
Ok, fair enough. I guess given the restriction of forward iterators that's about the best you can do. Though that would lead to alot of copies though.

Actually it's the optimum number of copies for a stable algorithm.

Quote:
Is this how partition works? Because that's how I (naively) imagined remove_if to work.

No, partition() is somewhat more intelligent than that. Let's partition this data set for 2s and non-2s:

1 2 3 2 4 2 2 3 2
^ ^
| |
Starting position

1 2 3 2 4 2 2 3 2
^ ^
| |
Move the front pointer to the first 2

1 2 3 2 4 2 2 3 2
^ ^
| |
Move the back pointer to the first non 2

1 3 3 2 4 2 2 2 2
^ ^
| |
Swap


1 3 3 2 4 2 2 2 2
^ ^
| |
Move the front pointer to the next 2


1 3 3 2 4 2 2 2 2
^ ^
| |
Move the back pointer to the next non 2


1 3 3 4 2 2 2 2 2
^ ^
| |
Swap


1 3 3 4 2 2 2 2 2
^
|
Move the front pointer to the next 2, but hit the back pointer. End.

Share this post


Link to post
Share on other sites
Never thought of that, that would be faster. But how does it manage given that Partition uses only ForwardIterators (something I checked since last response ;). And if partition doesn't do that, is there a standard function that does or should I create my own?

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
Never thought of that, that would be faster. But how does it manage given that Partition uses only ForwardIterators (something I checked since last response ;). And if partition doesn't do that, is there a standard function that does or should I create my own?


It uses bidirectional iterators not forward iterators.

In <algorithm> std::partition exists.

Alternatively I have an example of the algorithm that should work but it isn't tested as my compiler seems to like giving my container.end() iterator as an extremely large negative number that can't be dereferenced. It uses std::swap as I couldn't be bothered to rewrite it at the time I wrote this.

template <class In, class Pred>
In partition(In start, In end, Pred pred)
{
In i = start; In j = end;
while(i != end && j != start)
{
while(pred(*i))
++i;
while(!pred(*j))
--j;
if (i == j)
break;
std::swap(*i, *j);
}
return i;
}

Share this post


Link to post
Share on other sites

http://www.sgi.com/tech/stl/partition.html gives:

template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)


But at a cursory glance the algorithm looks good.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001

http://www.sgi.com/tech/stl/partition.html gives:

template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)


But at a cursory glance the algorithm looks good.


<a>http://www.cppreference.com/wiki/stl/algorithm/partition gives:
bidirectional_iterator partition( bidirectional_iterator start, bidirectional_iterator end, Predicate p );


Partition could work with a forward iterator but it wouldn't be linear time complexity.

Share this post


Link to post
Share on other sites
Quote:
Original post by ExcessNeo
Quote:
Original post by Ryan_001

http://www.sgi.com/tech/stl/partition.html gives:

template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred)


But at a cursory glance the algorithm looks good.


<a>http://www.cppreference.com/wiki/stl/algorithm/partition gives:
bidirectional_iterator partition( bidirectional_iterator start, bidirectional_iterator end, Predicate p );


Partition could work with a forward iterator but it wouldn't be linear time complexity.


My thoughts exactly. So I guess the SGI documentation is wrong?

Share this post


Link to post
Share on other sites
Quote:
Original post by ExcessNeo
Alternatively I have an example of the algorithm that should work but it isn't tested as my compiler seems to like giving my container.end() iterator as an extremely large negative number that can't be dereferenced.

That's because container.end() returns an iterator that's one past the last element, if any -- *container.end() is always illegal.

The C++ standard library consistently represents ranges with a begin iterator, pointing to the first element, and an 'end' iterator, which isn't included in the range. Thus:
begin
|
v
A B C D
^
|
end

Contains 1 element (B), not 2 (B and C). This applies to all standard library algorithms, as well as all containers.

Unfortunately, your version of partition is basically completely broken:
1) Tries to dereference *j while j==end, which as already mentioned is invalid/broken/wrong/undefined behavior
2) If pred always returns true, while(pred(*i)) is an infinite loop (until it starts reading outside the range again, which is again undefined behavior)
3) If pred always returns false, while(!pred(*j)) is an infinite loop (until it starts reading outside the range again)
4) if (i == j) will never sanely break -- since by the time this executes, pred(*i) is false but pred(*j) is true, to have exited their above loops, meaning pred is an invalid predicate or they don't refer to the same elements

Share this post


Link to post
Share on other sites
Quote:
Original post by Ryan_001
My thoughts exactly. So I guess the SGI documentation is wrong?

The original SGI STL implementation (which archeologists believe dates back to around 1300 B.C.E.) may have only required forward iterators -- but yes, it's wrong.

MSDN tends to be much better than SGI's docs on modern C++. Fewer glaring errors and outright omissions.

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
Quote:
Original post by ExcessNeo
Alternatively I have an example of the algorithm that should work but it isn't tested as my compiler seems to like giving my container.end() iterator as an extremely large negative number that can't be dereferenced.

That's because container.end() returns an iterator that's one past the last element, if any -- *container.end() is always illegal.

The C++ standard library consistently represents ranges with a begin iterator, pointing to the first element, and an 'end' iterator, which isn't included in the range. Thus:
begin
|
v
A B C D
^
|
end

Contains 1 element (B), not 2 (B and C). This applies to all standard library algorithms, as well as all containers.

Unfortunately, your version of partition is basically completely broken:
1) Tries to dereference *j while j==end, which as already mentioned is invalid/broken/wrong/undefined behavior
2) If pred always returns true, while(pred(*i)) is an infinite loop (until it starts reading outside the range again, which is again undefined behavior)
3) If pred always returns false, while(!pred(*j)) is an infinite loop (until it starts reading outside the range again)
4) if (i == j) will never sanely break -- since by the time this executes, pred(*i) is false but pred(*j) is true, to have exited their above loops, meaning pred is an invalid predicate or they don't refer to the same elements


Yea I understand that end is not in range I just wasn't quite thinking straight at gone 3am, though was just a case of adding a j--; before I dereferenced j.

I have since fixed it a bit although there is still a dereference, so looks like I'll either go back to the drawing board or just forget about it as I understand the principles of partition even if my attempt at implementing it was a catastrophic failure.

template <class In, class Pred>
In partition(In start, In end, Pred pred)
{
end--;
while(start != end)
{
while(start != end && !pred(*start))
++start;
while(pred(*end) && end != start)
--end;
if(start != end)
std::swap(*start, *end);
}
return end;
}

Seems to work using the short circuit nature of && although I guess since end is always in range for the while loop it's unnecessary.

Share this post


Link to post
Share on other sites
What happens if your algorithm is called with start == end?

Share this post


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

  • Advertisement