Time complexity of debug/checked iterators
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
回答
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."
すべての返信
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."
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...
- 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.
