On Mon, Apr 1, 2013 at 12:40 AM, Dave Abrahams
on Sun Mar 31 2013, Vadim Stadnik
wrote: The algorithms that implement random access to container elements by index (also often named 'rank') are efficient search algorithms using counters of elements stored in tree nodes. These algorithms are similar to algorithms searching an element by a key that support functions of associative containers, such as c.lower_bound(key) and c.upper_bound(key). In the general case, both kinds of search algorithms on trees have the same logarithmic running time. However, the augmented array based B+ trees have an important advantage over red-black trees. They offer constant time access to the nearest container elements in the worst case against constant amortized time. Thus, these new data structure can provide the efficiency of sequential processing close to that of std::vector.
Ah. Seems like we don't have appropriate concepts to characterize these things. What do you say about the big-O when the dominating factor will always have such a small constant that it becomes insignificant? It feels like a cop-out, but I guess I'd go with random_access.
Asymptotically, most of operators of these new iterators have O(1) cost, this group includes increment, decrement and comparison operators. However, a few operators {+= , -=, +, -, [ ]} have O(log N) cost. Quite obviously, such iterators are much closer to random access iterators than to bidirectional. In addition to this, without std::random_access_iterator_tag user algorithms can not take full advantage of the efficient algorithms offered by augmented data structures. The running time can increase quite significantly from O(log N) to O(N), since standard library algorithms would use the subset of operators of bidirectional iterators only. Regards, Vadim Stadnik