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.
Dietmar Kühl :
There are multiple reasons:\n\n\nWhen 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.\nEven 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.\nThe 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.\nThe 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.\n\n\nThe 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).",
2014-01-05T15:28:46
Yakk - Adam Nevraumont :
There is no technical reason why this could not be implemented.\n\nTo demonstrate, I will sketch out a way to implement this.\n\nWe add a new Iterator category, SkipableIterator. It is a subtype of BiDirectionalIterator and a supertype of RandomAccessIterator.\n\nSkipableIterators guarantee that the function between done in a context where std::between is visible works.\n\ntemplate<typeanme SkipableIterator>\nSkipableIterator between( SkipableIterator begin, SkipableIterator end )\n\n\nbetween returns an iterator between begin and end. It returns end if and only if ++begin == end (end is right after begin).\n\nConceptually, between should efficiently find an element \"about half way between\" begin and end, but we should be careful to allow a randomized skip list or a balanced red black tree to both work.\n\nRandom access iterators have a really simple implementation of between -- return (begin + ((end-begin)+1)/2;\n\nAdding a new tag is also easy. Derivation makes existing code work well so long as they properly used tag dispatching (and did not explicitly specialize), but there is a small concern of breakage here. We could have \"tag versions\" where iterator_category_2 is a refinement of iterator_category (or soemthing less hacky), or we could use a completely different mechanism to talk about skipable iterators (an independent iterator trait?).\n\nOnce we have this ability, we can write a fast ordered searching algorithms that works on map/set and multi. It would also work on a skip list container like QList. It might be even the same implementation as the random access version!",
2014-01-06T02:32:15
user541686 :
Great question. I honestly think there's no good/convincing/objective reason for this.\n\nAlmost all the reasons I see here (e.g. the predicate requirement) are non-issues to me. They might be inconvenient to solve, but they're perfectly solvable (e.g. just require a typedef to distinguish predicates).\n\nThe most convincing reason I see in the topmost answer is:\n\n\n Although it is likely that there are parent pointers, requiring so for the tree seems inappropriate.\n\n\nHowever, I think it's perfectly reasonable to assume parent pointers are implemented.\n\nWhy? Because the time complexity of set::insert(iterator, value) is guaranteed to be amortized constant time if the iterator points to the correct location. \n\nConsider that:\n\n\nThe tree must stay self-balancing.\nKeeping a tree balanced requires looking at the parent node at every modification. \n\n\nHow can you possibly avoid storing parent pointers here? \n\nWithout parent pointers, in order to ensure the tree is balanced after the insertion, the tree must be traversed starting from the root every single time, which is certainly not amortized constant time.\n\nI obviously can't mathematically prove there exists no data structure that can provide this guarantee, so there's clearly the possibility that I'm wrong and this is possible.\nHowever, in the absence of such data structures, what I'm saying is that this is a reasonable assumption, given by the fact that all the implementations of set and map I've seen are in fact red-black trees.\n\n\n\nSide note, but note that we simply couldn't partially-specialize functions (like lower_bound) in C++03.\nBut that's not really a problem because we could have just specialized a type instead, and forwarded the call to a member function of that type.",
2014-01-05T22:13:01
dyp :
(Elaborating on a comment)\n\nI think it's possible to supply a predicate that is not equivalent to the one supplied to std::set and still fulfil the requirement of partially sorted (for special sets). So you can only replace the lower_bound algorithm by a special red-black version if the predicate is equivalent to the std::set ordering.\n\nExample:\n\n#include <utility>\n#include <algorithm>\n#include <set>\n#include <iostream>\n\nstruct ipair : std::pair<int,int>\n{\n using pair::pair;\n};\n\nbool operator<(ipair const& l, ipair const& r)\n{ return l.first < r.first; }\n\nstruct comp2nd\n{\n bool operator()(ipair const& l, ipair const& r) const\n { return l.second > r.second; /* note the > */ }\n};\n\nstd::ostream& operator<<(std::ostream& o, ipair const& e)\n{ return o << \"[\" << e.first << \",\" << e.second << \"]\"; }\n\nint main()\n{\n std::set<ipair, comp2nd> my_set = {{0,4}, {1,3}, {2,2}, {3,1}, {4,0}};\n for(auto const& e : my_set) std::cout << e << \", \";\n\n std::cout << \"\\n\\n\";\n\n // my_set is sorted wrt ::operator<(ipair const&, ipair const&)\n // and wrt comp2nd\n std::cout << std::is_sorted(my_set.cbegin(), my_set.cend()) << \"\\n\";\n std::cout << std::is_sorted(my_set.cbegin(), my_set.cend(),\n comp2nd()) << \"\\n\";\n\n std::cout << \"\\n\\n\";\n\n // implicitly using operator<\n auto res = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{3, -1});\n std::cout << *res;\n\n std::cout << \"\\n\\n\";\n\n auto res2 = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{-1, 3},\n comp2nd());\n std::cout << *res2;\n}\n\n\nOutput:\n\n[0,4], [1,3], [2,2], [3,1], [4,0], \n\n1\n1\n\n[3,1]\n\n[1,3]",
2014-01-05T14:48:22