c++ - std map构造严格的弱顺序并找到下界

Question

我有一些现实生活中的墙，其特点是有两个高度(最左边和最右边的高度)。
例如

I        I     I  I
I     I  I     I  I
I     I  I     I  I    I
I_____I  I_____I  I____I

第一个具有最左边的高度 hl=4 , 最右边的高度 hr=3 ，第二个 hl=4和 hr=4等等。
给定 hl和 hr我现在的任务是找到体积最小的墙以达到 hl和 hr .因此(a)只允许降低墙两侧的高度，但不能增加，(b)损失的体积应该最小。
在第一种方法中，我使用最小高度 hMin=std::min(hl,hr) 将问题减少到一个高度。 .通过这样做，我可以用“墙”填充 map 并使用 hMin作为 key ，作为返回，使用 lower_bound 获得解决方案搜索 max(hl,hr) .
现在考虑到两个高度的最佳解决方案，我在构建严格的弱顺序时遇到了各种麻烦。到目前为止，我所尝试的是将键扩展到第二个高度，使用自定义less并等效地使用lower_bound。
我的习惯 less 看起来有点像:

    struct KeyLess
    {
        bool operator(Key const&x, Key const&y) const
        {
            if ((x.hl + roundOff < y.hl ) && (x.hr+ roundOff < y.hr))
                return true;
            if ((y.hl + roundOff < x.hl ) && (y.hr+ roundOff < x.hr))
                return false;
            return false;
        }
    };

但显然 x.hl> y.hl 有问题和 x.hr < y.hr或视觉上这些类型

I              I  
I              I  I    I
I     I  I     I  I    I
I_____I  I_____I  I____I

并且没有给出严格的弱排序 afaik。
如果您能帮助我为我的问题构建一个 less 运算符或向我展示另一种找到解决此问题的方法的方法，我将不胜感激。

例子

I              I       I  I        I     I
I              I  I    I  I     I  I     I
I              I  I    I  I     I  I     I
I     I        I  I    I  I     I  I     I
I_____I  I_____I  I____I  I_____I  I_____I

给定 hl=3和 hr=5它应该返回第三个( hl=4 和 hr=5 )。
只要我能找到解决方案，墙壁在 map 中保存的顺序本身并不相关(但我认为这也是我在这里找到有意义的排序的问题)。

Answer 1

我想你想要

struct KeyLess
{
    bool operator(Key const&x, Key const&y) const
    {
        return std::pair(std::abs(x.hl - x.hr), std::min(x.hl, x.hr)) 
             < std::pair(std::abs(y.hl - y.hr), std::min(y.hl, y.hr));
    }
};

IE。首先按高度差排序，然后按较小的高度排序。如果还需要区分

      I  I        
      I  I        
I     I  I     I  
I_____I  I_____I  

然后你可以通过任意选择第一个小于第二个来扩展它

struct KeyLess
{
    bool operator(Key const&x, Key const&y) const
    {
        return std::tuple(std::abs(x.hl - x.hr), std::min(x.hl, x.hr), x.hl < x.hr) 
             < std::tuple(std::abs(y.hl - y.hr), std::min(y.hl, y.hr), y.hl < y.hr);
    }
};