std::lower_bound和std::upper_bound的问题

Question

我正在优化一个查找几乎已排序数据的数据结构的工作。我相当有信心，“几乎”这个细节实际上并不重要，但我还不确定。

实际的数据结构比SO所需的更复杂，因此我对其进行了简化。简化版本是std::vector<Level>，其中包含价格、出价和要价：

• 价格严格递增
• 出价通常按升序排列
• 要价通常按降序排列

当我说“通常”时，我的意思是数据具有一长串通常为零的值，后面跟着有意义的值，但其中一些零可能实际上是负一。然而，我只会搜索正值，因此所有零和负一都不是有意义的返回值。

以下是我简化程序中用于SO的测试数据：

//                        Price  Bid  Ask    Index
levels.emplace_back(Level( 42.0,   0, 150)); //  0
levels.emplace_back(Level( 43.0,   0,  71)); //  1
levels.emplace_back(Level( 44.0,   0,  70)); //  2
levels.emplace_back(Level( 45.0,   0,  70)); //  3
levels.emplace_back(Level( 46.0,   0,  69)); //  4
levels.emplace_back(Level( 47.0,   0,   0)); //  5
levels.emplace_back(Level( 48.0,  -1,  -1)); //  6
levels.emplace_back(Level( 49.0,   0,   0)); //  7
levels.emplace_back(Level( 50.0,  80,   0)); //  8
levels.emplace_back(Level( 51.0,  81,   0)); //  9
levels.emplace_back(Level( 52.0,  81,   0)); // 10
levels.emplace_back(Level( 53.0,  82,   0)); // 11
levels.emplace_back(Level( 54.0, 201,   0)); // 12

当我在这个结构中搜索一些Bid，“寻找Bid”时，我希望找到第一个价格级别的价格，其Bid大于或等于“寻找Bid”。 当我在这个结构中搜索一些Ask，“寻找Ask”时，我希望找到最后一个价格级别的价格，其Ask大于或等于“寻找Ask”。 以下是我简化的SO程序：

#include <algorithm>
#include <iostream>
#include <vector>

struct Level final {
    Level() = delete;
    Level(const double a_price, const int a_bid, const int a_ask) :
        m_price(a_price),
        m_bid  (a_bid),
        m_ask  (a_ask)
    {}

    const double m_price;
    const int    m_bid;
    const int    m_ask;
};

int main(int argc, char** argv) {
    if (argc != 3) {
        std::cout << "Usage: " << argv[0] << " <Seek Bid> <Seek Ask>\n";
        exit(1);
    }

    std::vector<Level> levels;

    //                        Price  Bid  Ask    Index
    levels.emplace_back(Level( 42.0,   0, 150)); //  0
    levels.emplace_back(Level( 43.0,   0,  71)); //  1
    levels.emplace_back(Level( 44.0,   0,  70)); //  2
    levels.emplace_back(Level( 45.0,   0,  70)); //  3
    levels.emplace_back(Level( 46.0,   0,  69)); //  4
    levels.emplace_back(Level( 47.0,   0,   0)); //  5
    levels.emplace_back(Level( 48.0,  -1,  -1)); //  6
    levels.emplace_back(Level( 49.0,   0,   0)); //  7
    levels.emplace_back(Level( 50.0,  80,   0)); //  8
    levels.emplace_back(Level( 51.0,  81,   0)); //  9
    levels.emplace_back(Level( 52.0,  81,   0)); // 10
    levels.emplace_back(Level( 53.0,  82,   0)); // 11
    levels.emplace_back(Level( 54.0, 201,   0)); // 12

    const int seekBid = atoi(argv[1]);
    const int seekAsk = atoi(argv[2]);
    std::cout << "Seek Bid: " << seekBid << ", Seek Ask: " << seekAsk << '\n';

    if (seekBid <= 0 || seekAsk <= 0) {
        std::cout << "Seek Bid or Seek Ask is not positive\n";
        exit(1);
    }

    // If the last Level's Bid is < Seek Bid then what I am looking for doesn't exist
    if (levels.back().m_bid < seekBid)
        std::cout << "Cannot satisfy Seek Bid\n";
    else {
        // Find the first Level with a Bid <= Seek Bid
        // Not sure why I need to specify < instead of <= but appears to work
        const auto it = std::lower_bound(
            levels.begin(),
            levels.end(),
            seekBid,
            [](const Level& a_level, const int a_bid) { return a_level.m_bid < a_bid; }
        );
        std::cout << "Bid Price: " << it->m_price << ", Bid Index: " << &*it - &levels[0] << '\n';
    }

    // If the first Level's Ask is < Seek Ask then what I am looking for doesn't exist
    if (levels.front().m_ask < seekAsk)
        std::cout << "Cannot satisfy Seek Ask\n";
    else {
        // Find the last Level with Ask <= Seek Ask
        // Need to use std::prev due to how std::upper_bound works
        // Not sure why I need to specify < instead of <= but appears to work
        const auto it = std::prev(std::upper_bound(
            levels.begin(),
            levels.end(),
            seekAsk,
            [](const int a_ask, const Level& a_level) { return a_level.m_ask < a_ask; }
        ));
        std::cout << "Ask Price: " << it->m_price << ", Ask Index: " << &*it - &levels[0] << '\n';
    }

    return 0;
}

