A Bug On Sparse Vector

I would like to thank Xing Zhou, my great work mate, who identified a bug in my code when we work together on a machine learning tool. I know it is embarrassing, but I think writing it down here helps me from making the same mistake again. Here follows my code

      SparseRealVector::const_iterator i_x = x_.begin();
      SparseRealVector::const_iterator i_new_x = new_x_.begin();

      while (i_x != x_.end() && i_new_x != new_x_.end()) {
        if (i_x->first < i_new_x->first) {
          ++i_x;
        } else if (i_new_x->first < i_x->first) {
          ++i_new_x;
        } else {                // i_x->first == i_new_x->first
          if (i_x->second * i_new_x->second < 0) {
            new_x_.set(i_new_x->first, 0);
          }
          ++i_x;
          ++i_new_x;
        }
      }

A little background about the code: we use the STL map container to hold the sparse vector, and SparseRealVector::const_iterator is just stl::map::const_iterator. Different from map, when we set an element to 0, SparseRealVector::set will remove this element. The bug lies in the last “else” branch. In the case of (i_x->second * i_new_x->second < 0), we execute new_x_.set(i_x->first, 0) which removes the element pointed by i_new_x. This makes i_new_x a semantically dangling iterator. In practice, i_new_x now points to the elements next to the deleted one. Then ++i_new_x will further move to the next element. In general, this skips one element in new_x. So, the correct code should be:

  if (i_x->second * i_new_x->second < 0) {
    const_iterator temp = i_new_x + 1;
    new_x_.set(i_new_x->first, 0);
    i_new_x = temp;
  } else {
    ++i_new_x;
  }
  ++i_x;