c++ - 关于 std::lower_bound 和 std::upper_bound 的问题
问题描述
我正在努力优化对具有“几乎”排序数据的数据结构的查找。我相当有信心它的“几乎”细节实际上并不重要,但不确定
实际的数据结构比 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 时,“Seek Bid”,我想找到一个 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 Bids 和两个 70 Asks。在实际程序中找到第一个 81 Bid 和最后一个 70 Ask 是很重要的:
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
考虑我只搜索正值之前保证正确的结果 ?换句话说,考虑到我的搜索要求,负面行为是否会导致任何类型的未定义行为?std::lower_bound
关于 en.cppreference.com 和 cplusplus.com 的工作原理的描述非常令人困惑,我通过反复试验才意识到在我的 lambdas中使用<
而不是“正确”。如果我正在寻找我正在寻找的第一个/最后一个级别,<=
为什么使用它不“正确” ?<=
<=
解决方案
几乎所有(有序的)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
推荐阅读
- oauth-2.0 - 无法运行 mix google_apis.auth 任务
- wordpress - Wordpress - Travelify - 标题在博文中出现 3 次
- python - BigQuery,Python 批量插入 bigquery 以进行流式传输服务(“告诉”错误)
- javascript - 根据单独的序列数组通过内联键引用数据对象的最佳方法?
- vim - 如何在 Vim 中生成唯一的文件名并打开它?
- html - HTML Portfolio Template,使用React分离成组件,滚动不起作用,只跳转到部分页面
- c - 使用 if 语句检测用户是否输入了特定的字符或数字
- python - 如何处理延迟加载?
- javascript - 使用javascript将多个数组迭代到对象中
- networking - 如何在 CentOS7 KVM 主机/RHEL7 来宾中配置网络以进行 VLAN 连接