是否有任何技术原因导致std :: lower_bound不专门用于红黑树迭代器？

Question

std::lower_bound()如果我将一对红黑树迭代器(set::iterator或map::iterator)传递给它,我总是假设以对数时间运行.std::lower_bound()在这种情况下,至少在libstdc ++实现中,我必须自己两次燃烧以注意在O(n)时间运行.据我所知,该标准没有红黑树迭代器的概念; std::lower_bound()将它们视为双向迭代器,advance并将它们视为线性时间.我仍然没有看到任何理由为什么实现无法为红黑树迭代器创建特定于实现的迭代器标记, 并且lower_bound()如果传入的迭代器恰好是红黑树迭代器则调用专用.

是否有任何技术原因std::lower_bound()不专门用于红黑树迭代器？

---

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

---

赏金到期后:我发现Mehrdad和Yakk的答案最有说服力.我也无法决定; 我正在给予Mehrdad赏金并接受Yakk的回答.

Answer 1

原因有很多:

1. 使用非成员版本时,可以使用不同的谓词.事实上,不同的谓词具有使用,例如,当使用std::map<K, V>作为地图谓词上操作Ks,而在上范围的对操作K和V.
2. 即使谓词是兼容的,该函数也有一个接口,它使用树中某处的一对节点而不是有效搜索所需的根节点.尽管可能存在父指针,但对树的要求似乎是不合适的.
3. 提供给算法的迭代器不需要是树的t.begin()和t.end().它们可以位于树中的某个位置,使得树结构的使用可能效率低下.
4. 标准库没有树抽象或在树上运行的算法.虽然关联有序容器[可能]是使用树实现的,但相应的算法不会暴露给一般用途.

我认为值得怀疑的部分是使用通用名称的算法,该算法具有双向迭代器的线性复杂度和随机访问迭代器的对数复杂度(我理解比较的数量在两种情况下都具有对数复杂度,并且运动被认为是快点.

Answer 2

(阐述评论)

我认为可以提供一个与提供的谓词不同的谓词,std::set并且仍然满足部分排序(对于特殊集合)的要求.因此,lower_bound如果谓词等效于std::set排序,则只能用特殊的红黑版本替换算法.

例:

#include <utility>
#include <algorithm>
#include <set>
#include <iostream>

struct ipair : std::pair<int,int>
{
    using pair::pair;
};

bool operator<(ipair const& l, ipair const& r)
{  return l.first < r.first;  }

struct comp2nd
{
    bool operator()(ipair const& l, ipair const& r) const
    {  return l.second > r.second; /* note the > */ }
};

std::ostream& operator<<(std::ostream& o, ipair const& e)
{  return o << "[" << e.first << "," << e.second << "]";  }

int main()
{
    std::set<ipair, comp2nd> my_set = {{0,4}, {1,3}, {2,2}, {3,1}, {4,0}};
    for(auto const& e : my_set) std::cout << e << ", ";

    std::cout << "\n\n";

    // my_set is sorted wrt ::operator<(ipair const&, ipair const&)
    //        and       wrt comp2nd
    std::cout << std::is_sorted(my_set.cbegin(), my_set.cend()) << "\n";
    std::cout << std::is_sorted(my_set.cbegin(), my_set.cend(),
                                comp2nd()) << "\n";

    std::cout << "\n\n";

    // implicitly using operator<
    auto res = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{3, -1});
    std::cout << *res;

    std::cout << "\n\n";

    auto res2 = std::lower_bound(my_set.cbegin(), my_set.cend(), ipair{-1, 3},
                                 comp2nd());
    std::cout << *res2;
}

输出:

[0,4], [1,3], [2,2], [3,1], [4,0], 

1
1

[3,1]

[1,3]

Answer 3

好问题.老实说,我认为没有好的/令人信服的/客观的理由.

我在这里看到的几乎所有原因(例如谓词要求)对我来说都不是问题.它们可能不方便解决,但它们是完全可解的(例如,只需要一个typedef来区分谓词).

我在最顶层的答案中看到的最有说服力的理由是:

尽管可能存在父指针,但对树的要求似乎是不合适的.

但是,我认为假设父指针已经实现是完全合理的.

为什么？因为如果迭代器指向正确的位置,set::insert(iterator, value)则保证时间复杂度是分摊的恒定时间.

考虑一下:

1. 树必须保持自我平衡.
2. 保持树平衡需要在每次修改时查看父节点.

你怎么能避免在这里存储父指针？

如果没有父指针,为了确保插入后树是平衡的,必须每次从根开始遍历树,这肯定不是分摊的常量时间.

我显然不能在数学上证明不存在可以提供这种保证的数据结构,所以很明显我错了,这是可能的.
然而,如果没有这样的数据结构,我的意思是,这是一个合理的假设,通过这样一个事实:所有的实现给定的set和map我见过其实红黑树.

旁注,但请注意,我们根本无法lower_bound对C++ 03中的函数(如)进行部分特化.
但这并不是一个真正的问题,因为我们可以只使用专门的类型,并将调用转发给该类型的成员函数.

Answer 4

没有技术原因可以解决这个问题.

为了演示,我将草拟一种实现这一点的方法.

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

SkipableIterators保证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(或更少hacky)的细化,或者我们可以使用完全不同的机制来讨论可跳过的迭代器(一个独立的迭代器特征？).

一旦我们具备了这种能力,我们就可以编写一个快速有序的搜索算法,该算法适用于map/ set和multi.它也可以在跳过列表容器上工作QList.它甚至可能与随机访问版本的实现相同!