llvm dev - May 2008 - [LLVMdev] 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080523/9af5f6b1/attachment.html>

On May 23, 2008, at 4:10 AM, Nicolas Capens wrote:
> 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;
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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080523/2bdb4ccf/attachment.html>

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

 

  _____  

From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On
Behalf Of Dale Johannesen
Sent: Friday, 23 May, 2008 19:20
To: LLVM Developers Mailing List
Subject: Re: [LLVMdev] Iterator issue in BranchFolder::RemoveBlocksWithHash?

 

 

On May 23, 2008, at 4:10 AM, Nicolas Capens wrote:





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;

 

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.

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080524/8d3a4853/attachment.html>

On May 23, 2008, at 10:19 AM, Dale Johannesen wrote:
> On May 23, 2008, at 4:10 AM, Nicolas Capens wrote:
>
>> 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.