分享
三行代码  ›  专栏  ›  技术社区  ›  Nimra

为什么要重载“<”运算符才能使用IS置换算法? - why do we have to overload the '<' operator to use is_permutation algorithm

  •  -1
  • Nimra  · 技术社区  · 3 月前

    我有一个向量,它包含一个点的向量,它是一个有x和y坐标的类。基本上,我必须从向量中删除所有置换和子集。为了做到这一点,我使用的算法包括和是置换

    我已经重载了“==”运算符,这就解释了为什么我们需要它。但这两种算法不起作用,除非我重载“<”运算符。

    这是我的课程:

    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>进行比较以删除排列。 这些点是从文件中获取的,因此,当我们获得点时,我们只会将其添加到向量中,如果它们通过检查

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

    点向量是的typedef vector<points>;

    1 回复  |  直到 3 月前
        1
  •  5
  •   LogicStuff    3 月前

    这是关于 std::includes 对要排序的输入序列施加要求(根据比较器- operator< )

    在此前提下,该算法可以用 operator== (用not的语义( < > ))同样,线性渐近复杂性。如果没有排序的要求(并且第一个范围有随机访问迭代器),它将是O(n log m)。

    但与 运算符; 如果我们能回来的话,能早点决定吗? false 从算法中,因为我们已经从第二个序列中读取了一个元素,该元素位于第一个序列中的下一个序列之前。

    简而言之,处理有序序列的算法使用有序比较器。