Memory Access Violation

[Pherion]

Hello Everyone!

I've started programing back in high school, but I'm just getting back to it again for college. I'm working on a personal project to get me going again, and I've got a problem I can't figure out. Here's the relevant code:

int main(int argc, char* argv[])
{
     list<Mana> TheList;

     TheList.push_back( Mana(Mana::iRed) );
     TheList.push_back( Mana(Mana::iGreen) );
     TheList.push_back( Mana(Mana::iBlue) );
     TheList.push_back( Mana(Mana::iColorless, 5) );
     TheList.push_back( Mana(Mana::iColorless, 2) );
     TheList.push_back( Mana(Mana::iRed) );
     TheList.push_back( Mana(Mana::iGreen, 2) );

     ManaCost TheCost(&TheList);

     ManaCost NewList;
     NewList = TheCost;

     cout << NewList.GetPrintCost();

     getch();
     return 0;
}

The contents of Mana are irrelevant here, as I've tested the class thoroughly with no errors whatsoever. If you think it's relevant, I can attach the .cpp and .h files.

This function is also important:

// Function to order the costs and combine duplicates
void ManaCost::OrganizeCost()
{
     // Sort the list of mana costs
     Cost.sort();

     // Create two iterators.  One will point to the first item in the list
     // (Current).  The other will point to one item past Current (Next).
     list<Mana>::iterator Next = Cost.begin();
     list<Mana>::iterator Current = Next++;
     // Create two integers, ListSize stores size of the list, i is our counter
     int ListSize = Cost.size();
     int i = 0;

     // Initiate while loop ending when we have reached the end of the list
     while(i < ListSize)
     {
          // initiate second while loop that only executes if Next and Current
          // contain the same mana type, and it is colorless.
          while( (*Current) == (*Next) && (*Current) == Mana::sColorless )
          {
               // combine the two quantities, and delete the current contents
               // of Next
               Current->SetQty( Current->GetQty() + Next->GetQty() );
               Cost.erase(Next);
               // Set Next to the element following Current
               Next = Current;
               Next++;
               // There is now one less item in the list, so decrement ListSize
               // so we don't try to access something past the end of the list
               ListSize--;
          }
          // increment all values.
          Current++;
          Next++;
          i++;
     }
}

Finally, where the error is occurring:

ManaCost ManaCost::operator= (ManaCost& ToCopy)
{
     Cost.clear();

     int i = 0;
     int ListSize = ToCopy.GetCostSize();

     for(i = 0; i < ListSize; i++)
          Cost.push_back( *(ToCopy[i]) );

     OrganizeCost();
}

The operator function fully executes, but right after OrganizeCost is done, I get a memory access violation created by a list iterator. I've tried stepping through the program, and it looks like none of my code is throwing the violation. OrganizeCost() returns to the operator function, and then there's apparently some background stuff going on in the list container that's causing the problem. Here's the specific line that's throwing the violations (from list.h):

    allocator_type get_allocator() const
    {
      return (allocator_type)__buffer_list;
    }

    //
    // Iterators.
    //
    iterator       begin ()       { return _RWSTD_STATIC_CAST(__link_type,((*__node).next)); }  // <<-- THIS LINE!
    const_iterator begin () const { return _RWSTD_STATIC_CAST(__link_type,((*__node).next)); }

    iterator       end ()         { return __node;                      }
    const_iterator end ()   const { return __node;                      }
    reverse_iterator rbegin ()
    { 
      reverse_iterator tmp(end()); return tmp;
    }
    const_reverse_iterator rbegin () const
    { 
      const_reverse_iterator tmp(end()); return tmp;
    }
    reverse_iterator rend ()
    { 
      reverse_iterator tmp(begin()); return tmp;
    }
    const_reverse_iterator rend () const
    {
      const_reverse_iterator tmp(begin()); return tmp;
    }

I'm really at a loss here because it doesn't look like any of my code is causing the violation. I'm sure it's something I've done though!!! If I need to post more code, please let me know. Any responses are greatly appreciated!

[cire]

In ManaCost::OrganizeCost you are looping on the size of the list and the number of elements you've visited. However, you don't update i for every element you visit and you change the size of the loop inside the loop without checking to see if you've exhausted all elements. That's a recipe for disaster.

void ManaCost::OrganizeCost()
{
    if ( Cost.empty() )
        return ;

     // Sort the list of mana costs
     Cost.sort();

    std::list<Mana>::iterator next = Cost.begin() ;
    std::list<Mana>::iterator current = next++ ;

    while ( next != Cost.end()  )
    {
        if ( *current == *next && *current == Mana::sColorless )
        {
            current->SetQty( current->GetQty() + next->GetQty() ) ; 
            Cost.erase(next++) ;
        }
        else
            ++next, ++current ;
    }
}

You could greatly simplify ManaCost::operator= by letting the compiler define it. At the very least you need to return something like you say you're going to. If I had to write it by hand it would look like (note the change to the return and argument types):

ManaCost& ManaCost::operator= (const ManaCost& ToCopy)
{
    Cost = ToCopy.Cost ;
    return *this ;
}

[ne555]

ManaCost TheCost(&TheList); ¿how do you use that pointer?

