Subject: Re: [boost] Query regarding time complexity requirements of iterators in custom container
From: Rob Stewart (rob.stewart_at_[hidden])
Date: 2016-01-25 21:22:47
On January 25, 2016 5:15:31 PM EST, Soul Studios <matt_at_[hidden]> wrote:
> >> I see what you mean, however not sure if providing an additional
> >> iterator type would solve the problem from the point of view of the
> >> standard - you'd still be giving std::find and the like with an
> >> iterator
> >> and by definition that iterator must be compliant - which it
> >> wouldn't be.
> > The difference is that the user is choosing to use the
> non-conforming iterators with knowledge aforethought. Yes, it can
> increase std::find()'s complexity, which is non-conforming, but it
> will work and the user will have selected it. I see it as similar to
> using insert(begin(), value) when push_front() isn't available.
> You're missing the point. It still won't conform to the standard,
> regardless of user knowledge (which could be established via
> documentation at any rate).
No. I didn't miss the point. The user, writing standard-conforming code, would not get your random access iterators, because begin() and end() wouldn't provide them, and the range-based for loop wouldn't use them. OTOH, if the user used another means to get your random access iterators and chose to use them with std::find(), the code would be non-conforming, but might do exactly what the user wanted.
> Anyway, I've done some testing with bidirectional iterators and I'll
> sticking with them. They actually clarify and reinforce the use case
> the container, in a way, after checking them against the library I
(Sent from my portable computation engine)
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk