Sign in to follow this  
glopen

Pointer containers! ("User breakpoint called from code at 0x..")

Recommended Posts

glopen    138
I was feeling pretty happy with the following bit of code working:
if ( obj_1Q.size() > 0 )
{
obj_1Q.erase( std::remove_if(obj_1Q.begin(), obj_1Q.end(), std::mem_fun_ref(obj_1::isactive)), obj_1Q.end() );
std::for_each(obj_1Q.begin(), obj_1Q.end(), std::mem_fun_ref(obj_1::render));
}
This all works perfectly with instance containers. Trying to modify the code for a vector of pointers I ended up with these: #1.
if ( bulletQ.size() > 0 )
{
vector<bullet*>::iterator j = std::remove_if( bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::isactive) );

if( j!=bulletQ.end() )	//just in case
	for( vector<bullet*>::iterator i = bulletQ.end(); i!=j; i-- )
	{
		free ( bulletQ.back() );
		bulletQ.pop_back();
	}
std::for_each( bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::render) );
}
and, #2.
if ( bulletQ.size() > 0 )
{
vector<bullet*>::iterator j = std::remove_if( bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::isactive) );

if( j!=bulletQ.end() )
	for( vector<bullet*>::iterator i = bulletQ.end(); i!=j; i-- )
	{
		free ( i );
		bulletQ.pop_back();
	}
std::for_each( bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::render) );
}
Okay, before you guys start flaming me for using pointers, let me just state my problems: a) #1 causes an access violation, so there's definitely something wrong with determining the bounds. b) #2 causes the weird "User breakpoint called from code at 0x.." in NTDLL! ...(). I gather this is an issue with the heap being corrupted, probably due to some unwarranted freeing. Apparently this only happens under WIN32 debug environment, but my game crashes even when I'm just executing the exe. Any ideas? I'm sensing I'm pretty close but can't spot the problem. Can you help? Thanks.

Share this post


Link to post
Share on other sites
rip-off    10979
I don't know if you can reliably combine remove_if with pointer containers without possibly causing memory leaks. That said, the problem you are having in #1 is that you are modifying a vector while iterating over it. #2 is just bad mojo, because you are free()ing the iterator itself, not the pointer (which is *it).

The best solution is to use boost::ptr_vector.

A distant second is to delete the pointers during std::remove_if, using a custom functor:

struct DeleteIfInactive
{
typedef enemy *EnemyPtr;
bool operator()( EnemyPtr &ptr ) const
{
bool b = !ptr->isactive();
if(b)
{
delete ptr;
ptr = 0;
}
return b;
}
};

// the vector being empty is not a special case here
typedef std::vector<bullet *> BulletVector;
BulletVector::iterator it = std::remove_if( bulletQ.begin(), bulletQ.end(), DeleteIfInactive() );

bulletQ.erase(it,bulletQ.end());

std::for_each( bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::render) );



I *think* this should work, but you still need to carefully code all possible control paths that may remove items from the vector to ensure the pointers are deleted. Using a smart container, or a container of smart pointers, is far superior.

Share this post


Link to post
Share on other sites
glopen    138
Thanks. Well, I was told about Boost's ability handle this type of things. But for now I'd really like to know exactly where I'm going wrong with my code instead of abstracting everything away. This bit of code is getting really frustrating and I really don't want to lose any sleep over it now :) Thanks, though. Anyone?

EDIT:
@rip-off:

Hey, thanks for the codes.

I actually thought of something like this, but the idea of defining structs/functions for every type of object put me off. Shouldn't
typedef enemy *EnemyPtr;
be
typedef bullet *EnemyPtr;
in this context?
Thanks.

PS: I see what you mean by iterating through the vector while changing it. That's why I started from the end :)

[Edited by - glopen on August 15, 2008 4:47:21 PM]

Share this post


Link to post
Share on other sites
rip-off    10979
std::remove_if doesn't guarantee which elements are in the removed range.

The following example might help:

std::vector<int> numbers;
for(int i = 0 ; i < 40 ; ++ i)
{
numbers.push_back(i);
}

std::random_shuffle(numbers.begin(),numbers.end());

std::vector<int>::iterator it = std::remove_if(numbers.begin(),numbers.end(), &even);

