c++ - Is there any technical reason why std::lower_bound is not specialized for red-black tree iterators?

Question

I have always assumed that std::lower_bound() runs in logarithmic time if I pass a pair of red-black tree iterators (set::iterator or map::iterator) to it. I had to burn myself twice to notice that std::lower_bound() runs in O(n) time in this case, at least with the libstdc++ implementation. I understand that the standard doesn't have the concept of red-black tree iterators; std::lower_bound() will treat them as bidirectional iterators and advance them in linear time. I still don't see any reason why the implementation couldn't create an implementation specific iterator tag for red-black tree iterators and call a specialized lower_bound() if the passed in iterators happen to be red-black tree iterators.

Is there any technical reason why std::lower_bound() is not specialized for red-black tree iterators?

---

UPDATE: Yes, I am aware of the find member functions but it is so not the point. (In a templated code I may not have access to the container or work only on a part of container.)

---

After the bounty has expired: I find Mehrdad's and Yakk's answers the most convincing. I couldn't decide between the too; I am giving the bounty to Mehrdad and accepting Yakk's answer.

Answer 1

There are multiple reasons:

1. When using the non-member version a different predicate can be used. In fact, a different predicate has to be used when using, e.g., a std::map<K, V> as the map predicate operates on Ks while the range operates on pairs of K and V.
2. Even if the predicate is compatible, the function has an interface using a pair of nodes somewhere in the tree rather than the root node which would be needed for an efficient search. Although it is likely that there are parent pointers, requiring so for the tree seems inappropriate.
3. The iterators provided to the algorithm are not required to be the t.begin() and the t.end() of the tree. They can be somewhere in the tree, making the use of the tree structure potentially inefficient.
4. The standard library doesn't have a tree abstraction or algorithms operating on trees. Although the associative ordered containers are [probably] implemented using trees the corresponding algorithms are not exposed for general use.

The part I consider questionable is the use of a generic name for an algorithm which has linear complexity with bidirectional iterators and logarithmic complexity with random access iterators (I understand that the number of comparisons has logarithmic complexity in both cases and that the movements are considered to be fast).