使用正向与反向迭代器的两段算法是否必然等价?
问题:两段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
相关产品推荐
相关产品推荐

