问题描述

我一直假设 std::lower_bound() 以对数时间运行，如果我传递一对红黑树迭代器(set::iterator 或 map::iterator) 到它.我不得不烧了自己两次才能注意到 std::lower_bound() 在这种情况下以 O(n) 时间运行，至少在 libstdc++ 实现中是这样.我知道标准没有红黑树迭代器的概念；std::lower_bound() 会将它们视为双向迭代器，并在线性时间内 advance 它们.我仍然不明白为什么实现不能为红黑树迭代器创建一个实现特定的迭代器标签并调用一个专门的 lower_bound() 如果通过in 迭代器恰好是红黑树迭代器.

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.

std::lower_bound() 不是专门用于红黑树迭代器的，有什么技术原因吗?

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

更新:是的，我知道 find 成员函数，但这不是重点.(在模板化代码中，我可能无法访问容器或仅在容器的一部分上工作.)

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.)

赏金到期后:我发现 Mehrdad 和 Yakk 的回答最有说服力.我也无法在两者之间做出决定；我给 Mehrdad 赏金并接受 Yakk 的回答.

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.

推荐答案

没有技术原因无法实施.

There is no technical reason why this could not be implemented.

为了演示，我将勾勒出实现这一点的方法.

To demonstrate, I will sketch out a way to implement this.

我们添加了一个新的迭代器类别，SkipableIterator.它是 BiDirectionalIterator 的子类型和 RandomAccessIterator 的超类型.

We add a new Iterator category, SkipableIterator. It is a subtype of BiDirectionalIterator and a supertype of RandomAccessIterator.

SkipableIterator 保证函数 between 在 std::between 可见的上下文中完成.

SkipableIterators guarantee that the function between done in a context where std::between is visible works.

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

between 返回 begin 和 end 之间的迭代器.它返回 end 当且仅当 ++begin == end(end 紧跟 begin 之后).

between returns an iterator between begin and end. It returns end if and only if ++begin == end (end is right after begin).

从概念上讲，between 应该有效地找到一个大约介于"begin 和 end 之间的元素，但我们应该小心允许随机跳过列表或平衡的红黑树都可以工作.

Conceptually, 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.

随机访问迭代器有一个非常简单的between实现——return (begin + ((end-begin)+1)/2;

Random access iterators have a really simple implementation of between -- return (begin + ((end-begin)+1)/2;

添加新标签也很容易.只要现有代码正确使用标签调度(并且没有明确专门化)，派生就会使现有代码运行良好，但这里有一个小问题.我们可以有标签版本"，其中 iterator_category_2 是 iterator_category 的改进(或者更简单的东西)，或者我们可以使用完全不同的机制来讨论可跳过的迭代器(一个独立迭代器特征?).

Adding 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?).

一旦我们有了这个能力，我们就可以编写一个快速有序的搜索算法，适用于map/set 和multi.它也适用于像 QList 这样的跳过列表容器.它甚至可能与随机访问版本的实现相同！

Once 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!

这篇关于std::lower_bound 不专门用于红黑树迭代器是否有任何技术原因?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！