I have a rope container using a self-balancing order-statistic tree as its underlying storage (each tree node containing a variable but in general fairly numerous elements of the rope, for example if storing chars the tree nodes are likely to hold ~4000 elements).
Is it reasonable to assign the rope iterators the std::random_access_iterator_tag iterator_category even though the +, +=, -, -=, etc operations are actually logarithmic complexity (in terms of distance from the current position)? If the new position lies within the current tree node (which should be much more frequent than larger jumps) then the operation is in fact O(1)as required by random access, it is only when needing to step along the tree that the true O(1) complexity is lost. However in all cases it is much better than O(n) as using bidirectional would imply.
I could, of course, make up my own category tag but I would then need to specialize the various free-standing algorithm functions to take advantage.
Perhaps this is an opinion question that is not really suitable to SO but I am still curious what people think about this issue.
Suppose you are using a container from a library. The library's documentation claims the container's iterators satisfy the requirements of a random access iterator. Your program has performance issues, which you trace back to those iterators' increment operator being O(lg n) instead of O(1). Would you feel justified in complaining / filing a bug report? Probably.
Do you want to write code that others will complain about? Probably not. Your mileage may vary, but it is usually better to understate performance than overstate it. Few people complain that computations are too fast.