Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2006-06-19 14:32:43


"Alan Stokes" <alan_at_[hidden]> writes:

> On 18/06/06, David Abrahams <dave_at_[hidden]> 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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk