Time complexity of debug/checked iterators

Question

Hi.

I've heard that the C++ iterators in Visual Studio 2005 (checked iterators and debug iterators), do not meet to time complexity (big-O) specifications required by the C++ standard. I tried to find some documentation about it, but found nothing. Is there some paper describing this nonconformance, or maybe I'm wrong and the iterators are fully confomant?

Thanks,
Yuval

Answer 1

Hi: I passed your question on to Bill Plauger who is the author of the C++ Standard Library that ships with Visual C++. Here is his response.

"MS tried pretty hard to ensure that checked iterators were reasonably

fast and, more importantly, had proper time complexity. Debug iterators also

meet time complexity requirements, but the algorithms that use them (in the

container member functions and the headers <algorithm> and <numeric>) don't.

It's a fine point, perhaps, but an important one."

 

Answer 2

Thanks for the answer.

When you say "MS tried pretty hard to ensure that checked iterators ... had proper time complexity", do you mean "tried and succeeded", or "tried and failed"? I couldn't quite figure it out from the answer...

And I really think that adding a similar explanation to the relevant MSDN pages is a good idea...

Answer 3

We mean "Tried and succeeded". Of course if you have examples of cases where this is not the case we'd love to hear about them.