Thread: std::vector::erase is screwing with my pointers...

  1. #1
    Not stupid, just stupider yaya's Avatar
    Join Date
    May 2007
    Location
    Earthland
    Posts
    204

    Thumbs up std::vector::erase is screwing with my pointers...

    There must be something I'm not seeing here. All I want to do is remove a single object in my vector, and it does do this, but all of the pointers in the objects AFTER the deleted one is set to NULL.
    Hopefully this'll explain it better:

    Code:
    bool TEXTURE::RemoveTexture( UINT32 Location )
    {
    	if ( Location >= 1 && Location < Texture.size() - 1 )
    	{
    		Texture.erase( Texture.begin() + Location );
    		return true;
    	}
    
    	return false;
    };
    That is how I erase the single texture. Each object in the Texture vector is one of these babys:

    Code:
    struct TEXTUREINFO
    {
    	TEXTUREINFO() : Tex( NULL ), Name( "DefaultTextureName" ), Filename( "DefaultTextureFilename" ) {};
    	TEXTUREINFO( IDirect3DTexture9* tTex, std::string tName, std::string tFilename ) : Tex( tTex ), Name( tName ), Filename( tFilename ) {};
    	TEXTUREINFO( const TEXTUREINFO& copy );
    	~TEXTUREINFO();
    
    	TEXTUREINFO& operator=( const TEXTUREINFO& other );
    
    	IDirect3DTexture9* Tex;
    	std::string Name;
    	std::string Filename;
    };
    Now, suppose I try to remove an object in the 10th position in the vector, it will get rid of it fine. The only problem is that the Tex member in the above struct will go to NULL for everything that is after the one I just deleted. I figure that it may be calling the destructor for all of these... but why? How do I get around this?

    Thanks.

  2. #2
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    First of all, note the TWO off-by-one bugs in this line:
    Code:
    if ( Location >= 1 && Location < Texture.size() - 1 )
    Second... I assume you're storing a vector of TEXTUREINFO's directly, not a vector of pointers? In that case, yes, the object will be copied and the destructor will be invoked. I suggest storing pointers rather than the objects directly in the vector. Otherwise, you might want to use smart pointers in the structure.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Erasing an element from a vector invalidates all pointers, references and iterators to the elements after the deleted element.

    EDIT:
    Nah, a check shows that pointers are excluded, so you are not in the realm of undefined behaviour. EVOEx's explanation is probably correct then.

    EDIT #2:
    Grr... I am completely off track here. Texture is a std::vector<TEXTUREINFO>, even though this is only stated in the text, not in the code.
    Last edited by laserlight; 12-01-2009 at 12:27 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    When you remove an item from a vector, the vector must internally copy all the items after the one that was removed. I'm willing to bet the problem is that your copy constructor or assignment operator functions are incomplete.
    bit∙hub [bit-huhb] n. A source and destination for information.

  5. #5
    Not stupid, just stupider yaya's Avatar
    Join Date
    May 2007
    Location
    Earthland
    Posts
    204
    Argh... this is going to take a while to fix, then.

    @EVOEx: Yes, I just realised that -1 shouldn't be there, but the Location>=1 should be there for other reasons.

    Thanks for you super duper ultra mega quickly speedily fast replies!

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by bithub View Post
    When you remove an item from a vector, the vector must internally copy all the items after the one that was removed. I'm willing to bet the problem is that your copy constructor or assignment operator functions are incomplete.
    My bet's on that also.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by laserlight View Post
    Erasing an element from a vector invalidates all pointers, references and iterators to the elements after the deleted element.

    EDIT:
    Nah, a check shows that pointers are excluded, so you are not in the realm of undefined behaviour. EVOEx's explanation is probably correct then.
    If you are referring to a "pointer to an element", my understanding is that you were correct first time. From the perspective of the STL, a pointer to an element is an iterator.

    If the vector elements are pointers, then things change. The values of the elements are unaffected by erase() operations - or any operations that (potentially) implicitly resize the vector.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by grumpy
    If you are referring to a "pointer to an element", my understanding is that you were correct first time. From the perspective of the STL, a pointer to an element is an iterator.
    Yes, but here the standard makes a distinction between a pointer to an element obtained by the user of the container through the use of the address of operator, and an iterator of the iterator type of the container - otherwise there would be no need to specify anything about pointers separately, which it does. I believe that this is to give leeway for the implementation of such an iterator type.

    For some reason, I thought that pointers to elements of a container were being stored in other objects, and these were being invalidated.

    EDIT:
    hmm... but thinking about it further, if a reference is invalidated, then a pointer would be as well, since references are as "raw" as pointers in this respect. It is only in some cases where an iterator might be invalidated, but pointers and references are not. Therefore, my original, and your present, interpretation should be correct.
    Last edited by laserlight; 12-02-2009 at 09:34 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I don't believe the vector impl re-copies all items after the point of deletion. Pointers to the elements in the vector should be valid at all times and the vector will not alter the state of these pointers. Proof of this is creating a vector with pointers to objects on the heap and then clearing the vector. All the memory will be leaked which means the vector is not messing with the pointers at all.

    What the vector will alter is iterators. After removal all iterators and indices beyond the point of removal will be incorrect. So if you are storing size_t indices as IDs into the texture vector you must somehow notify all those texture objects that their texture ID has changed.

    There is a workaround to the limitations of vector by using it a bit differently but I am still working on it.
    Last edited by VirtualAce; 12-02-2009 at 10:01 PM.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by Bubba
    I don't believe the vector impl re-copies all items after the point of deletion.
    Refer to the C++ Standard concerning std::vector's erase member functions:
    Quote Originally Posted by C++03 Section 23.2.4.3 Paragraph 4
    The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.
    The fact that the assignment operator may be called for as many times as there are elements in the vector after the point of deletion indicates that the Standard expects such copying.

    Quote Originally Posted by Bubba
    Pointers to the elements in the vector should be valid at all times and the vector will not alter the state of these pointers.
    As I reasoned, invalidation of references should mean invalidation of pointers.
    Quote Originally Posted by C++03 Section 23.2.4.3 Paragraph 3
    Invalidates all the iterators and references after the point of the erase.
    Quote Originally Posted by Bubba
    Proof of this is creating a vector with pointers to objects on the heap and then clearing the vector. All the memory will be leaked which means the vector is not messing with the pointers at all.
    That is proof that the vector is not altering the pointers, and indeed it cannot since it has no way to know about them. However, that is not proof that the pointers remain valid after the point of deletion.

    I would like to re-iterate: I was on the wrong track because I did not perceive correctly what yaya was talking about. It is very likely that an incorrectly implemented copy assignment operator is the one that is causing yaya's objects' pointers to become null pointers.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    However, that is not proof that the pointers remain valid after the point of deletion.
    The pointer in the vector that points to the object on the heap remains valid, the pointer to the position in the vector that holds the pointer to the object on the heap does not. This is true even if you take the item on the end of the vector and stick it into the removal point and pop the last item off the vector. You can no longer iterate the vector using iterators b/c when it reaches the point of removal it will throw an exception related to incompatible iterator types. I'm working on a fix for this.

    It is very likely that an incorrectly implemented copy assignment operator is the one that is causing yaya's objects' pointers to become null pointers.
    I could see this causing memory leaks and dangling pointers but I cannot see how it would nullify or invalidate all pointers in a vector beyond the point of removal. Those objects are on the heap and the vector could care less about them. It only contains the pointers to them but so could a thousand other objects. The only way they can become invalid is if someone has called delete on them and failed to set the pointer to 0 - provided this is being checked prior to using the pointers. The only way this could be accomplished in this context is if the object is doing a delete this in it's destructor. That would definitely cause some problems.

    Code:
    struct TEXTUREINFO
    {
    	TEXTUREINFO() : Tex( NULL ), Name( "DefaultTextureName" ), Filename( "DefaultTextureFilename" ) {};
    	TEXTUREINFO( IDirect3DTexture9* tTex, std::string tName, std::string tFilename ) : Tex( tTex ), Name( tName ), Filename( tFilename ) {};
    	TEXTUREINFO( const TEXTUREINFO& copy );
    	~TEXTUREINFO();
    
    	TEXTUREINFO& operator=( const TEXTUREINFO& other );
    
    	IDirect3DTexture9* Tex;
    	std::string Name;
    	std::string Filename;
    };
    If inside the destructor you are performing a SAFE_RELEASE(Tex) this will invalidate all the textures after the point of removal. What you need is this type of vector:

    Code:
    typedef std::vector<TEXTUREINFO *> TextureVector;
    TextureVector m_textureVector;
    The only time I store the actual objects in the vector or any container is if they do not use dynamic memory and/or COM objects.

    IE:
    Code:
    ...
    struct TextInfo
    {
       DWORD color;
       std::string text;
    };
    
    typedef std::vector<TextInfo> TextVector;
    TextVector g_textVector;
    ...
    But this still does not get around the fundamental problem with vector. You cannot assign texture IDs to other objects if the ID is the index in the vector. Removal from the texture vector can cause the IDs to change thus changing all the textures that objects are depending on.
    Last edited by VirtualAce; 12-02-2009 at 10:26 PM.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by Bubba
    The pointer in the vector that points to the object on the heap remains valid
    If you are talking about a vector of pointers, and then you are saying that the elements of the vector after the point of deletion remain valid, then that is obvious

    However, this also does not back up your assertion about pointers always being valid since they are not about the elements of the vector, but pointers to elements of the vector:
    Quote Originally Posted by Bubba
    Pointers to the elements in the vector should be valid at all times and the vector will not alter the state of these pointers.
    Quote Originally Posted by Bubba
    the pointer to the position in the vector that holds the pointer to the object on the heap may not.
    That is what we're talking about.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Maybe it would be better to move all the elements you want to delete with some algorithm (std::remove_if? I don't know.) and then use erase. Not that I'm suggesting you ignore problems with your assignment operator or copy constructor.

  14. #14
    Not stupid, just stupider yaya's Avatar
    Join Date
    May 2007
    Location
    Earthland
    Posts
    204
    I changed them all to pointers (wasn't as tedious as I first thought) and it works fine. Thanks, all.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by Bubba
    I could see this causing memory leaks and dangling pointers but I cannot see how it would nullify or invalidate all pointers in a vector beyond the point of removal.
    It does not. It sounds like you are making the same mistake as I did: in the original post, yaya was talking about a vector of objects. The pointers in question are members of these objects. My point about pointer/iterator/reference invalidation is not applicable here.

    Quote Originally Posted by yaya
    I changed them all to pointers (wasn't as tedious as I first thought) and it works fine.
    Good to hear that, but you still might want to check the correctness of the copy constructor and copy assignment operator. If you do not need them since you do not want to copy, consider disabling them by declaring them private.
    Last edited by laserlight; 12-02-2009 at 10:24 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 06-06-2008, 10:10 AM
  2. Using pointers to pointers
    By steve1_rm in forum C Programming
    Replies: 18
    Last Post: 05-29-2008, 05:59 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Staticly Bound Member Function Pointers
    By Polymorphic OOP in forum C++ Programming
    Replies: 29
    Last Post: 11-28-2002, 01:18 PM