Given an empty array, I need to make two type of queries
it = st.find(k);
idx = distance(st.begin(), it);
No. It is not possible (with the predefined containers). The sequence containers of the C++ Standard Library have either:
deque is an exception, but only when the insertion/removal takes place at the ends of the array. The general case is still O(N).
Furthermore, the classification of iterators does not include a category for this case. You have the bidirectional iterators (those of
multimap), which take O(N) time to jump to a random position, and the next category is for random access iterators (those of
string). There is no intermediate category.
Adding a new category would not be trivial at all. The library also implements a lot of algorithms (like
for_each) that work with containers. There is an implementation for every iterator category.
Order statistic trees have been proposed at Boost several times. As far as I know:
The main difficulty for them being accepted was the generalized opinion that they were not a benefit, but a hazard. Today's programmers are used to solve all the problems they know with the typical containers. Experienced programmers fear that newbies might blindly use the proposed container for everything, instead of choosing carefully.