Iterator issue in BranchFolder::RemoveBlocksWithHash?

Hi all,

I updated from 2.2 to the latest SVN head and I now get a debug assert in BranchFolder::RemoveBlocksWithHash: “vector iterators incompatible”. I’m using Visual C++ 2005. I think this is the culprit code:

MergePotentials.erase(CurMPIter);

if (CurMPIter==B)

break;

The erase clears the _Mycont field (i.e. the iterator’s container), while the == expects CurMPIter and B to have the same container. I’m no STL guru but it seems wrong to first erase an element and then try to compare it. I traced it back to revision 50921 made on May 10’th. I rewrote it like following, which I’m not entirely sure is the intended behavior but it ‘works for me’:

CurMPIter = MergePotentials.erase(CurMPIter);

if (CurMPIter==B)

break;

Kind regards,

Nicolas Capens

Thanks for analyzing the problem.

I also am not a STL guru; the standard says erase
“Invalidates all the iterators and references after the point of the erase”
which is not wonderfully worded, but I take it to mean an iterator referring to the point of the erase remains valid…But if it doesn’t work that way on VC++, it doesn’t. Now I know.

It’s clearly better to call erase only once, so I’ve rewritten it that way. Please make sure it works for you.

Hi Dale,

I looked deeper into it and your patch is excellent I think. Thanks.

The STL documentation is indeed a bit unclear. After a bit of Googling it looks like a lot of people faced this issue. But the documentation doesn’t define what the iterator points to after the erase, so logically it is invalidated as well. There’s one trick get predictable behavior in a convenient way though:

v.erase(i–);

The post-decrement moves the iterator to the previous element (which will remain valid) before the erase call, while actually still returning the iterator to the element we want to erase.

Cheers,

Nicolas

I updated from 2.2 to the latest SVN head and I now get a debug assert in BranchFolder::RemoveBlocksWithHash: “vector iterators incompatible”. I’m using Visual C++ 2005. I think this is the culprit code:

    MergePotentials.erase(CurMPIter);
    if (CurMPIter==B)
      break;

The erase clears the _Mycont field (i.e. the iterator’s container), while the == expects CurMPIter and B to have the same container. I’m no STL guru but it seems wrong to first erase an element and then try to compare it. I traced it back to revision 50921 made on May 10’th. I rewrote it like following, which I’m not entirely sure is the intended behavior but it ‘works for me’:

    CurMPIter = MergePotentials.erase(CurMPIter);
    if (CurMPIter==B)
      break;

Thanks for analyzing the problem.

I also am not a STL guru; the standard says erase
"Invalidates all the iterators and references after the point of the erase"
which is not wonderfully worded, but I take it to mean an iterator referring to the point of the erase remains valid....

From n2461:

8 The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

Pretty clear.

If you play with --i, be careful of iterators that point to the beginning.

I also am not a STL guru; the standard says erase
"Invalidates all the iterators and references after the point of the
erase"
which is not wonderfully worded, but I take it to mean an iterator
referring to the point of the erase remains valid....

From n2461:

8 The insert members shall not affect the validity of iterators and
references to the container, and the erase members shall invalidate
only iterators and references to the erased elements.

Pretty clear.

In the current standard that language appears under "associative containers", but this is a vector. Has it been moved?
The language I quoted applies specifically to vectors.

In any event, I'm not arguing that this ought to work, just that the (current) standard is badly worded.

If you play with --i, be careful of iterators that point to the
beginning.

Thanks, I've already hit that one.

From n2461:

8 The insert members shall not affect the validity of iterators and
references to the container, and the erase members shall invalidate
only iterators and references to the erased elements.

Pretty clear.

In the current standard that language appears under "associative
containers", but this is a vector.

Ah, and from vector:

23.2.5.4 vector modifiers [vector.modifiers]

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
4 Effects: Invalidates iterators and references at or after the point of the erase.

:slight_smile: Sorry, didn't realize this was vector and the page this was on was marked container requirements and I didn't realize I was reading just the associative container requirements.

In any event, I'm not arguing that this ought to work, just that the
(current) standard is badly worded.

I think it was a bug in the original language standard. You can ask Howard, if you're curious.

There's a proposed resolution to fix this:

http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#414

Looks like it's being fixed, anyway. Good.