Subject: Re: [boost] Query regarding time complexity requirements of iterators in custom container
From: Soul Studios (matt_at_[hidden])
Date: 2016-01-24 16:15:15
> IIRC, these operators are O(log N), right? So you can provide an
> operator+ that is more efficient than std::advance would be, right?
Close enough - in best case it approximates O(1), in worst case O(N),
general case probably closer to O(log N).
> I had a similar issue with a filtering iterator adaptor over a
> std::vector::iterator; is that bidirectional or random access?
> Its operator< is O(1) but its operator+ is O(N).
Must be a very strange underlying model if the + operator is anything
other than O(1)? At any rate, vector iterators are random access.
> Perhaps at some point in the future we'll have a more fine-grained
> set of concepts that allow us to define iterator features more
> precisely. For the time being, you should definitely implement
> the operators (if I'm right about them being logarithmic), and
> then decide whether to declare the iterator to be random-access or
> not. Weigh up the merits of strict compliance vs. pragmatism.
> If you don't declare it as random access, what happens? You might
> like to consider, for example, that some std algorithms are
> documented to require random access iterators - but typically
> work in practice with other iterators as long as they implement the
> required operators.
Yes, we lose access to std::find in particular under GCC I think.
I'll remove them for the moment, which's a shame since the code took a
long time to write, but I don't see any way around it, unless anybody
else has input on the matter.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk