代码之家 › 专栏 › 技术社区 › asimes

关于std::下限和std::上限的问题

c++

asimes · 技术社区 · 7 年前

我正在做的工作是优化对“几乎”排序数据的数据结构的查找。我相当有信心,它的“几乎”细节其实并不重要,但不确定

实际的数据结构比需要的更复杂,所以我简化了它。简化版是 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

当我在这个结构中搜索某个出价“Seek Bid”时,我想找到第一层的出价大于或等于“Seek Bid”

当我在这个结构中搜索一些Ask,“Seek-Ask”时,我想找到最后一个级别的价格,这个级别的Ask大于或等于“Seek-Ask”

下面是我的简化程序:

#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运行测试程序的一些示例。“Seek Bid”是81,“Seek Ask”是70的情况非常重要,因为有两个81 Bid和两个70 Ask。在实际程序中,重要的是找到前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

所有这些结果都是正确的,但这些是我的问题:

我有必要把所有的负数都归零吗在使用前搜索以保证正确的结果 std::lower_bound 或 std::upper_bound 考虑到我只是寻找积极的价值观?换句话说,做消极的因为我的搜索要求有任何未定义的行为吗?
关于如何 标准:下限 工作于 en.cppreference.com和cpluplus.com非常混乱,我只意识到使用 < 而不是 <= 在我的羔羊身上是“正确的” 通过反复试验。为什么不“正确”使用 <= 如果我是寻找第一层/最后一层 <= 我在寻找什么为了什么?

3 回复 | 直到 7 年前

Evg 7 年前

std::lower_bound 和 std::upper_bound 执行简单的二进制搜索。它们不搜索特定的元素值,而是搜索分区点。你申请的范围 标准:下限 不需要对to进行排序。这个 requirement 是:

范围 [first, last) 必须对表达式进行分区 element < value 或 comp(element, value) ,即表达式所针对的所有元素 true 必须位于表达式所针对的所有元素之前 false .

我有必要在搜索之前把所有的负数都归零吗。。。

不,你的范围总是按照表达式划分的 元素<值 如果 value 是积极的。

为什么不“正确”使用 <= 如果我在找第一层/最后一层 <= 我在找什么?

因为 标准:下限 依靠 < 关系,不在 <= . 粗略地说,它得出 a <= b 从 !(b < a) .

Caleth 7 年前

一般要求在 Compare . 必须有一个单一的顺序,以便使用提供的比较,等价元素组在该顺序中有一个特定的位置。 lower_bound 和 upper_bound 要求输入的顺序是这样的。

为了保证搜索结果的正确性,我有必要在搜索之前把所有的负数都归零吗。

在这种情况下不会,因为它只会测试 Level 与给定的正值相对,而不是彼此相对。你的 comp 对待 0 相当于 -1 ,所以它们“出故障”并不重要。这将是一种未定义的行为 0个 或此数据集中的负数。

为什么不“正确”使用 <= 如果我在找第一层/最后一层 <= 我在找什么?

因为这打破了严格弱序的不对称性要求。如果只需要较大的值,请使用 上限 .

skeller 7 年前

几乎所有(有序的)stl容器都依赖于严格的弱顺序。严格的弱排序根据一个项相对于另一个项的优先级定义元素的相对位置。

因此,严格弱序具有以下性质:

对于S中的所有x,x和lt;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://github.com/bashrc-real/Codearchive/blob/master/cpp/Strict_weak_ordering_and_stl.md

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