You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

使用正向与反向迭代器的两段算法是否必然等价?

问题:两段std::set迭代器操作代码是否等价?

首先给出代码定义:

struct pt{int x,y;};
auto cmpSet = [](pt a, pt b) { return a.x<b.x;};
std::set<pt, decltype(cmpSet)> s(cmpSet);

请问以下两段代码是否必然等价?

第一段代码(正向迭代器实现)

if(upper==s.begin()) continue;
auto it= std::prev(upper);
while(it!=s.end() && (*it).y<=p.y){
    auto prv = it == s.begin() ? s.end() : std::prev(it);
    s.erase(it);
    it=prv;
}

第二段代码(反向迭代器实现)

if(upper==s.begin()) continue;
auto it = std::make_reverse_iterator(upper);
while (it != s.rend() && (*it).y <= p.y) {
    auto victim = std::prev(it.base());
    it = std::next(it);
    s.erase(victim);
}

我实际测试发现二者不等价:将两段代码分别提交至算法评测系统时,使用正向迭代器的代码被判定为通过,而使用反向迭代器的代码出现运行时错误。

背景说明

这段代码用于从n个唯一3D点中筛选出不存在其他“X更大、Y更大且Z更小”的点,时间复杂度要求O(n log n)。实现方式是按Z方向排序,并用std::set维护XY平面的当前边界,逻辑类似最小栈结构。

我无法访问测试数据集或调试栈跟踪,评测系统为OmegaUp,该题目来自已结束的Coder Bloom 5月31日私有编程竞赛。

内容的提问来源于stack exchange,提问作者chubakueno

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.13 00:22:48