c++ - std::stable_sort 根本不稳定？

Question

我在使用 std::stable_sort 时遇到了一个奇怪的错误在 Point 上数据类型。默认排序 Point值首先由 x 坐标确定，然后由 y 坐标确定以打破平局。但是，我正在使用 std::stable_sort根据点相对于外部点的斜率对点进行排序。我一直发现 std::stable_sort不保留相对于外部点具有相同斜率的点的相对顺序。

这是正确执行并产生预期输出的代码。

std::vector<Point> points;
/* 
Work is done here to fill the vector with Points.
These Points form several horizontal lines. 
*/
std::sort(points.begin(), points.end()); //Sorts Points based on their coordinates
for (const Point& elem : points)  //Displays sorted vector
    std::cout << elem << ' ';

Output:
(1888, 7657) (2682, 14118) (4750, 4652) (5067, 14118) (5766, 4652) (7453, 14118) 
(7599, 7657) (7821, 14118) (8934, 7996) (9972, 4652) (10375, 12711) (10411, 7996) 
(12772, 7657) (13291, 7996) (13832, 7657) (14226, 12711) (16307, 4652) (18177, 12711) 
(20385, 12711) (20547, 7996) 
//The Points are sorted in order of increasing x-coordinate

但是当我使用 std::stable_sort为了根据所有元素相对于第一个元素的斜率对 vector 进行排序，即使在具有相同斜率的点之间， vector 也不再按 x 坐标递增的顺序排序。

const Point& P0 = points[0];
auto compLambda = [&](const Point& a, const Point& b)
    {return P0.slopeCompare(a,b) != 1;}
std::stable_sort(points.begin() + 1, points.end(), compLambda);
for (const Point& elem : points)
    std::cout << elem << ' ';

Output:
(1888, 7657) //First point remains unmoved, as expected
(4750, 4652) (5766, 4652) (9972, 4652) (16307, 4652)

/*These points all form a horizontal line with the first point.*/
(13832, 7657) (12772, 7657) (7599, 7657) 
/*However, they appear to be sorted in order of DECREASING x-coordinates!??!?*/

(20547, 7996) (13291, 7996) (10411, 7996) (8934, 7996) (20385, 12711) (18177, 12711) 
(14226, 12711) (10375, 12711) (7821, 14118) (7453, 14118) (5067, 14118) (2682, 14118)

一般来说，std::stable_sort似乎始终如一地神奇地颠倒了比较具有相同斜率的元素的相对顺序。除此之外，上面提到的方法似乎工作正常。我已经在下面发布了 Point 类的方法(operator<< 除外)，但我看不出其中任何一个错误应该如何导致 std::stable_sort变得不稳定。

这是 Point 类的压缩版本。

#include <limits>

class Point{
private:
    int x, y;
public:
    ///Default constructor for Point[] arrays
    Point(void) = default;   

    ///Regular constructor
    Point(int x, int y): x(x), y(y) {}

    ///Default comparison operators
    inline bool operator<(const Point& other){
        return x < other.x || x == other.x && y < other.y;
    }
    inline bool operator>(const Point& other){
        return x > other.x || x == other.x && y > other.y;
    }
    inline bool operator==(const Point& other){
        return x == other.x && y == other.y;
    }

    ///Returns the slope between this point and another. Note that vertical   
    ///lines have a slope of INF and the method returns -INF if the argument 
    ///is the same as the instance. Also, horizontal lines are treated 
    ///specially to prevent evaluation of -0.0
    inline double slopeTo(const Point& other){
        if (x == other.x)
            return y == other.y ? -HUGE_VAL : HUGE_VAL;
        else if (y == other.y)
            return 0;
        else
            return static_cast<double>(y - other.y)/(x - other.x);
    }

    ///Slope comparator
    inline int slopeCompare(const Point& a, const Point& b){
        if (slopeTo(a) > slopeTo(b))
            return 1;
        else if (slopeTo(a) < slopeTo(b))
            return -1;
        else
            return 0;
    }
};

Answer 1

由于 double 的舍入，slopeTo 本质上是不稳定的。所以 slopeCompare 是不稳定的，所以使用它排序充其量是不稳定的，并且可能比不稳定更糟糕。

通过交叉乘法而不是除法来比较斜率可以获得更好的结果。但是对于仍然不完美的大值。

编辑:乍一看我错过了更严重的错误:

auto compLambda = [&](const Point& a, const Point& b)
    {return P0.slopeCompare(a,b) != 1;}

当 a==b 需要返回 false 时返回 true。