c++ - 下限 == 上限

Question

下限是什么意思。如果我不得不猜测，我会回答这个函数在小于请求值的最后一个元素处返回迭代器。但我看到lower_bound 几乎和upper_bound 一样。唯一的区别是在 upper_bound 的情况下严格不等式。stl 中是否存在与下限的正常定义一致的真正下限选择函数。

编辑：文档中有太多的否定让我感到困惑。问题是我得到了相同的迭代器。我通过从 lower_bound 返回值中减去 1 来解决它。我用它来插值：

    float operator()(double f)
        {
        SpectrumPoint* l=std::lower_bound(beginGet(),endGet(),(SpectrumPoint){float(f),0.0f}
            ,SpectrumPoint::CompareFreqLessThan);
        if(l>beginGet())
            {--l;}

        SpectrumPoint* u=std::lower_bound(beginGet(),endGet(),(SpectrumPoint){float(f),0.0f}
            ,SpectrumPoint::CompareFreqLessThan);

        if(u==endGet())
            {u=beginGet();}

        if(l==u)
            {
            if(u==endGet())
                {return u->amp;}
            return l->amp;
            }

        double f_min=l->freq;
        double A_min=l->amp;
        double f_max=u->freq;
        double A_max=u->amp;

        double delta_f=f_max-f_min;
        double delta_A=A_max-A_min;

        return A_min + delta_A*(f-f_min)/delta_f;
        }

