Time complexity of debug/checked iterators
- 0
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
Answers
- 0
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."
All Replies
- 0
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...
- 0We 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.
