Re: [boost] Bug/Incompatibility: Visual C++ 2005 checkediteratorslead to major crashes

From: David Abrahams (dave_at_[hidden])
Date: 2006-06-18 15:33:46

"Victor A. Wagner Jr." <vawjr_at_[hidden]> writes:

>>In the mode where std::vector<T>::iterator is "checked."  The type
>>has the right syntax and mostly the right semantics but doesn't meet
>>the complexity requirements to be a conforming iterator.
>
> I looked at the standard and I don't see anything other than "must be 
> constant" for the operators provided, hence the missing "complexity 
> column" from the tables.  I understand they take much longer to 
> execute than the non checked ones, but I don't find any loops (which 
> would indicate an O(n) or worse) in  <vector> .
> All the conditional code seems to be in the same path and executed no 
> more often which makes it difficult to see how it changes big-O

You may be right.  Frankly I've never looked at the code used by MS
and was going based on hearsay and dimly remember past experience with
STLPort.

IIRC from STLPort there are some operations that have to walk the
entire list of iterators into a container (hence a loop), but I'm not
sure if that affects conformity.  std::list<T>::erase, perhaps?
That's supposed to be O(1) and maybe that becomes O(N) where N is the
number of iterators into the list.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com