"Alan Stokes" <alan@alanstokes.org.uk> writes:
On 18/06/06, David Abrahams <dave@boost-consulting.com> wrote:
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.
The "checked iterators" just include a check to make sure you don't go beyond the end of a container (or do various other bad things);
Like dereferencing an invalid iterator. which requires somehow identifying the iterators that have become invalid.
I don't think this breaches any of the complexity requirements.
How do you do that without looking at all the iterators to see if they're pointing at the node being deleted?
The MS library in a debug build does include some code that is non-conformant because of the performance requirements. For example, the binary search family of algorithms first checks that the range is properly ordered (so they're O(N) instead of O(log N)). But the release builds don't have those checks and so don't breach the requirements.
Is that a distinct switch from the one that makes iterators checked?
I believe your argument was that boost should disable checked iterators by default (even though they are enabled by default by the compiler) because they were non-conforming. If that isn't true then I suggest staying with the compiler default.
Yes, but is it true? A quick inspection of the <list> header suggests that it is. -- Dave Abrahams Boost Consulting www.boost-consulting.com