std::sort(it,numbers.end());

std::copy(it,numbers.end(),std::ostream_iterator<int>(std::cout," "));

numbers.erase(it,numbers.end());
std::cout << "\n------------------------------\n";
std::sort(numbers.begin(),numbers.end());
std::copy(numbers.begin(),numbers.end(),std::ostream_iterator<int>(std::cout," "));




What happens on my computer is that I get a list of the (to be) erased elements. If you look carefully, this list will contain even numbers! Yet the range printed at the end contains all even numbers. The thing is that the remove_if process may have already destroyed some elements before the erase takes place: it doesn't guarantee which elements are in that range. This makes the algorithm more efficient.

To make your code work, the algorithm you would need is std::partition(), which keeps all elements intact. You could then reliably delete all the end elements. You would need to change how you delete them though, as modifying a vector can invalidate iterators. While pop_back() shouldn't trigger a reallocation, its a bad habit to get into modifying while iterating.

Share this post


Link to post
Share on other sites
rip-off    10979
Quote:

what does this do: typedef enemy *EnemyPtr;


Typedef just provides an alias for a type. For long type names (such as nested template types) it can reduce typing an increase clarity. It has nothing to do with encapsulation.

In this case I used an alias for a pointer to enemy because I can never remember how to write references to pointers (mostly because I never use raw pointers where possible).

Share this post


Link to post
Share on other sites
Drigovas    509
1: If you're using C++, use 'new' and 'delete', not 'free' or 'malloc'. It is a pretty good idea to be consistant with these, as there is more going on with a 'new' command than with a 'malloc' command, and more going on with a 'delete' command than a 'free' command. You are clearly using C++ by your use of STD, there should be nowhere in your code that uses the 'free' function [unless you have redefined it to something that has nothing to do with malloc, which is then just bad practice].

2: In case 2, you are attempting to 'free' an iterator, not the object that it points to. Also, an iterator set to 'end()' doesn't just skip along as the vector shortens, so you'll be redundantly freeing the same thing.

Pretty sure that upon fixing the issues with case 2, you'll see the same problem as with case 1 currently. I'm pretty sure why case 1 is failing, but not sure enough to blurt it out as truth....

And there is nothing wrong with using pointers.

Share this post


Link to post
Share on other sites
glopen    138
Thanks. Algorithms are not something I generally have problems with, it's just that using pointers always messes things up. The only decent way I could manage to free up memory properly was by swapping the to be freed ones with the last element.

Quote:
To make your code work, the algorithm you would need is std::partition(), which keeps all elements intact. You could then reliably delete all the end elements. You would need to change how you delete them though, as modifying a vector can invalidate iterators. While pop_back() shouldn't trigger a reallocation, its a bad habit to get into modifying while iterating.


Actually I was under the impression that remove_if did the partition thing. I'm guessing it's either Boost or some more messing with codes for me :(

Share this post


Link to post
Share on other sites
glopen    138
Quote:
Original post by Drigovas
2: In case 2, you are attempting to 'free' an iterator, not the object that it points to. Also, an iterator set to 'end()' doesn't just skip along as the vector shortens, so you'll be redundantly freeing the same thing.


Well, apparently the "User breakpoint called from code at 0x.." thing is likely to happen in this kind of mess ups. But how? Wouldn't 'pop_back()' change the 'end()'? In my mind, this is what I'm doing:

1. Find pointers pointing to inactive objects and send them to the back of the vector (remove_if?)
2. Starting from the end, keep 'deleting' and 'popping' the these pointers.

Shouldn't the iterator just skip along with 'end()'? I dunno.

Quote:
Pretty sure that upon fixing the issues with case 2, you'll see the same problem as with case 1 currently. I'm pretty sure why case 1 is failing, but not sure enough to blurt it out as truth....


Well, anything that tells me where the access violation occurs...

Quote:
And there is nothing wrong with using pointers.


:P

Share this post


Link to post
Share on other sites
SiCrane    11839
The normal implementation of std::remove_if() works something like this: std::remove_if<>() takes two iterators that describe a range, and a value to remove from that range. It removes the elements by copying on top of the elements to be removed with values from later on in the range. So 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
Zahlman    1682
Quote:
Original post by glopen
Okay, before you guys start flaming me for using pointers, let me just state my problems:

a) #1 causes an access violation, so there's definitely something wrong with determining the bounds.
b) #2 causes the weird "User breakpoint called from code at 0x.." in NTDLL! ...(). I gather this is an issue with the heap being corrupted, probably due to some unwarranted freeing. Apparently this only happens under WIN32 debug environment, but my game crashes even when I'm just executing the exe.


The way you say this is worrying for three reasons.

First, pre-emptive "defense" in an OP is always worthy of suspicion. If you know or suspect that people are likely to jump on you for doing something a certain way, why are you doing it that way? Are you not aware of the alternatives? If so, is your purpose to find out about them?

Second, a phrase like "before you guys start flaming me" suggests that you are about to follow up with reasons for why you are doing what you are doing. Instead, you've just gone ahead and described in more detail what goes wrong. That's useful information, sure, but it keeps one wondering.

Third, you seem worried that there is some culture of "flaming people for doing things certain ways" here. That certainly isn't intended on the part of those doing the "flaming". The goal is to find out why people are doing what they are doing, and identify and correct any delusions about what their method accomplishes or what other methods would or wouldn't accomplish.

Basically, it seems like you already have an idea that your approach is wrong (or hard to work with), but are resistant to changing it. Why?

Quote:

Quote:
Original post by Drigovas
2: In case 2, you are attempting to 'free' an iterator, not the object that it points to. Also, an iterator set to 'end()' doesn't just skip along as the vector shortens, so you'll be redundantly freeing the same thing.


Well, apparently the "User breakpoint called from code at 0x.." thing is likely to happen in this kind of mess ups. But how? Wouldn't 'pop_back()' change the 'end()'? In my mind, this is what I'm doing:

1. Find pointers pointing to inactive objects and send them to the back of the vector (remove_if?)
2. Starting from the end, keep 'deleting' and 'popping' the these pointers.

Shouldn't the iterator just skip along with 'end()'? I dunno.


"end()" is not magical. When you called it to initialize the variable 'i', you created a copy of a value which refers to the end of the vector. When you call pop_back(), the location of the end of the vector changes, but your variable's value doesn't, because it's *just a value*. The pop_back() function has no way of knowing that the variable 'i' exists in the caller's scope. Nor should it; it's your responsibility.

But that said, you don't need a variable to loop like that, anyway. What you are trying to do is:


While the .end() of the vector isn't 'j':
Clean up the allocated bullet.
.pop_back() the vector.


So, why not just write exactly that? I.e.,


while (j != bulletQ().end()) {
delete bulletQ.back(); // notice 'delete' to match 'new',
// rather than 'free' to match 'malloc'.
// Someone mentioned something about "freeing the iterator itself rather than
// what it points to", and I got confused for a second. This way is correct;
// .back() returns a reference to an element, not a pointer.
bulletQ.pop_back();
}


However, that is all missing the point - pointed out several times - that (a) 'free' is something that doesn't appear in modern C++ programs; and (b) in fact, 'new' and 'delete' also appear very, very rarely, because of tools like smart pointers and pointer containers. And the point that you don't actually want to deallocate things in this way, anyway, because the std::remove_if algorithm copies pointers around in a somewhat tricky way, so that you can't really identify "the set of pointers to bullets that are now dead". (See SiCrane's post). Thus, even if you fixed the "surface" errors, you would still have a broken program.

What you would want to do is delete the bullets when you determine that they are inactive. That is, as a part of the remove_if() process itself. That looks like:


bool isActiveBulletDeletingIfNot(bullet* b) {
if (b->isactive) { return true; }
// If it's not active, deallocate it *here*
delete b;
return false;
}

bulletQ.erase(std::remove_if(bulletQ.begin(), bulletQ.end(), isActiveBulletDeletingIfNot), bulletQ.end());

std::for_each(bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::render));


The pointers at the end of the container that are removed by the .erase() call are a mess - some might point to the still-alive bullets, some might not - but we don't care; they're garbage. We just get rid of them. We made sure with the remove_if application that there is still one pointer, in the "alive" section of hte vector, to each alive bullet, and that all "dead" bullets are *already* cleaned up.

