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.