while(i<ListSize){
   while( (*Current) == (*Next) //... 

In the last iteration `Current' will point to the last element.
However, `Next' is invalid and you are trying to dereference it.

You may use while( Next not_eq Cost.end() ) making a special case for an empty list.

[Pherion]

Thanks guys for the quick responses! They were immensely helpful :)

Cire, I used your code. For some reason it didn't cross my mind that list might have the = operator overloaded! I should have thought of that one LOL.

For the OrgonizeCost function, I really love how you wrote it out, but one of the problems I had writing it was incramenting Next. I wasn't sure how the iterator would respond to the ++ operator if I had already erased the object Next pointed to. I'm guessing the iterator keeps track of what the next object would have been, and ++ sends you there. Is that correct?

Also, I noticed that you wrote all of the local variables in all lowercase. Way back when I first started I developed the convention of capitalizing all of my variables. Is there a precedent for lowercase? Or is it just style?

[vigo]

Hi Pherion,

I think you're right to be nervous about the iterator increment after erase. From the list::erase() documentation:

Iterators, pointers and references referring to elements removed by the function are invalidated.

A safer way would be to use next=Cost.erase(next), which returns a valid iterator to the element after the one that was removed.

One thing, I noticed:

std::list<Mana>::iterator next = Cost.begin() ;
    std::list<Mana>::iterator current = next++ ;

Did you mean to initialize the iterators the other way around?

Also, I'm not sure about the exact logic you intended for OrganizeCost(), but as written it only combines adjacent duplicates in the list, not over all entries.

To do that would require something like:

first = std::find(Cost.begin(), Cost.end(), Mana::sColorless);
next = ++first;
while (next != Cost.end())
{
   if (*next == *first)
   {
      first->SetQty(first->GetQty() + next->GetQty()); 
      next=Cost.erase(next);
   }
   else
      ++next;  
}

[cire]

Pherion wrote:

. I'm guessing the iterator keeps track of what the next object would have been, and ++ sends you there. Is that correct?

In Cost.erase(next++) ;, a copy of next is made, next is incremented, then the copy is returned as the argument to erase. It is perfectly safe to do for a list. It wouldn't be safe for a vector, however, as iterators after the element erased are invalidated.

vigo wrote:

I think you're right to be nervous about the iterator increment after erase. From the list::erase() documentation:
Iterators, pointers and references referring to elements removed by the function are invalidated.

next does not refer to the element removed by the function. The copy fed to erase does.

Pherion wrote:

Also, I noticed that you wrote all of the local variables in all lowercase. Way back when I first started I developed the convention of capitalizing all of my variables. Is there a precedent for lowercase? Or is it just style?

It is purely a matter of style, however your style of choice isn't seen much. Whether that has any significance is for you to decide.

Vigo wrote:

Also, I'm not sure about the exact logic you intended for OrganizeCost(), but as written it only combines adjacent duplicates in the list, not over all entries

*coughsortedlistcough*

[ne555]

If you found Cost.erase(next++); weird, simply use next = Cost.erase(next); that will work with `std::vector' too.

[Pherion]

Did you mean to initialize the iterators the other way around?

Nope :) This way, Current ends up with the first iterator, and Next has the second. It only takes two lines of code. If I did it the other way around I'd have to make them both equal to Cost.begin(), then add a third line with Next++:

list<Mana>::iterator Current = Cost.begin();
list<Mana>::iterator Next = Cost.begin();
Next++;

Also, I'm not sure about the exact logic you intended for OrganizeCost(), but as written it only combines adjacent duplicates in the list, not over all entries.

Cire is correct. I've sorted the list before this loop. So yes it will only combine adjacent elements, but since the list is sorted, this is fine.


So it seems there are two options for incrementing Next:

Cost.erase(Next++);

or

Next = Cost.erase(Next);

Are there any advantages to either one. There's no overhead differences really, except for the minimal space the copy of Next takes up, but since it's just and iterator, its pretty small. The second looks clearer to me, and works with vector - but honestly I don't see myself using vectors that much when list is so much more useful (then again, I don't do this for a living - yet!). Can anyone expound upon the strengths and weakness of each method?

P.S. Missed this earlier!

¿how do you use that pointer?

Sorry ne555, I missed this one. It's just an extra constructor I included because I'm OCD and I was testing it. I also have a reference constructor (for the copy constructor), a few others. I'd have to show you the whole class for them all to make sense though.

[cire]

The second looks clearer to me, and works with vector - but honestly I don't see myself using vectors that much when list is so much more useful (then again, I don't do this for a living - yet!).

Just fyi, there are very few situations where a list will be as efficient as a vector.

Use whichever you like. It's really a matter of style. They're equally readable and both convey intent nicely. erase takes its argument by value, so there's no avoiding the copy, unless the call is inlined. I tend to prefer the first for brevity's sake, but if you ever think you might change the container type you should probably prefer the second.

[Pherion]

Cire, isn't the vector still limited by it's initial size, and list is virtually unlimited in size? Did I miss anything? LOL I don't have a really good source (book wise) for the STL right now, and the ones I do have are quite a few years old, so there may be some info I'm missing. All of the info I've read on the STL favors list over vector because it is unlimited in size - has something changed since my books were printed back in 2003? LOL

[cire]

vectors have never been limited by initial size. It sounds like you may be confusing vectors with arrays.

http://stackoverflow.com/questions/5056973/when-do-you-prefer-using-stdlistt-instead-of-stdvectort

[Pherion]

Thanks a bunch everyone. The help has been fantastic! I'm very impressed so far with how helpful everyone here is!

cire, I've done some reading and refferenced the book I was working from on vectors, and my book always initialized them with a size:

vector aVector<int>[20]

Or something to that effect. Unfortunately he never mentioned that we can expand them! So I'll definitely start using them when it's appropriate!