Sign in to follow this  

STL remove oddity

This topic is 3625 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
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
*takes-a-deep-breath*

Where to start? OK ... the apparent break of encapsulation. TEXTURE_INSTANCE isn't really a class but a struct holding information about the texture and therefore doesn't really provide any encapsulation. I could of course turn it into a class and let a simple call to the destructor do all the dirty work. I admit that kind of approach would probably be more in the spirit of OOP. Anyway ... the actual Texture class I was talking about in my first post merely holds a (private) pointer to the corresponding TEXTURE_INSTANCE and provides access only through public functions of course.
As for me reinventing the wheel ... well, as I said before. I like to do things my way. I started programming in C++ only just recently so I am still in a preocess of learning (as every programmer probably is for the rest of his career ^^). My point is, I simply don't want to rely that much on stuff others did for me already and blindly take it for granted. Of course this isn't always possible, but I really don't mind reinventing the wheel here or there if it gives me some deeper insight in the processes behind something.
Just looking up an algorithm in the documentation and calling the corresponding function is much easier forgotten than writing the actual algorithm yourself, understanding it thoroughly while doing so. Right now I am coding for myself so I really don't care about other's "mental arithmetic to parse correctly". No offence, Ravyne! =)
Did I forget something? Oh yeah the implementation of a second iterator. Could someone give me a hint as to how to do that? Because right now it only looks like a complication of things to me. What's wrong with my matchCount? It seems to work just fine ...

Share this post


Link to post
Share on other sites
The mental arithmetic and parsing matters because weeks or months from now, when you come back to it, you won't have the understanding of how it really works, only the understanding that you once understood that it works, and an assumption that your understanding then still holds true; an assumption that may or may not be valid. For example, what if you decide to support multi-threading, or if you decide to go back and make that encapsulated struct a proper class?

I do agree that there is a valuable learning experience to be had by writing it yourself, and kudos on the superb algorithmic optimization you've included; I think most people would have written a more naive implementation. But now you've done it and its out of the way. You've conquered remove_if on your own terms, so now its time to make it your bitch, rather than typing it over again and again[grin].

There's code that works, and then there's code that's elegant. The difference is that elegant code is concise and immediately clear in its intention. Every programmer should strive to write elegant code.

As for how to implement your code in terms of two iterators, simply create two iterators, read and write, both at the beginning of the collection. When an item is removed, only move the read iterator forward. When an item is not removed, check if write is less than read, if so: copy the contents of read into write, then move both iterators forward. When write read reaches container.end(), write will point to the first item that needs to be erased or container.end() if no items were removed(ie the iterator that remove_if returns.)

Something like: (only mentally tested, may have bugs)

HRESULT D3DCore::Texture::cleanUnreferenced() {
TextureList::iterator write = sm_texList->begin(),
read = sm_texList->begin();

while(read != sm_texList->end())
{
if((*read)->referenceCount <= 0)
{
if((*read)->texture)
(*read)->texture->Release();

(*read)->texture = NULL;
delete (*read);
}
else
{
if(write < read)
*(write) = *read;

write++
}

read++;
}

sm_texList->erase(write, read);

return D3D_OK;
}





[Edited by - ravyne2001 on January 10, 2008 1:37:37 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by ravyne2001
You've conquered remove_if on your own terms, so now its time to make it your bitch, rather than typing it over again and again[grin].

Agreed! ^^

And thanks for the code. It looks just fine.

Share this post


Link to post
Share on other sites

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