Расхождения между std :: lower_bound и std :: set :: lower_bound - PullRequest
Новая
       36

Расхождения между std :: lower_bound и std :: set :: lower_bound

4 голосов
/ 20 сентября 2011

В проекте 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, 
                            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.

Обратите внимание, что это позволяет (косвенно) сравнивать другой (но сопоставимый) тип, который вернул бы *ForwardIterator, но нетограничение сложности на число продвижений итераторов.(Для контейнера на основе узла это будет O (последний - первый) шаг итератора.) 

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

Стандарт не детализирует эти функции, но подразумевается, что они предназначены для O (log2 (последний- сначала)) сравнения и улучшения, но требуется, чтобы ключ поиска был таким же, как и содержащийся тип.

Итак, мои вопросы:
(1) Есть ли способ получить скорость * 1011?* и гибкость типа поиска std::lower_bound?
(2) Почему std::lower_bound не требуется специализироваться для std::set::iterator?
(3) Существуют ли реализации, где std::lower_bound специализируется на std::set::iterator, или есть причина, почему нет?

Я надеялся найти что-то вроде: 

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

или: 

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;
   ...
}

Но я сомневаюсь, что оно существует.Очевидно, что все это можно распространить на другие древовидные контейнеры и другие алгоритмы.Я сам написал бы код, но для этого потребовалось бы использовать специфический для реализации код.Эта идея возникла из этого вопроса: Эффективный поиск в наборе с неключевым типом

1 Ответ

4 голосов
/ 20 сентября 2011
Контейнер

A std::set заказывается в соответствии с объектом сравнения, который предоставляется во время строительства. Когда вызывается std::lower_bound, нет способа проверить, что ему был передан соответствующий объект сравнения, поэтому реализация не может знать, использовать ли стандартный алгоритм или специализированный для наборов, так как последний действителен только при использовании объект сравнения, используемый для упорядочения набора (или объект, который дает те же результаты).

Два примера прототипов, которые вы добавили, не будут работать:

  1. Специализация std::lower_bound для работы на std::set итераторах:

    Это не будет работать по причине, указанной выше: нет способа проверить, соответствует ли данный объект сравнения объекту, указанному в конструкторе набора. Ваш прототип только проверяет, соответствует ли тип объекта сравнения, но могут быть разные объекты сравнения одного типа.

  2. Заставить std::set::lower_bound принять аргумент шаблона:

    Это может сделать его несовместимым с объектом сравнения набора, поскольку operator() этого объекта обычно не будет шаблонным и ожидает только аргументы типа T.

...