Jump to content
  • Advertisement
Sign in to follow this  
zappernapper

vectors and iterators

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

does anyone know why using iterators to go through a vector is more reliable than using the random access notation []? i.e:
for (int i = 0; i < myVec.size(); ++i)
  delete myVec;  //myVec is a vector of pointers
myVec.clear();
doesn't necessarily always work as expected as opposed to
vector<MyObj*>::iterator iObj;
        for (iObj= myVec.begin(); iObj!= myVec.end(); iObj++)
        {
            delete (*iObj);
            myVec.erase(iObj);
            iObj--;
        }
which works correctly but requires more code and more chance for error Thanks for any light someone can shed on this subject! -zappernapper **please note: any criticism of typos is unappreciated, as this was just an example and not ACTUAL code

Share this post


Link to post
Share on other sites
Advertisement
The two pieces of code you posted do different things. The first just deletes the pointers.. ie. deallocates the memory the pointers point to. The actual pointers remain in the vector. The second piece of code removes the pointers from the vector as well as deallocating the memory pointed to. Also, I think erase invalidates iterators (not sure though).

myVec.erase(iObj);
iObj--;

Should be:
iObj=myVec.erase(iObj);

erase returns the element after the element erased.

In general, using a for loop with an index variable works just as well as iterators. It's just easier to use an iterator if you're deleting elements. Also, I think iterators might be faster sometimes (anyone know?)

Share this post


Link to post
Share on other sites
Quote:
Original post by dyerseve
Also, I think erase invalidates iterators (not sure though).


It is generally correct: erase() invalidates the iterator you pass it.

Share this post


Link to post
Share on other sites
right, which is why i use --iterator, which moves it to a valid location, and using myvec.clear() in the first example does the same thing as erase in the second, thereby getting rid of all the pointers, after freeing the memory... this question arose because i had a game that would crash after i would try to resart it because the bitmaps and backgrounds i had in vectors were SUPPOSED to be cleared, but apparently they weren't, because refilling the vectors caused access violations. in short, iterators worked, access notation didn't, but they should each work equally well in this situation and i don't understand why they don't... any ideas?

Share this post


Link to post
Share on other sites
Quote:
Original post by zappernapper
right, which is why i use --iterator, which moves it to a valid location


No, once you've called erase(iObj), you're not allowed to touch iObj at all. You may not increment it, you may not decrement it, you may not dereference it. It has been invalidated. If you try that with any other container but std::vector, bad things will happen.

Quote:
were SUPPOSED to be cleared, but apparently they weren't


What did you do to test whether the vector had really been cleared or not? Did you check size() and capacity()?

Quote:
because refilling the vectors caused access violations.


How were you 'refilling' the vectors?

Quote:
please note: any criticism of typos is unappreciated, as this was just an example and not ACTUAL code


The onus is on you to give an example that reflects the actual code you have problems with, otherwise any advice we give you may prove inaccurate.

Share this post


Link to post
Share on other sites
Quote:

How were you 'refilling' the vectors?

myVec.push_back();

Quote:
Quote:
please note: any criticism of typos is unappreciated, as this was just an example and not ACTUAL code


The onus is on you to give an example that reflects the actual code you have problems with, otherwise any advice we give you may prove inaccurate.
[/quote]

I understand this in most cases, but all to often i'll beasking something similar to this and just retyping something general, and people will start commenting that i forgot a semicolon, not ever answering the original question... it's just frustrating to deal with that when i've already checked for typos, and typos (like semicolons, but obviously not variable names) usually come out during compilation, not as access violations.

following are code fragrments from the actual prog... again, it works using iterators, but NOT []:

//main
g_pGraphics->CleanupAll(); //empties the vectors as discussed above
g_pGraphics->AddBackground(IDB_BG);
g_pGraphics->AddBackground(IDB_WALL, 0, true, RGB(0, 0, 0));

g_pBallSprite = g_pGraphics->AddSprite(IDB_BALL, g_rcPlayfield, 0, 0,
BA_BOUNCE, 0, true);

