具有相等元素的 std::sort 给出分段错误

2022-01-12 00:00:00 sorting segmentation-fault c++

我有一个存储指针的容器.我试图根据指针指向的相应对象中的数据成员以非递增顺序对这些指针进行排序.就我而言，许??多对象可能对该数据成员具有相同的值.

I have a container storing pointers. I am trying to sort these pointers in non-increasing order based on a data member in the corresponding objects pointed by the pointers. In my case, it is possible that many objects have the same value for that data member.

以下是说明问题的简短代码.对排序函数的调用给出了分段错误.奇怪的是，如果容器中有 16 个元素指向具有相同双精度值的对象，则排序似乎有效.但是，如果我有 17 个元素指向具有相同值的对象，则会出现段错误.

The following is a short code to illustrate the problem. The call to the sort function is giving a Segmentation fault. The weird thing about this is, if I have 16 elements in the container pointing to objects with same value for the double, the sort seems to work. But if I have 17 elements pointing to objects with same value, it gives a seg fault.

谁能解释一下为什么会这样?

Can anyone please explain why this happens? 

#include <iostream>
#include <algorithm>
#include <deque>

//some class
class A {
public:
    double a;
    A(double aval);
};

A::A(double aval) : a(aval) {}

//compare class
struct cmp_A : std::greater_equal<A*> {
    bool operator() (const A* x, const A* y) const;
} cmp_A_obj;

//greater_equal comparison
bool cmp_A::operator() (const A* x, const A* y) const {
    return (x->a >= y->a);
}

int main() {
    std::deque<A*> Adeque;
    //insert 17 A pointers into the container
    for(int i = 1; i<=17; i++) {
        Adeque.push_back(new A(5));
    }

    //This call to sort gives a Segmentation fault
    std::sort(Adeque.begin(), Adeque.end(), cmp_A_obj);

    for(std::deque<A*>::iterator i = Adeque.begin(); i!= Adeque.end(); i++) {
        std::cout << "|" << (*i)->a;
    }
    std::cout << std::endl;
}

推荐答案

你的比较必须实现 严格弱排序.小于或等于不满足这一点.它应该等同于在运算符 < 和 > 中实现的小于"或大于"，例如整数.

Your comparison must implement a strict weak ordering. Less than or equal does not satisfy this. It should be equivalent to "less than" or "greater than" as implemented in operators < and > for, say, integers.

元素的相等性通过应用此排序两次来确定:

Equality of elements is determined by applying this ordering twice:

(!cmp(a,b)) && (!cmp(b,a)); // if this is false, a == b

相关文章