set.lower_bound 成对函数

Question

我了解到 set.lower_bound(key) 函数 returns 集合中的值尽可能接近键，我想知道当传递的键是一对时它是如何工作的（比如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;
}

Answer 1

I learned that set.lower_bound(key) function returns the value from the set as close as possible to the key

首先，这是错误的。最好参考 cppreference 以获取正确信息。以下是关于 std::set::lower_bound 的评论：

Returns an iterator pointing to the first element that is not less than (i.e. greater or equal to) key.

因此它不是元素尽可能接近而是第一个元素大于或等于。

i was wondering how it works when the key passed is a pair(say x,y coordinates of a point), i.e the set contains pairs.

因为它适用于任何其他类型 T。它在内部实现为 bst（通常作为红黑树）。因此查找是 O(nlogn)。你说的order/comparator用的是什么？ std::set 基本上是：

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

如您所见，它接受一个比较器作为模板参数，默认设置为 std::less。因此

checks whether the first argument is less than the second

你问它如何比较两对？这是 std::pair 上的文档必须说的内容：

Compares lhs and rhs lexicographically by operator<, that is, compares the first elements and only if they are equivalent, compares the second elements.

现在您了解了 std::lower_bound 的工作原理。给定根据比较器排序的树，它遍历底层 bst 以找到等于或大于键的第一个元素。

我希望事情现在 crystal 清楚了:)

set.lower_bound 成对函数

set.lower_bound function with pairs

algorithm

data-structures

set

std-pair

lower-bound