// graphic engine
void GraphicEngine::CleanupAll()
{
CleanupSprites(); // work similar to emptying the bitmap vector
CleanupBackgrounds();
CleanupForegrounds();
if(!m_vBitmaps.empty())
{
vector<Bitmap*>::iterator biBitmap;
for (biBitmap = m_vBitmaps.begin(); biBitmap != m_vBitmaps.end(); biBitmap++)
{
delete (*biBitmap);
m_vBitmaps.erase(biBitmap);
biBitmap--;
}
}
m_vBitmaps.clear();

}
/* used to be
void GraphicEngine::CleanupAll()
{
CleanupSprites();
CleanupBackgrounds();
CleanupForegrounds();
if(!m_vBitmaps.empty())
for (int i = 0; i < m_vBitmaps.size(); ++i)
delete m_vBitmaps;
m_vBitmaps.clear();
}*/

...
void GraphicEngine::AddSprite(Sprite* pSprite)
{
// Add a sprite to the sprite vector
if (pSprite != NULL)
{
// See if there are sprites already in the sprite vector
if (m_vSprites.size() > 0)
{
// Find a spot in the sprite vector to insert the sprite by its z-order
vector<Sprite*>::iterator siSprite;
for (siSprite = m_vSprites.begin(); siSprite != m_vSprites.end(); siSprite++)
if (pSprite->GetZOrder() < (*siSprite)->GetZOrder())
{
// Insert the sprite into the sprite vector
m_vSprites.insert(siSprite, pSprite);
return;
}
}

// The sprite's z-order is highest, so add it to the end of the vector
m_vSprites.push_back(pSprite);
}
}
...
Sprite* GraphicEngine::AddSprite(...)
{
HDC hDC = GetDC(m_hWindow);
if ((hDC != NULL) && (m_hInstance != NULL))
{
Bitmap* newBit = new Bitmap(hDC, uiResID, m_hInstance, bTrans, crTransColor);
if (newBit != NULL)
{
m_vBitmaps.push_back(newBit);
POINT v = {0, 0};
POINT pos = {xPos, yPos};
Sprite* newSprite = new Sprite(newBit, pos, v, ZOrder, rcBounds, baAction);
AddSprite(newSprite);
return newSprite;
}
}
return NULL;
}
// the add background works similarly but with fewer variables



Quote:

What did you do to test whether the vector had really been cleared or not? Did you check size() and capacity()?

doesn't clear() do that reliably? or in which cases wouldn't it?

hopefully that's enough info

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Quote:
Original post by dyerseve
Also, I think erase invalidates iterators (not sure though).


It is generally correct: erase() invalidates the iterator you pass it.

In this specific case it doesn't matter, but its worth pointing out that in the case of vectors erase() also invalidates all iterators after the one you pass to it.

As for the specific problem, where exactly do you get the access violation?

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by zappernapper
doesn't clear() do that reliably? or in which cases wouldn't it?


While it will remove all the elements, whether or not clear() also sets the capacity to zero is undefined. Though looking at your code, I don't see why the indexing-based approach might fail. Sorry. You're going to have to use your debugger to find out when, where and how the problems happen.

Incidentally, for your AddSprite function, you might consider having a look at std::lower_bound and other sorted-range algorithms. insert() also works correctly when you use end() as the insertion point.

Share this post


Link to post
Share on other sites
vector<MyObj*>::iterator iObj;
for (iObj = myVec.begin(); iObj != myVec.end(); iObj = myVec.erase(iObj))
delete(*iObj);
There, now it's as short as your first example. Corrected too of course.
The problem you are having is most likely caused by other code.

btw, Does anyone have a link to the run-time complexities of functions such as clear()? I've seen implementations of it for maps that simply use erase. But doesn't that make it O(nlogn)? I rekon it should be O(n), thus deleting all items afterwards would be faster.

[Edited by - iMalc on September 11, 2005 1:56:06 PM]

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!