我一直假设std::lower_bound()如果我将一对红黑树迭代器（set::iterator或map::iterator）传递给它，则它会以对数时间运行。std::lower_bound()在这种情况下，我至少要消耗O 两次才能运行，至少要使用libstdc ++实现。我了解该标准没有红黑树迭代器的概念；std::lower_bound()会将它们视为双向迭代器，advance并在线性时间内将它们视为。 我仍然看不到为什么该实现无法为红黑树迭代器创建特定于实现的迭代器标签， 并且lower_bound()如果传递的迭代器恰好是红黑树迭代器，则无法调用专门的原因。
std::lower_bound()
set::iterator
map::iterator
advance
lower_bound()
有什么技术原因为什么std::lower_bound()不专门针对红黑树迭代器？
更新： 是的， 我知道find成员函数，但这不是重点。 （在模板代码中，我可能无权访问该容器或只能在一部分容器上工作。）
赏金到期后： 我发现Mehrdad和Yakk的答案最有说服力。我也无法决定。我要悬赏Mehrdad并接受Yakk的回答。
没有技术原因无法执行此操作。
为了演示，我将勾勒出一种实现方法。
我们添加了一个新的Iterator类别SkipableIterator。它是的子类型BiDirectionalIterator和的超类型RandomAccessIterator。
SkipableIterator
BiDirectionalIterator
RandomAccessIterator
SkipableIterators确保between在std::between可见的上下文中完成该功能。
between
std::between
template<typeanme SkipableIterator> SkipableIterator between( SkipableIterator begin, SkipableIterator end )
between返回介于begin和之间的迭代器end。end当且仅当++begin == end（end紧接在begin）之后才返回。
begin
end
++begin == end
从概念上讲，between应该有效地找到begin和之间的“大约一半”的元素end，但是我们应该小心允许随机跳转列表或平衡的红黑树同时起作用。
随机访问迭代器的实现非常简单between-return (begin + ((end-begin)+1)/2;
return (begin + ((end-begin)+1)/2;
添加新标签也很容易。只要它们正确使用了标记分派（并且没有明确地专门化），派生就可以使现有代码很好地工作，但是这里很少涉及破坏。我们可以使用“标记版本” iterator_category_2来完善iterator_category（或减少黑客行为），也可以使用完全不同的机制来讨论可跳过的迭代器（独立的迭代器特性？）。
iterator_category_2
iterator_category
一旦具备此功能，我们就可以编写适用于map/ set和的快速排序搜索算法multi。它也可以在跳过列表容器（如）上工作QList。它甚至可能与随机访问版本相同！
map
set
multi
QList
