Jump to content
  • Advertisement
Sign in to follow this  
ChaosIII

STL remove oddity

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

Hi! I recently implemented a Texture-class into my project based on the cTexture example in Eamonn Doherty's article: See here. However, the displayed method to clean up unreferenced textures always produced an invalid iterator - exception so I changed it and employed the STL remove algorithm instead. See here. Now since this algorithm includes copying and moving the objects inside the list / vector I expected that some of the pointers to these objects (held by the texture-class instances) could become invalid, for the actual object they pointed to might have been copied to another location and then removed. Surprisingly this doesn't seem to be the case. None of my testruns produced any bugs or assertion failures. The pointers still seem to point to the right location (i.e. the new copy of the original object). Can anyone explain this please? Here is the actual code I use:
//typedef std::vector<TEXTURE_INSTANCE*> TextureList;

HRESULT D3DCore::Texture::cleanUnreferenced() {
	TextureList::iterator it;
	int matchCount = 0;
	
	for(it = sm_texList->begin(); it != sm_texList->end(); it++) {
		if((*it)->referenceCount <= 0) {
			if((*it)->texture) (*it)->texture->Release();
			(*it)->texture = NULL;
			delete (*it);

			matchCount++;
		}
		else if(matchCount > 0) {
			*(it-matchCount) = *it;
		}
	}
	it = sm_texList->end();
	sm_texList->erase(it-matchCount, it);
	
	return D3D_OK;
}



Share this post


Link to post
Share on other sites
Advertisement
Erasing or inserting elements into a vector will invalidate the iterators, not the objects contained in them. If you were using a non-POD type (A pointer is a POD type), you'd see the copy constructor and/or operator=() called on the object. However, POD types don't have either.

Share this post


Link to post
Share on other sites
1) Why not just use boost::shared_ptr?
2) If the pointers are in the vector, how could the pointed-at things be "unreferenced"?
3) How could a reference count be *less than* zero?
4) Why not use a standard library algorithm for this kind of traversal, such as std::remove_if? (It seems to be exactly what you're reinventing here).
5) Don't write 'else if (opposite of the other condition)'. Just write 'else'. You wouldn't say "if it is raining, I'll take my umbrella, otherwise, if it is not raining, I'll put on some sunscreen and a hat" in English: the emboldened part is purely redundant.
6) There's no way for this function to "fail" (except to crash), so what's the point of returning a success code?

tl;dr: simplify.

Share this post


Link to post
Share on other sites
1) Cause I never heard of them.
2) Yup ... thanks ... problem understood!!!
3) Just a precaution.
4) Read the code again. The "if" is not redundant.
5) I like to do things my way. ;-)
6) You're right!

Thanks!

Share this post


Link to post
Share on other sites
Also, another point in favor of remove_if is that it should be more efficient than erasing individual items at a time because it doesn't erase them immediately. Instead, it gives you an iterator so you can erase them all at once after the call to remove_if. In general, that means far less memory being shuffled around.

Share this post


Link to post
Share on other sites
Quote:
Original post by ChaosIII
4) Read the code again. The "if" is not redundant.


Er, yes. :x

Ravyne, his code does that optimization. He deletes pointers one at a time (which can't be optimized anyway, although it can be cleaned up considerably with smart pointers), and erases in one go.

Still.

Assuming that it's deliberate that the vector could contain pointers to "unreferenced" things, that means it holds "weak" pointers (i.e. ones that don't affect the lifetime of the object). These are modelled in Boost by boost::weak_ptr (with the assumption that there are also boost::shared_ptrs lurking around that also point to the same thing).

In this case, the code becomes simply:


// You will need to #include <algorithm> in addition to what you have
// (and of course the relevant Boost headers :) )
//typedef boost::weak_ptr<TEXTURE_INSTANCE> WeakTexPtr;
//typedef std::vector<WeakTexPtr> TextureList;

// The TEXTURE_INSTANCE class gets replaced simply by its 'texture' member,
// which then does the Release() work in its destructor. The shared_ptr already
// contains a reference count, so you can throw away your existing one.

// Or you could try to make it work with boost::intrusive_ptr instead :)

// I like to encapsulate "the erase-remove idiom" as a function of its own...
template <typename Container, typename Predicate>
void filter_out(C& c, P undesired) {
c.erase(std::remove_if(c.begin(), c.end(), undesired), c.end());
}

void D3DCore::Texture::cleanUnreferenced() {
// Why do you point at the vector in the first place?
TextureList& textures = *sm_textList;
// 'expired' means there are no more living shared_ptrs to the
// corresponding TEXTURE_INSTANCE.
filter_out(textures, std::mem_fun_ref(&WeakTexPtr::expired));
}

Share this post


Link to post
Share on other sites
Well first off, the code really doesn't have to be super-efficient. It won't be called often and probably only during loading sequences anyway.
Right now I am satisfied with the fact that everything "works" just fine, but I'll make a note and maybe have another look into it in the end when I get to the optimization part ... ^^

Share this post


Link to post
Share on other sites
The original code looks pretty hairy to me.

This appears to be breaking encapsulation:
			if((*it)->texture) (*it)->texture->Release();
(*it)->texture = NULL;

and this just makes my spidey sense tingle[smile]:
			*(it-matchCount) = *it;

Instead of subtracting matchcount to get a new iterator, you could simply use two iterators, a source and a dest iterator. Then I notice that the algorithm being used is basically the same as remove_if.
Zahlman has this all sorted out in the code he posted.

Share this post


Link to post
Share on other sites
Quote:
Original post by ChaosIII
Well first off, the code really doesn't have to be super-efficient. It won't be called often and probably only during loading sequences anyway.
Right now I am satisfied with the fact that everything "works" just fine, but I'll make a note and maybe have another look into it in the end when I get to the optimization part ... ^^


I'd like to note that I didn't say anything about optimization, except to observe that you'd already done one - which is also done by the standard library algorithm. [smile]

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Ravyne, his code does that optimization. He deletes pointers one at a time (which can't be optimized anyway, although it can be cleaned up considerably with smart pointers), and erases in one go.


Ah yes, I should have read it more carefully. I'll note to the OP, though, that you are reinventing the remove_if wheel. The fact that my first look over the code was incorrect yields evidence that the one-off approach will introduce difficulty in maintenance later. On the other hand, a remove_if based solution (As Zahlman showed) is a single line that anyone who rightly calls himself a C++ programmer can immediately know what it does without any mental parsing and arithmetic. It also limits potential errors because it provides a known solution for the loop and copy mechanisms, leaving only the determination of what should be deleted up to the author. If you're going to go as far as using std::vector, you should be using remove_if as well; the standard algorithms were, of course, designed to be used with the standard containers.

I'll also back up the suggestions made by iMalc, the design of the texture container does certainly seem to break encapsulation, and the second bit of code took too much mental arithmetic to parse correctly, even when I went back to look at the code a second time. If you cannot be convinced to switch to remove_if, at least replace matchCount with a second iterator... although, again, at that point you will literally be recreating what is likely to be a typical implementation of remove_if word-for-word.

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!