"Victor A. Wagner Jr." <vawjr@rudbek.com> 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