我很抱歉这种混乱:-(

score 131 · Accepted Answer

下限：第一个大于或等于的元素。
上限：严格大于的第一个元素。

例子：

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|

如您所见，n 的半开等程是[lb( n ), ub( n ))。

请注意，这两个边界都为您提供了所需值的元素的有意义的插入位置，以便保持顺序，但lower_bound有一个显着特征，即如果该元素已经存在，那么您将获得一个实际指向该元素的迭代器。因此，您可以使用lower_bound有序范围来实现您自己的唯一成员或多成员容器。

void insert(Container & c, T const & t)
{
    auto it = std::lower_bound(c.begin(), c.end(), t);

    // if unique container:
    if (it != c.end() && *it == t) { /* error, element exists! */ return; }

    c.insert(it, t);
}

score 8 · Accepted Answer

它在最后一个小于请求值的元素之后返回迭代器。这作为插入位置很有用（这就是函数返回该迭代器的原因）。半开范围first, lower_bound(first, last, value)指定所有小于的值也很有用value。

upper_bound返回迭代器过去最后一个元素[小于或等于/不大于]所要求的值。或者严格来说：值不小于的最后一个元素，因为这两种算法都专门处理小于比较器。

如果您希望迭代器在由lower_bound. lower_bound.

当心没有元素小于所要求的值的边缘情况，在这种情况下你不能拥有你想要的东西，因为它不存在。lower_bound当然在这种情况下返回范围的开头，因此不需要特殊情况的返回值。

score 8 · Accepted Answer

由于这已重新打开，我将尝试让我的评论成为答案。

这个名字lower_bound在数学上是不正确的。一个更好的名字可能是least_upper_bound，但这可能会使大多数没有数学头脑的人感到困惑。（然后你怎么称呼upper_bound？？almost_least_upper_bound耶！）

lower_bound我的建议：克服名称和upper_bound技术上不正确的事实。定义的两个函数非常有用。将这些功能视为对符号的有用滥用。

lower_bound要生成符合 C++ 迭代器概念的数学上正确的函数，该函数必须返回反向迭代器而不是正向迭代器。返回反向迭代器并不像可能被错误命名的lower_boundand所采用的方法那么有用upper_bound，并且返回反向迭代器的概念与并非所有容器都是可逆的事实相冲突。

为什么是反向迭代器？正如不能保证容器中存在上限一样，同样不能保证会存在下限。存在lower_bound和upper_bound返回end()表明搜索到的值是超出范围的高。需要返回一个真正的下限rend()以指示搜索到的值是超出范围的低值。

有一种方法可以以前向迭代器的形式实现真正的下限，但其代价是滥用end()“没有下限”的含义。这种滥用符号的问题在于，该函数的某些用户可能会做一些等效的事情true_lower_bound(off_scale_low_search_value)-1，瞧！one 有一个指向集合中最大元素的指针。

也就是说，这是如何做到的。end()如果容器为空或搜索的值小于容器中的第一个值，则返回真正的下界函数。否则返回upper_bound()-1。

score 2 · Accepted Answer

lower_bound,upper_bound和equal_range是在排序序列中执行二进制搜索的函数。对三个函数的需求来自于元素可能在序列中重复的事实：

1, 2, 3, 4, 4, 4, 5, 6, 7

在这种情况下，当搜索值 4 时，lower_bound将返回一个指向三个值为 4 的元素中的第upper_bound一个的迭代器，将返回一个指向值为 5 的元素的迭代器，equal_range并将返回一个包含这两个迭代器的对。

score 2 · Accepted Answer

在大卫哈曼的回答之后，我试图解释为什么我们经常觉得lower_bound/的名字upper_bound不正确，或者至少不直观。

这是因为我们正在寻找一个低于查询的元素。我画了一张图和一个用例：

代码：

template< typename T, typename U >
auto infimum(std::map<T,U> const& ctr, T query)
{
    auto it = ctr.upper_bound(query);
    return it == ctr.begin() ? ctr.cend() : --it;
}

template< typename T, typename U >
bool is_in_interval(std::map<T,U> const& ctr, T query)
{
    auto inf = infimum(ctr, query);
    return inf == ctr.end() ? false : query <= inf->second;
}

https://ideone.com/jM8pt3

基本上要获得“灰色箭头”的行为，我们需要upper_bound - 1这就是为什么它很奇怪。

让我稍微改一下：从lower_bound我们本能地期望的名字returns-first-immediately-inferior-element（如灰色箭头）。但是我们得到returns-first-immediately-superior-element了lower_bound；和first-immediately-strictly-superior-element上限。这就是令人惊讶的地方。

令人惊讶的是，假设您使用的是上图中我的思想实验这样的稀疏序列。equal_range但是，当您按照密集序列中的“边界”来考虑它时，它会很有意义，其中充满了高原，就像美丽的 Kerrek SB 描绘的那样。

测试代码：

#include <map>
#include <cassert>
#include <iostream>

// .. paste infimum and is_in_interval here

int main()
{
    using std::cout;
    using Map = std::map<int,int>;
    Map intervals{{2,5}, {8,9}};

    auto red = infimum(intervals, 4);
    assert(red->first == 2);
    cout << "red->first " << red->first << "\n";

    auto green = infimum(intervals, 6);
    assert(green->first == 2);
    cout << "green->first " << green->first << "\n";

    auto pink = infimum(intervals, 8);
    assert(pink->first == 8);
    cout << "pink->first " << pink->first << "\n";

    auto yellow = infimum(intervals, 1);
    assert(yellow == intervals.cend());

    auto larger_than_all = infimum(intervals, 15);
    assert(larger_than_all->first == 8);

    bool red_is = is_in_interval(intervals, 4);
    cout << "red is in " << red_is << "\n";

    bool green_is = is_in_interval(intervals, 6);
    cout << "green is in " << green_is << "\n";

    bool pink_is = is_in_interval(intervals, 8);
    cout << "pink is in " << pink_is << "\n";

    bool yellow_is = is_in_interval(intervals, 1);
    cout << "yellow is in " << yellow_is << "\n";
}

结果是

red->first 2
green->first 2
pink->first 8
red is in 1
green is in 0
pink is in 1
yellow is in 0

似乎还可以。

所以当然实用函数不是很好，它们应该设计一个范围 API，所以我们可以使用任何集合或子范围，或者反向迭代器，或者过滤视图等等。当我们拥有 C++20 时，我们可以做到这一点。与此同时，我刚刚制作了一个简单的教育性地图绘制 API。

玩它：
https ://ideone.com/jM8pt3

score 1 · Accepted Answer

lower_boundand的另一种用法upper_bound是在容器中查找一系列相等的元素，例如

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);
auto upper = std::upper_bound(lower, data.end(), 4);

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

score 1 · Accepted Answer

哎呀！

您是否更改了原始代码或者从第一天开始就出现复制粘贴错误？

float operator()(double f)
{
    SpectrumPoint* l=std::lower_bound//...
...
    SpectrumPoint* u=std::lower_bound//...
...
}

在我今天阅读的代码中，您将 lower_bound 分配给“l”和“u”。

c++ - 下限 == 上限

7 回答 7

Related

Reference