c++ - 按 'enveloping' 或 'dominance' 标准排序坐标

Question

我正在尝试根据 vector 中的坐标是否被其他坐标包围或支配来对它们进行排序。例如，坐标 [1 , 2 , 1 , 1] 被 [4, 2 , 1 , 2] 包围或控制，即使两者的第二个和第三个值坐标相等。

节目亮点。 (完整程序 online at rextester.com )

int input[18][4] = { { 4 , 3 , 3 , 3 } , { 1 , 5 , 4 , 1 } , { 2 , 4 , 5 , 4 } ,
                     { 3 , 1 , 2 , 5 } , { 4 , 2 , 1 , 2 } , { 1 , 3 , 3 , 1 } ,
                     { 2 , 3 , 3 , 3 } , { 3 , 1 , 2 , 3 } , { 5 , 2 , 1 , 2 } ,
                     { 1 , 4 , 4 , 1 } , { 1 , 1 , 2 , 1 } , { 1 , 2 , 1 , 1 } ,
                     { 2 , 1 , 2 , 4 } , { 2 , 2 , 1 , 2 } , { 3 , 1 , 1 , 2 } ,
                     { 2 , 1 , 2 , 3 } , { 1 , 1 , 1 , 1 } , { 2 , 1 , 1 , 2 } };   

struct Coordinate
{
    Coordinate(){}
    Coordinate( int (&val)[4] );
    bool operator<( const Coordinate& otherCoord ) const;
    void print() const;

    int value[4];
};      

void print( const std::vector<Coordinate>& coord );

int main()
{
    std::vector<Coordinate> coord;
    coord.assign( input  , input + 18 );
    print( coord );

    std::sort( coord.begin() , coord.end() );
    print( coord );
}

但是程序输出不是我所期望的，

[ 1 , 1 , 1 , 1 ]
[ 1 , 4 , 4 , 1 ]
[ 2 , 1 , 1 , 2 ]
[ 2 , 1 , 2 , 3 ]
[ 3 , 1 , 1 , 2 ]
[ 1 , 3 , 3 , 1 ]
[ 2 , 2 , 1 , 2 ]
[ 2 , 1 , 2 , 4 ]
[ 1 , 2 , 1 , 1 ]
[ 1 , 1 , 2 , 1 ]
[ 4 , 3 , 3 , 3 ]
[ 5 , 2 , 1 , 2 ]  // <-- ???
[ 3 , 1 , 2 , 3 ]
[ 2 , 3 , 3 , 3 ]
[ 4 , 2 , 1 , 2 ]  // <-- ???
[ 3 , 1 , 2 , 5 ]
[ 2 , 4 , 5 , 4 ]
[ 1 , 5 , 4 , 1 ]

例如 [ 5 , 2 , 1 , 2 ] 包络或支配 [ 4 , 2 , 1 , 2 ] 但出现在它之前，如程序输出所示.

Answer 1

你要的是lexicographical ordering这基本上相当于说比较(x1, y1) < (x2, y2)相当于说if (x1 < x2 || (x1 == x2 && y1 < y2))

你的 body Coordinate::operator<可以修改如下:

for( int i = 0; i < 4; ++i ) {
   if( value[i] > otherCoord.value[i] ) 
     return false; 
   if (value[i] < otherCoord.value[i] ) 
     return true; 
} 
return false;

我们返回false最后，因为我们正在执行严格的小于比较。当我们到达那条线时，我们知道两个坐标的所有元素都是相同的，所以如果我们返回 true 那么我们就满足了 <=相反。

但是，我建议您更新此代码以使用更现代的 C++。即 vector 和数组。这很好，尤其是因为默认 operator<对于 std::array将为您执行字典排序。 (此外，您不必担心指针数学，因为您可以使用迭代器)。

这是你的新类(class):

template<size_t N>
struct Coordinate
{
    Coordinate(){}
    Coordinate( std::array<int, N> _val);
    bool operator<( const Coordinate& otherCoord ) const;
    void print() const;
    
    std::array<int, N> value;
};  

下面是您将如何实现 operator< :

template<size_t N>
bool Coordinate<N>::operator<( const Coordinate<N>& otherCoord ) const
{
    return value < otherCoord.value;
}

最后 main :

int main()
{
    std::vector<Coordinate<4>> coords;
    coords.assign( input.begin(), input.end() );
    print(coords);
    std::sort(coords.begin(), coords.end());
    print( coords );
}

首选 Coordinate 的模板这样您就可以在编译时制作任意维度的坐标。现在有很多 magic numbering继续使一切正常。

Here's a live demo