[cfe-dev] [libc++] debug mode

[Steven Watanabe]

AMDG

On 09/19/2011 04:41 PM, M.E. O'Neill wrote:
> I wrote:
>>> Feel free to suggest alternative designs or variations; my preference though is for schemes where mass iterator invalidation is O(1) (and actually fairly cheap), and the common case (valid iterators) is fast.
> 
> ... and Steven Watanabe replied:
>> mass iterator invalidation is O(1) even if you implement it by marking all valid iterators as invalid.  Recall that in the standard, O(1) means /amortized/ constant time.  The work done invalidating the iterators can always be paired off with the work done creating them in the first place.
> 
> The key with any amortized algorithm is that you shouldn't fall into the trap of repeating work in such a way as to break the amortization.
> 
> Thus, if you pair each invalidation with creation, yes, it's O(1).  But if you have to *check* multiple times whether to invalidate an iterator or not, then you exceed O(1).
> 
> For vector erase, it's not clear to me how you would (at negligible cost) know which of your zillion iterators should be invalidated and which should not.  Maybe Howard's design does this in some clever way?
> 

In any event, the messy case is invalidating
some iterators.  This is still the same under
your scheme.  The only difference is that you've
made it lazy, so we sometimes avoid the extra
work.  The worst case is still the same.

In Christ,
Steven Watanabe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: OpenPGP digital signature
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20110919/c5965b81/attachment.sig>