std :: lower_bound和std :: set :: lower_bound之间的差异 [英] Discrepencies between std::lower_bound and std::set::lower_bound

问题描述

C ++草稿说明了关于std :: lower_bound：

 §25.4.3.1 lower_bound [lower.bound] 
 template< class ForwardIterator，class T> 
 ForwardIterator lower_bound（ForwardIterator first，
 ForwardIterator last，
 const T& value）; 
 template< class ForwardIterator，class T，class Compare> 
 ForwardIterator lower_bound（ForwardIterator first，
 ForwardIterator last，
 const T& value，
比较comp）; 
 
要求：[first，last]的元素e应该按照
分区为表达式e <值或comp（e，值）。 
返回：范围[first，last]中的最远迭代器i，使得对于
，范围[first，i）中的任何迭代器j都满足以下对应的
条件：* j< value或comp（* j，value）！= false。 
复杂性：最多log2（last-first）+ O（1）比较。 
  

请注意，这允许（通过暗示）比较不同c $ c> * ForwardIterator 将返回，但是对迭代器提升的数量没有复杂性限制。 （对于基于节点的容器，这将是O（last-first）迭代器进度。）

 §23.4.6.1 
 class set {
 ... 
 iterator lower_bound（const key_type& x）; 
 const_iterator lower_bound（const key_type& x）const; 
 ... 
} 
  

标准没有详细说明这些功能，但它暗示这些是用于O（log2（last-first））比较和进步，但要求搜索键与包含的类型相同。

我的问题是：

（1）是否有办法获得 std :: set :: lower_bound 的速度和搜索类型的灵活性 std :: lower_bound ？

（2）为什么 std :: lower_bound 是专门为 std :: set :: iterator ？

（3）是否有实现 std :: lower_bound 是专门为 std :: set :: iterator ，还是有理由为什么不？

我希望能找到类似的东西：

 类Key，类Comp，类Alloc，类Lookup> 
 std :: set< Key，Compare，Alloc> :: const_iterator 
 lower_bound（
 std :: set< Key，Comp，Alloc> :: const_iterator begin，
 std： ：set< Key，Comp，Alloc> :: const_iterator end，
 const Lookup& find，
比较comp）; 
 template<类Key，类Comp，类Alloc，类Lookup> 
 std :: set< Key，Compare，Alloc> :: iterator 
 lower_bound（
 std :: set< Key，Comp，Alloc> :: iterator begin，
 std： ：set< Key，Comp，Alloc> :: iterator end，
 const Lookup& find，
比较comp）; 
  

或：

 code> template< class Key，class Compare = less< Key>，class Allocator = allocator< Key> > 
 class set {
 ... 
 template< class Lookup> 
 iterator lower_bound（const Lookup& x）; 
 template< class Lookup> 
 const_iterator lower_bound（const Lookup& x）const; 
 ... 
} 
  

但我怀疑它存在。显然，所有这些都可以扩展到其他基于树的容器，以及其他算法。我自己编写代码，但它需要我使用实现特定的代码。这个想法来自这个问题：使用非键类型设置的有效搜索

解决方案

订购了 std :: set 容器根据在施工时给出的比较对象。当调用 std :: lower_bound 时，没有办法检查是否传递了匹配的比较对象，因此实现无法知道是使用标准算法还是一个专用于集合，因为后者仅在使用用于集合排序的比较对象（或给出相同结果的比较对象）时才有效。

两个示例原型

工作 std :: set 迭代器：

这将不工作原因如上：没有办法检查给定的比较对象是否匹配集合的构造函数中给定的。

制作 std :: set :: lower_bound 采用模板参数：

这可能会使其与集合的比较对象不兼容， c $ c> operator（）通常不会被模板化，并且只需要类型 T 的参数。

The C++ draft says about std::lower_bound:

§ 25.4.3.1 lower_bound [lower.bound]  
template<class ForwardIterator, class T>  
ForwardIterator lower_bound(ForwardIterator first, 
                            ForwardIterator last, 
                            const T& value);  
template<class ForwardIterator, class T, class Compare>  
ForwardIterator lower_bound(ForwardIterator first, 
                            ForwardIterator last, 
                            const T& value, 
                            Compare comp);  

Requires: The elements e of [first,last) shall be partitioned with respect 
    to the expression e < value or comp(e, value).
Returns: The furthermost iterator i in the range [first,last] such that for 
    any iterator j in the range [first,i) the following corresponding 
    conditions hold: *j < value or comp(*j, value) != false.
Complexity: At most log2(last − first) + O(1) comparisons.

Note that this allows (by implication) one to compare a different (but comparable) type than *ForwardIterator would return, but there's no complexity limitation on the number of iterator advancements. (For a node based container, this would be O(last − first) iterator advancements.)

§ 23.4.6.1
class set { 
   ...
    iterator lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
   ...
}

The standard doesn't detail these functions, but it's implied that these are for O(log2(last − first)) comparisons and advancements, but require the search key to be the same as the contained type.

So my questions are:
(1) Is there a way to get the speed of std::set::lower_bound and the flexibility of search type of std::lower_bound?
(2) Why isn't std::lower_bound required to be specialized for std::set::iterator?
(3) Are there implementations where std::lower_bound is specialized for std::set::iterator, or is there a reason why not?

I was hoping to find something like:

template< class Key, class Comp, class Alloc, class Lookup>  
std::set<Key, Compare, Alloc>::const_iterator 
    lower_bound(
        std::set<Key, Comp, Alloc>::const_iterator begin, 
        std::set<Key, Comp, Alloc>::const_iterator end, 
        const Lookup& find,
        Compare comp);
template< class Key, class Comp, class Alloc, class Lookup>  
std::set<Key, Compare, Alloc>::iterator 
    lower_bound(
        std::set<Key, Comp, Alloc>::iterator begin, 
        std::set<Key, Comp, Alloc>::iterator end, 
        const Lookup& find,
        Compare comp);

or:

template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> >
class set {
   ...
    template<class Lookup>
    iterator lower_bound(const Lookup& x);
    template<class Lookup>
    const_iterator lower_bound(const Lookup& x) const;
   ...
}

But I doubt it exists. Obviously, all of this can be expanded to other tree-based containers, and other algorithms. I'd code it myself, but it would require me to use implementation specific code. This idea came from this question: Efective search in set with non-key type

解决方案

A std::set container is ordered according to a comparison object that is given at construction time. When std::lower_bound is called, there is no way to check that it was passed a matching comparison object, so the implementation can't know whether to use the standard algorithm or one specialized to sets, as the latter is only valid when using the comparison object used for the set's ordering (or one which gives the same results).

The two example prototypes you added won't work:

1. Specializing std::lower_bound to work on std::set iterators:

   This won't work for the reason given above: There is no way to check if the given comparison object matches the one given in the set's constructor. Your prototype only checks that the type of the comparison object matches, but there can be different comparison objects of the same type.

2. Making std::set::lower_bound take a template argument:

   This may make it incompatible with the set's comparison object, since that object's operator() will usually not be templated, and expects only arguments of type T.

这篇关于std :: lower_bound和std :: set :: lower_bound之间的差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！