以下是运行我的SO测试程序的一些示例。当“寻找买入价”为81且“寻找卖出价”为70时，这种情况非常重要，因为有两个81买入价和两个70卖出价。在实际程序中，找到第一个81买入价和最后一个70卖出价非常重要。

Seek Bid: 79, Seek Ask: 68
Bid Price: 50, Bid Index: 8
Ask Price: 46, Ask Index: 4

Seek Bid: 80, Seek Ask: 69
Bid Price: 50, Bid Index: 8
Ask Price: 46, Ask Index: 4

Seek Bid: 81, Seek Ask: 70
Bid Price: 51, Bid Index: 9
Ask Price: 45, Ask Index: 3

Seek Bid: 82, Seek Ask: 71
Bid Price: 53, Bid Index: 11
Ask Price: 43, Ask Index: 1

所有这些结果都是正确的，但这是我的问题： 1. 在搜索之前，是否有必要将所有负数变成零以确保使用 std::lower_bound 或 std::upper_bound 时得到正确的结果，考虑到我只搜索正值？换句话说，给定我的搜索要求，这些负数会导致任何未定义的行为吗？ 2. en.cppreference.com 和 cplusplus.com 上关于 std::lower_bound 工作原理的描述非常令人困惑，直到我通过试错才意识到在我的 lambda 表达式中使用 < 而不是 <= 是“正确”的。如果我正在寻找第一个/最后一个<=我要查找的等级，为什么使用<=不是正确的？

- asimes

---

原因是大多数算法/数据结构需要一个“严格弱序”（strict weak ordering），详情请参考“维基百科”的相关条目，也可查看“isocpp”网站上的文章。 - skeller

Answer 1

几乎所有（有序）stl容器都依赖于严格弱序。 严格弱序定义了元素相对位置的优先级。 因此，严格弱序具有以下属性： - 对于S中的所有x，不成立x < x（反自反性）。 - 对于S中的所有x，y，如果x < y，则不成立y < x（非对称性）。 - 对于S中的所有x，y，z，如果x < y且y < z，则x < z（传递性）。 - 对于S中的所有x，y，z，如果x与y无法比较（既不成立x < y也不成立y < x），并且y与z无法比较，则x与z无法比较（不可比较性的传递性）。 如果要使这些STL容器和算法按规定工作，则您提供的比较必须提供此严格弱序。 参考资料，更多细节：

https://en.cppreference.com/w/cpp/named_req/Compare

https://github.com/bashrc-real/Codearchive/blob/master/cpp/Strict_weak_ordering_and_stl.md

https://en.wikipedia.org/wiki/Weak_ordering

- skeller

Answer 2

一般要求在 Compare 中有描述。 必须有单一排序，使得等效元素组在该排序中具有特定位置，使用提供的比较。 lower_bound 和 upper_bound 要求输入按此顺序排列。

在搜索之前，有必要将所有负数变成零以保证正确结果吗。

不需要在这种情况下进行操作，因为它只会针对给定正值测试 Level ，而不是相互之间的比较。您的 comp 将0视为与-1等价，因此它们“顺序无关紧要”。在此数据集中搜索 0 或负数将导致未定义的行为。

如果我正在寻找第一个/最后一个小于/等于我正在搜索的级别，为什么不使用<=就不“正确”了？

因为这违反了严格弱序的不对称性要求。如果您只想要较大的值，请使用 upper_bound 。

- Caleth

---

你对我的第一个问题的回答非常有帮助，但是你能否澄清一下我第二个问题的答案？目前我使用std::lower_bound和std::upper_bound分别用于Bid和Ask，且都是使用<而不是<=，并且结果是正确的。 - asimes

Answer 3

std::lower_bound和std::upper_bound执行简单的二分查找。它们不会搜索特定元素值，而是搜索分区点。您应用std::lower_bound的范围不需要排序。要求是：[first, last)范围必须根据表达式element < value或comp(element, value)进行分区，即所有使表达式为true的元素必须在所有使表达式为false的元素之前。

---

不需要。如果value为正数，则始终根据表达式element < value对您的范围进行分区。

因为std::lower_bound依赖于<关系而不是<=关系。粗略地说，它从!(b < a)推导出a <= b。

- Evg

---

请问您能否澄清一下第二个答案？对我来说，!(b < a) 应该意味着 b >= a，所以我还不理解。 - asimes

@asimes，lower_bound的意思是：给我一个范围、一个值和一个a < value的关系，我会返回第一个>= value元素的位置。如果你用<=代替<，它就无法实现其广告所说的功能。这是一份合同。 - Evg