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: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2016-01-23 13:35:19

Soul Studios wrote:
> currently working on Colony,

Links might help for those who don't know what that is :-)

> last version I'm working on has achieved constant-time(amortised) 
> time-complexity for iterator operations, except for the random-access 
> operators (+, -, +=, -=, [], >, <, >=, <=). It's not possible to make 
> these constant-time due to the nature of the algorithms and structure of 
> container.
> Ion pointed out to me that there is an obscure C++ requirement for 
> iterators that all operations be constant-time.
> Given this, is it worth keeping these in Colony before submitting to 
> Boost, or would it be best to remove them and make the iterator 
> bidirectional-only prior?

IIRC, these operators are O(log N), right?  So you can provide an
operator+ that is more efficient than std::advance would be, right?

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).

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.

Regards,  Phil.