c++ - 为什么我们必须重载 '<' 运算符才能使用 is_permutation 并包含算法

Question

我有一个包含点 vector 的 vector 是一个具有 x 和 y 坐标的类。我基本上必须从我的 vector 中删除所有排列和子集。为此，我使用了算法 includes 和 is_permutation

我已经重载了“==”运算符，这也是我们需要它的原因。但是除非我重载“<”运算符，否则这两个算法不起作用。

这是我的点类:

class Point{

private:    
    int x;
    int y;
public:
    Point(){
        x=0;
        y=0;
    }
    Point(int xx, int yy){
        x=xx;
        y=yy;
    }

    double getSlope(Point p){
        if(this->x!=p.x && this->y!=p.y){
            return (double)(double(this->y-p.y)/double(this->x-p.x));
        }else if(this->x==p.x){
            return INT_MAX;
        }else{
            return INT_MIN;
        }
    }   
    void print(){
        cout<<"(" <<x<<","<<y<<")";
    }
    bool operator == (Point &p){
    if(this->x==p.x && this->y==p.y )
        return true;
    else
        return false;
    }
    bool operator < (Point &p){
        cout<<"\nin the < operator\n";
    if(this->x < p.x && this->y < p.y )
        return true;
    else
        return false;
    }
};

这是接受点的临时 vector 的函数 并将其与 vector> 进行比较以删除排列。 这些点是从文件中获得的，所以当我们得到点时，我们只将它添加到 vector> 如果它们通过检查

bool check(PointVector temp, vector<PointVector> pointArrays ){

    for(int i =0 ; i < pointArrays.size(); i++){
        if(is_permutation(pointArrays[i].begin(),pointArrays[i].end(),temp.begin())){
            return false;
        }else if(includes(pointArrays[i].begin(),pointArrays[i].end(),temp.begin(),temp.end())){
            return false;
        }else if(includes(temp.begin(),temp.end(),pointArrays[i].begin(),pointArrays[i].end())){
            pointArrays[i].swap(temp);
            return false;
        }

    }
    return true;
}

Point Vector 是 vector<points>; 的类型定义

Answer 1

这是关于 std::includes ，这对要排序的输入序列提出了要求(根据比较器 - operator< )。

在此前提下，算法可以用operator==实现(具有 not < 和 not > 的语义)和相同的线性渐近复杂度。¹ 对于长度为 n 的第一个范围和长度为 m 的第二个范围，我们迭代第一个范围，每次将元素与第二个范围的当前元素进行比较。在匹配时，我们像往常一样将迭代器递增到两个范围。所以，这是 O(n+m) = O(n)，因为 n < m => false .问题是如果 n > m 并且结果应该是 false ，我们必须迭代整个第一个范围以查看(我们无法在检查第一个范围的 n - m + 1 个元素与第二个范围的第一个元素之前做出决定)。 n - m 越大，越差。

但是用operator< ，如果我们应该返回 false，我们可以更快地决定(更确切地说永远不会晚)从算法中，因为我们从第二个序列中读取了一个元素，该元素位于第一个序列中的下一个元素之前。

---

示例:

{1} 是 {2, ..., 10⁶} 的子范围吗？

operator== : 10⁶ - 1 次比较 operator< : 1 比较

即使是 operator<然而，版本在这个示例中仍然受到影响:

{10⁶} 是 {1, ..., 10⁶ - 1} 的子范围吗？

operator== : 10⁶ - 1 次比较 operator< : 10⁶ - 1 次比较

然后由程序员选择预期的迭代方向以产生更短的决策时间。

总的来说，处理有序序列的算法在顺序比较方面起作用，因为它们提供了对输入序列的更多洞察。

---

<子> 1. 如果没有任何一个范围的排序要求(以及随机访问迭代器)，复杂性会更高(取决于附加结构/预排序的使用)。