vectors and iterators

Started by
8 comments, last by iMalc 18 years, 7 months ago
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
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?)
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.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
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?
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.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
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.


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 []:
//maing_pGraphics->CleanupAll(); //empties the vectors as discussed aboveg_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 enginevoid 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 bevoid 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
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
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.
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
Another thing you might want to consider is using boost::shared_ptr with STL containers rather than naked pointers.

There's an example of how to do this in the article Using Modern C++ to Eliminate Memory Problems.
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]
"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

This topic is closed to new replies.

Advertisement