C++ 下界 == 上界

lower_bound == upper_bound

提问by user877329

What does lower_bound mean. If I had to guess I would answer that this function returns the iterator at the last element that is less than the value asked for. But I see that lower_bound is almost the same as upper_bound. The only difference is strict inequality in the case of upper_bound. Is there a true lower bound selection function in stl that agrees with the normal definition of lower bound.

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

EDIT: It was too many negations in the docs which made me confused. The problem was that I got the same iterator. I solved it by subtracting 1 from lower_bound return value. I use it for interpolation:

编辑：文档中有太多的否定让我感到困惑。问题是我得到了相同的迭代器。我通过从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;
        }

I am sorry for this confusion :-(

我很抱歉这种混乱:-(

回答by Kerrek SB

• Lower bound: first element that is greater-or-equal.

• Upper bound: first element that is strictly greater.

• 下限：第一个大于或等于的元素。

• 上限：第一个严格大于的元素。

Example:

例子：

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

As you can see, the half-open equal-range for nis [lb(n), ub(n)).

正如你所看到的，半开相等范围ñ为[磅（ñ），UB（ñ））。

Note that both bounds give you meaningful insertion locations for an element of the desired value so that the ordering is maintained, but lower_boundhas the distinguishing feature that ifthe element already exists, then you get an iterator which actually points to that element. Thus you can use lower_boundon an ordered range to implement your own unique-membership ormultiple-membership container.

请注意，这两个边界都为具有所需值的元素提供了有意义的插入位置，以便保持排序，但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);
}

回答by Steve Jessop

It returns the iterator one past the last element that is less than the value asked for. This is useful as an insertion position (and that's why the function returns that iterator). It's also useful that the half-open range first, lower_bound(first, last, value)specifies all values less than value.

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

upper_boundreturns the iterator one past the last element [less than or equal to / not greater than] the value asked for. Or strictly: the last element which the value is not less than, since both algorithms deal exclusively in less-than comparators.

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

If you want the iterator before the iterator returned by lower_bound, you can subtract 1 (for a random access iterator), decrement (for a bidirectional iterator), or do a linear search instead of using lower_bound(for a forward iterator that is none of those).

如果您希望在 返回的迭代器之前使用迭代器lower_bound，则可以减去 1（对于随机访问迭代器）、递减（对于双向迭代器）或进行线性搜索而不是使用lower_bound（对于没有这些的前向迭代器） .

Beware the edge case that there is no element less than the value asked for, in which case you can't have what you want, because it doesn't exist. lower_boundof course returns the beginning of the range in that case, so doesn't need a special-case return value.

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

回答by David Hammen

Since this has been reopened, I'll try to make my comment an answer.

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

The name lower_boundis mathematically incorrect. A better name might be least_upper_bound, but that would probably confuse most non-mathematically minded folk. (And then what do you call upper_bound? almost_least_upper_bound? Yech!)

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

My advice: Get over the fact that the names lower_boundand upper_boundare technically incorrect. The two functions as defined are quite useful. Think of those functions as a useful abuse of notation.

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

To make a mathematically correct lower_boundfunction that conforms with the C++ concept of an iterator, the function would have to return a reverse iterator rather than a forward iterator. Returning a reverse iterator is not nearly as useful as the approach taken by the perhaps misnamed lower_boundand upper_bound, and the concept of returning a reverse iterator runs afoul of the fact that not all containers are reversible.

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

Why a reverse iterator? Just as there is no guarantee that an upper bound exists in the container, there similarly is no guarantee that a lower bound will exist. The existing lower_boundand upper_boundreturn end()to indicate that the searched-for value is off-scale high. A true lower bound would need to return rend()to indicate that the searched-for value is off-scale low.

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

There is a way to implement a true lower bound in the form of a forward iterator, but it comes at the price of abusing the meaning of end()to mean "there is no lower bound". The problem with this abuse of notation is that some user of the function might do something equivalent to true_lower_bound(off_scale_low_search_value)-1and voila! one has a pointer to the largest element in the set.

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

That said, here's how to do it. Have the true lower bound function return end()if the container is empty or if the searched-for value is smaller than the first value in the container. Otherwise return upper_bound()-1.

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

回答by Jens Kilian

lower_bound, upper_boundand equal_rangeare functions which perform binary search in a sorted sequence. The need for three functions comes from the fact that elements may be repeated in the sequence:

lower_bound,upper_bound和equal_range是按排序顺序执行二分查找的函数。三个函数的需要来自于元素可能在序列中重复的事实：

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

In this case, when searching for the value 4, lower_boundwill return an iterator pointing to the first of the three elements with value 4, upper_boundwill return an iterator pointing to the element with value 5, and equal_rangewill return a pair containing these two iterators.

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

回答by v.oddou

Following David Hammen's answer, I attempted to explain why we often don't feel the names of lower_bound/upper_boundto be correct, or at least intuitive.

按照 David Hammen 的回答，我试图解释为什么我们经常觉得lower_bound/的名称upper_bound不正确，或者至少不直观。

It's because we are looking for an element immediately lower than the query. I made a drawing and a use case:

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

Code:

代码：

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

https://ideone.com/jM8pt3

Basically to get the behavior of the "grey arrows", we need upper_bound - 1which is why it's weird.

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

Let me rephrase that slightly:from the name lower_boundwe instinctively expect returns-first-immediately-inferior-element(like the grey arrows). But we get returns-first-immediately-superior-elementfor lower_bound; and first-immediately-strictly-superior-elementfor upper_bound. That's what is surprising.

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

It's surprising in the hypothesis that you work with a sparse sequencelike my thought experiment in the picture above. But it makes wonderful sense when you think of it in terms of ?bounds of an equal_range? in a dense sequence, populated with plateaus, like Kerrek SB beautifully pictured.

假设您使用稀疏序列，就像我上图中的思想实验一样，这令人惊讶。但是当你从 ?bounds of an 的角度考虑它时，它是非常有意义的equal_range。在一个密集的序列中，充满了高原，就像 Kerrek SB 美丽的图画。

Test code:

测试代码：

#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";
}

results in

结果是

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

seems ok.

看起来还可以。

So of course the utility functions are not very good, they should be designed with a range API, so we can work with any collection or sub-range, or reverse iterators, or filtered views and whatnot. We can get that when we have C++20. In the meantime, I just made a simple educative map-taking API.

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

play with it:
https://ideone.com/jM8pt3

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

回答by Bruce Ricker

Auch!

哎哟！

Did you change the original code or is the copy-paste error in there since day one?

您是更改了原始代码还是从第一天起就出现了复制粘贴错误？

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

In the code I read today you are assigning lower_bound to both 'l' and 'u'.

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

回答by Andrey

Another usage of lower_boundand upper_boundis to find a range of equal elements in a container, e.g.

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