on Sun Mar 31 2013, Vadim Stadnik
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. -- Dave Abrahams