Re: [boost] Query regarding time complexity requirements of iterators in custom container

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.