Home
Blogs
Forums
News
Portfolios
Projects
Tutorials
36 users logged in
New? Learn about game development.
Before posting, review our community guidelines.
Follow Us
Chat in the GameDev.net Discord!
Mastodon
Back to General and Gameplay Programming

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

Started by
12 comments, last by Zahlman 15 years, 8 months ago
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.
Advertisement
I'd recommend using boost::ptr_list (Quick tutorial) when dealing with STL and pointers. It works the same as STL, but takes ownership of the pointers you give it, and will delete them for you.
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 heretypedef 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.
blog | twitter
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]
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.
blog | twitter
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).
blog | twitter
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.
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 :(
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

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.

This topic is closed to new replies.

Advertisement

Popular Topics

Aybe One
How do you manage yourself and your time as years pass on? GDNet Lounge
ReignOnU
Do your part to stop global warming and climate change GDNet Lounge
Konjointed
C++ how do you use dependency injection? For Beginners
Jikoob
Too many managers? General and Gameplay Programming
aigan
The promise of freedom in story games Game Design and Theory
konev13
Syncing 3D animation with hitboxes General and Gameplay Programming
Advertisement

Recommended Tutorials

Myopic Rhino
Cel-Shading Graphics and GPU Programming
Thibault Ober
Shadow Mapping in depth analysis Graphics and GPU Programming
Carsten Germer
Postmortem: "Pavel Piezo - Trip to the Kite Festival", a game for learning languages Production and Management
Myopic Rhino
Security Issues of Online Gaming Networking and Multiplayer
gdarchive
Cross-Platform Game Development with Xamarin and MonoGame General and Gameplay Programming

Reticulating splines

About GameDev.net
Community Guidelines
Terms of Service
Privacy Policy
Contact Us
Copyright (c) 1999-2024 GameDev.net, LLC
Back to Top