# 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;
```