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

M.E. O'Neill oneill at cs.hmc.edu
Mon Sep 19 16:41:55 PDT 2011


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?

    M.E.O.





More information about the cfe-dev mailing list