Iterator disfunctionality

Question

I have a code in which I basically have positive values and negative values. The negative values represent operators('+'=-1,'-'=-2,'*'=-3,'/'=-4) and I basically have to either divide, to make the sum and so on of the 2 numbers preceding the negative value.

std::list<long>::iterator i,j;
for(i=num.begin();++i!=num.end();)
{
            if(*i<0&&num.size()>=2)
            {
                    if(*i==-1)
                    {
                              *i=*--(j=i)+*----(j=i);
                    }
                    else if(*i==-2)
                    {
                              *i=*----(j=i)-*--(j=i);
                    }
                    else if(*i==-3)
                    {
                              *i=*--(j=i)**----(j=i);
                    }
                    else if(*i==-4&&*--(j=i)!=0)
                    {
                              *i=*----(j=i)/(*--(j=i));
                    }//this part is working properly
                    num.erase(--(j=i));
                    num.erase(--(j=i));//here is the only problem
                    break;
    }
}

Apparently, I am trying to erase a value from the list that doesn't exist.

Answer 1

You have undefined behaviour with:

*--(j=i) + *----(j=i);

where you modify several times j in unspecified order. using std::prev would solve that and would make the code cleaner.

Answer 2

Stepping aside from the fact that some of your code is undefined behavior and completely unnecessarily cryptic.

std::list<long>::iterator i,j;
for(i=num.begin();++i!=num.end();)
{
    // ...
    num.erase(std::prev(i));
    num.erase(std::prev(i));
}

We know num.size() >= 2, but we don't know that i is at least 2 past begin so there are actually two things to erase. It's likely that your first and/or second runs through the loop are trying erase nonexistent iterators.

[edit] Apparently your loop check is ++i != num.end(). First, don't do that. Second, I guess that effectively means that you're starting one past begin, so that's why you fail on the 2nd erase in the first iteration of the loop:

[begin] <--> [item] <--> [item] <--> ...
             ^
             i

You're trying to erase the two items in front of i. There is only one.

Answer 3

There are a couple of things seriously wrong with your code:

• In expressions like *--(j = i) + *----(j = i), the compiler is free to rearrange the operators in just about any way that doesn't violate direct dependencies. So it might do the two assignments first, then the three decrementations, and finally the two dereferences (resulting in something equivalent to *(i - 3) + *(i - 3)). Or it might do the assignment and the two decrements on the right, then the assignment and the decrement on the left, and then the two dereferences, resulting in the equivalent of *(i - 1) + *(i - 1). Or any number of other combinations. (If i and j were pointers, and the operators built-in types, you'd have undefined behavior.) As a general rule: no expression should have more than one side effect. Not only because of order of evaluation issues, but because you want people to be able to read your code. (This comment also holds for things like ++i != num.end(); with few exceptions, a condition of a for, while or if shouldn't have side effects.)

• Erasing elements of a container when iterating over it should be avoided, unless you really know what you are doing. Depending on the type of the container, it might invalidate your iterators; in the case of std::list, it shouldn't, as long as the element being erased isn't the one designated by the iterator, but it's very difficult to understand where your iterator ends up. In your case, you don't seem to take any precautions for the case where i points to the second element; if you try to erase the element in front of it twice, you're going to be in trouble.

Finally, it looks to me that you're trying to evaluate an expression in RPN. I'll pass on the fact that you're using negative values to indicate operators—a better solution would be a struct, with a field for the operator, and a field for the value (ignored in the case of operators like '+'). Something like:

enum Operator
{
    push,
    add,
    sub,
    mult,
    div
};

struct Term
{
    Operator op;
    long value;
};

But the classical way of implementing this would be a stack of values: iterate over the expression without mutating it, pushing values onto the stack, and popping, doing the operation and pushing the results for the operators. If the expression is valid, you'll end up with exactly one element on the stack: verify this, and that there are at least enough elements for the operators.

And don't forget that there is such a thing as a switch. Your loop should be something like:

std::stack<long> stack;
for ( auto current = num.cbegin(), end = num.cend(); current != end; ++ current ) {
    switch ( current->op ) {
    case push:
        stack.push( current->value );
        break;
    //  ...
    }
}
if ( stack.size() != 1 ) {
    //  error...
} else {
    //  results are the only remaining element on the stack.
}