有什么技术原因为什么std :: lower_bound不专门用于红黑树迭代器？

有什么技术原因为什么std :: lower_bound不专门用于红黑树迭代器？

没有技术原因无法执行此 *** 作。

为了演示，我将勾勒出一种实现方法。

我们添加了一个新的Iterator类别

SkipableIterator

。它是的子类型

BiDirectionalIterator

和的超类型

RandomAccessIterator

。

SkipableIterator

s确保

between

在

std::between

可见的上下文中完成该功能。

template<typeanme SkipableIterator>SkipableIterator between( SkipableIterator begin, SkipableIterator end )

between

返回介于

begin

和之间的迭代器

end

。

end

当且仅当

++begin ==end

（

end

紧接在

begin

）之后才返回。

从概念上讲，

between

应该有效地找到

begin

和之间的“大约一半”的元素

end

，但是我们应该小心允许随机跳转列表或平衡的红黑树同时起作用。

随机访问迭代器的实现非常简单

between

-

return (begin + ((end-begin)+1)/2;

添加新标签也很容易。只要它们正确使用了标记分派（并且没有明确地专门化），派生就可以使现有代码很好地工作，但是这里很少涉及破坏。我们可以使用“标记版本”

iterator_category_2

来完善

iterator_category

（或减少黑客行为），也可以使用完全不同的机制来讨论可跳过的迭代器（独立的迭代器特性？）。

一旦具备此功能，我们就可以编写适用于

map

/

set

和的快速排序搜索算法

multi

。它也可以在跳过列表容器（如）上工作

QList

。它甚至可能与随机访问版本相同！