c++ - 为什么我们必须重载“<”运算符才能使用 is_permutation 并包含算法
问题描述
我有一个包含点向量的向量是一个具有 x 和 ay 坐标的类。我基本上必须从我的向量中删除所有排列和子集。为此,我使用了算法包括和 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> 中
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 是一个 typedefvector<points>;
解决方案
这大约是std::includes
,它对要排序的输入序列提出了要求(根据比较器 - operator<
)。
在这个前提条件下,算法可以用(用 not和 notoperator==
的语义)和相同的线性渐近复杂度来实现。1对于长度为 n 的第一个范围和长度为 m 的第二个范围,我们迭代第一个范围,每次将元素与第二个范围的当前元素进行比较。在匹配时,我们像往常一样将迭代器增加到两个范围。所以,这是 O(n+m) = O(n),因为 n < m => 。问题是如果 n > m 并且结果应该是,我们必须迭代整个第一个范围来查看(在检查第一个范围的 n - m + 1 个元素与第二个范围的第一个元素之前,我们无法决定)。n - m 越大,越差。<
>
false
false
但是有了operator<
,我们可以更快地决定(更确切地说永远不会再晚),我们是否应该false
从算法中返回,因为我们已经从第二个序列中读取了一个元素,该元素在第一个序列中的下一个元素之前。
例子:
{1} 是 {2, ..., 10 6 } 的子范围吗?
operator==
: 10 6 - 1 比较 operator<
: 1 比较
然而,即使是版本,在这个例子operator<
中仍然受到影响:
{10 6 } 是 {1, ..., 10 6 - 1} 的子范围吗?
operator==
: 10 6 - 1 比较 operator<
: 10 6 - 1 比较
然后由程序员来选择预期会产生更短决策时间的迭代方向。
总体而言,处理有序序列的算法根据顺序比较工作,因为它们提供了对输入序列的更多洞察。
1. 如果没有对任一范围的排序要求(以及随机访问迭代器),复杂性会更高(取决于使用额外的结构/预排序)。
推荐阅读
- r - 在 PHP 页面上抓取关键字
- python - How to split a dataset with multiple variables into train and test while both having the same composition using python?
- python - 如何以列名作为标识符融化 pd.dataframe?
- javascript - 嵌套地图中的Reactjs handleclick绑定不起作用
- python - Python 中的网页抓取 - 我在价格列中收到特殊字符,但网页中没有特殊字符
- javascript - 从上传的pdf中获取包含换行符的文本
- flutter - Flutter 资产图像无法正确显示
- javascript - OAuth 2.0 的 Google 弃用通知
- docker - 文件夹存在于容器中,但无法 cd 进入 dockerfile 中的文件夹
- php - phpcs --standard=PHPCompatibility 未检测到错误