But again - with more sophisticated tools, we don't have to implement these things ourself. And we don't have to wrap our head around weird concepts like "is active bullet, deleting if not". Which is a very strange thing for a function to do.




While I'm ranting: "bulletQ" is a poor name for a variable (I assume you're looking for a cutesy way to say "bullet queue"; but it wouldn't kill you to type the other letters, and you're not actually using the vector as a queue), and zero is not a special case (it is perfectly OK to apply std::remove_if() to an empty vector, or "iterate while i != j" even though it happens that i == j right away).

Share this post


Link to post
Share on other sites
glopen    138
Thanks wise people for all those responses.

@SiCrane:
Thanks for pointing out all the details. Come to think of it, I do actually remember a copy_if in its definition. remove_if is probably not the best way to go about it.

@Zahlman:
Okay, I mostly agree with whatever you said but there's definitely a need of some clarifications.

Quote:

Second, a phrase like "before you guys start flaming me" suggests that you are about to follow up with reasons for why you are doing what you are doing. Instead, you've just gone ahead and described in more detail what goes wrong. That's useful information, sure, but it keeps one wondering.


"Flaming" is definitely not the correct term to use for a post like this, but I guess the sense of hurry (that I was in) didn't quite carry through to the post. I just wanted to quickly state my problems in case the thread turned into a prolonged discussion about the de/merits of using pointers in general. Not exactly "flamed", but I have been "told off" for using pointers before. And come on, don't tell me you have'nt come across posts like "pointers are EEEEVIL!!" from time to time (I know I have, whatever you say).

Quote:
Basically, it seems like you already have an idea that your approach is wrong (or hard to work with), but are resistant to changing it. Why?


Because I'd really like to know where I'm going wrong, or if I understand what I'm doing? Otherwise, the discussion could've just ended with the first reply by _fastcall (which is probably the best way, I know, but I'd still be in the dark about how my code was (not) working).

Having said all that, thanks for all the info.

Quote:
bool isActiveBulletDeletingIfNot(bullet* b) {

if (b->isactive) { return true; }

// If it's not active, deallocate it *here*

delete b;

return false;

}


One question, isn't it supposed to return 'false' when the thing is active, i.e. doesn't a 'true' return value tell the algorithm to remove it?

Quote:

But again - with more sophisticated tools, we don't have to implement these things ourself. And we don't have to wrap our head around weird concepts like "is active bullet, deleting if not". Which is a very strange thing for a function to do.


:D I don't know why this is weird, I just don't know a more intuitive way.

Quote:
While I'm ranting: "bulletQ" is a poor name for a variable (I assume you're looking for a cutesy way to say "bullet queue"; but it wouldn't kill you to type the other letters, and you're not actually using the vector as a queue),..


I'd rather shoot myself than be "cutesy" with my codes, it's just that I started out using std::queue in the really early stages of coding and never got around changing it. It's actually rather addictive just pasting names of large class names and simply sticking a "Q" in the end. Nothing permanent.

Anyway, thanks for all the enlightening replies. They've definitely left me a bit wiser.

Share this post


Link to post
Share on other sites
glopen    138
EDIT: REPOST! ( Damn Firefox bugs }:[ )

EDIT2: Just wanted to add for anyone interested that the codes by rip-off (post #3)(and Zahlman, with some modifications) seem to work perfectly:

template< class T >
struct StructDeleteObjPtr {

bool operator()( T& b )
{
if (b->active) { return false; }

delete b;

return true;
}
};

...
bulletQ.erase(std::remove_if(bulletQ.begin(), bulletQ.end(), StructDeleteObjPtr<bullet*>()), bulletQ.end());
std::for_each(bulletQ.begin(), bulletQ.end(), std::mem_fun(&bullet::render));


It seems that I did this initially, but forgot to call the 'erase()' method, which caused all sorts of problems. It works now.


[Edited by - glopen on August 16, 2008 4:39:38 PM]

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by glopen
One question, isn't it supposed to return 'false' when the thing is active, i.e. doesn't a 'true' return value tell the algorithm to remove it?


Sigh. I do this kind of thing in untested code all the time. No matter how many times I have to write it :D But then, after all, why should I do all the work to ensure correctness? ;)

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