std map constructing strict weak order and finding lower bound

user_11101828 0
Viewed 112

I have some kind of real life walls which are characterized by two heights (leftmost and rightmost height).

e.g.

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

the first one has leftmost height hl=4, rightmost height hr=3, the second hl=4 and hr=4 and so on.

Given hl and hr my task is now to find the wall loosing minimal volume in order to reach hl and hr. So (a) only lowering the heights on either side of the wall is allowed but not increasing and (b) the lost volume should be minimal.

In a first approach I've reduced the problem to one height using the minimal height hMin=std::min(hl,hr). By doing so I can fill a map with the "walls" and use hMin as keys and in return get the solution using lower_bound searching with max(hl,hr).

Now considering the two heights optimal solution I'm getting into all sorts of trouble constructing a strict weak order. What I have tried until now is to extend the key for a 2nd height, use a custom less and use equivivalently lower_bound. My custom less looks somewhat like:

    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;
        }
    };

but obviously has problems for x.hl> y.hl and x.hr < y.hr or visually for these types

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

and does not give a strict weak ordering afaik.

I would appreciate any help constructing a less operator for my problem or showing me another way of finding a solution to this problem.

Example

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

Given hl=3 and hr=5 it should return the 3rd (hl=4 and hr=5). The order the walls are saved in the map is not per se relevant as long as I can get to the solution (But I think that is also my problem to find a meaningful ordering here).

stdmap c++
2 Answers

I think you want

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));
    }
};

I.e. ordering first by the difference in heights, then by the smaller height. If you still need to distinguish

      I  I        
      I  I        
I     I  I     I  
I_____I  I_____I

Then you can extend that by arbitrarily choosing the first as less than the second

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);
    }
};
user_26108100

You have a map (or set) which requires strict weak ordering, but you don't care about the order.

You can simply use unordered_map (or unordered_set) and not have to worry about it.

Or you can create a strict weak ordering. Fortunately this is already available in the standard library using std::tie from #include <tuple>

bool Key::operator<(const Key &rhs) const {
    return std::tie(hl, hr) < std::tie(rhs.hl, rhs.hr);
}

But of course, if the order actually DOES matter, but has its own meaning and can be arbitrarily changed, then you should use std::vector. Let the algorithm put things where they need to be.

user_17665440
Related