Функция set.lower_bound с парами - PullRequest
Новая
       74

Функция set.lower_bound с парами

0 голосов
/ 08 апреля 2020

Я узнал, что функция set.lower_bound (key) возвращает значение из набора как можно ближе к ключу, мне было интересно, как это работает, когда переданный ключ является парой (скажем, x, y координаты точки) набор содержит пары.

Я столкнулся с этим в следующем фрагменте кода 

 int compare(pairll a, pairll b)
{ 
        return a.px<b.px; 
}
double closest_pair(pairll pnts[],int n)
{
        sort(pnts,pnts+n,compare);
        double best=INF;
        set<pairll> box;
        box.insert(pnts[0]);
        int left = 0;
        for (int i=1;i<n;++i)
        {
            while (left<i && pnts[i].px-pnts[left].px > best)
                box.erase(pnts[left++]);
            for(typeof(box.begin()) it=box.lower_bound(make_pair(pnts[i].py-best, pnts[i].px-best));it!=box.end() && pnts[i].py+best>=it->py;it++)
                best = min(best, sqrt(pow(pnts[i].py - it->py, 2.0)+pow(pnts[i].px - it->px, 2.0)));
            box.insert(pnts[i]);
        }
        return best;
}

1 Ответ

2 голосов
/ 08 апреля 2020

Я узнал, что функция set.lower_bound (key) возвращает значение из набора как можно ближе к клавише

Прежде всего, это ложь. Всегда лучше обратиться к cppreference для получения правильной информации. Вот что нужно сказать о std :: set :: lower_bound:

Возвращает итератор, указывающий на первый элемент, ключ которого не меньше (то есть больше или равен).

Следовательно, это не элемент как можно ближе , а первый элемент, больший или равный.

Мне было интересно, как он работает, когда передаваемый ключ является парой (скажем, x, y координаты точки), т.е. набор содержит пары.

Как это будет работать для любого другого типа T. Внутренне он реализован как BST (обычно в виде красно-черного дерева). Следовательно, поиск O(nlogn). Какой порядок / компаратор использовал ты говоришь? std :: set в основном: 

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

Как видите, он принимает компаратор в качестве параметра шаблона со значением по умолчанию std :: less . Следовательно, он

проверяет, меньше ли первый аргумент, чем второй

Вы спрашиваете, как он сравнивает две пары? Вот что говорит c на std :: pair :

Сравнивает lhs и rhs лексикографически по оператору <, то есть сравнивает первые элементы и только если они эквивалентны, сравнивает вторые элементы. </p>

Итак, теперь вы понимаете, как работает std :: lower_bound. Обход базового bst позволяет найти первый элемент, равный или превышающий ключ, учитывая дерево, упорядоченное в соответствии с компаратором.

Надеюсь, теперь все предельно ясно:)

...