这段代码是用编写的C++
。我有以下结构:
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Data
{
int h, b, w;
Data(int _h, int _b, int _w) : h(_h), b(_b), w(_w)
{}
bool operator<(const Data& other) const
{
bool overlap = (other.b >= b && other.b <= w) ||
(other.w >= b && other.w <= w) ||
(other.b < b && other.w > w);
if (overlap)
{
return h < other.h;
}
return h > other.h;
}
};
在operator<
将用于排序。想法是从最高-h到最低-h进行排序,除非两个变量之间b
或w
比较变量之间没有任何重叠。剩余代码:
vector <int> getOrdering(vector <int> height, vector <int> bloom, vector <int> wilt)
{
vector<Data> vdata;
for (int i = 0; i < height.size(); i++)
{
vdata.push_back(Data(height[i], bloom[i], wilt[i]));
}
sort(vdata.begin(), vdata.end());
vector<int> ans;
for (Data data : vdata)
{
ans.push_back(data.h);
}
return ans;
}
int main()
{
vector <int> p0 = { 1, 2, 3, 4, 5, 6 };
vector <int> p1 = { 1, 3, 1, 3, 1, 3 };
vector <int> p2 = { 2, 4, 2, 4, 2, 4 };
vector<int> ans = getOrdering(p0, p1, p2);
for (int a : ans)
{
cout << a << ' ';
}
cout << endl;
return 0;
}
我编写operator<
函数的方式,代码应该输出2 4 6 1 3 5
。但是输出是6 5 4 3 2 1
。我正在使用Visual Studio 2013 Ultimate。
调试完该operator<
函数后,我发现它正被Data
对象调用,如下所示:
1st call: this->h = 2, other.h = 1
2nd call: this->h = 1, other.h = 2
3rd call: this->h = 3, other.h = 2
4th call: this->h = 2, other.h = 3
5th call: this->h = 4, other.h = 3
6th call: this->h = 3, other.h = 4
7th call: this->h = 5, other.h = 4
8th call: this->h = 4, other.h = 5
9th call: this->h = 6, other.h = 5
10th call: this->h = 5, other.h = 6
请注意,当Data
对象的h值为1、3或5时,它们的b和w值相同。它们将按h的升序排序。同去真正的Data
对象其H值是2,4和6,但在operator<()
没有两个Data
对象都比较过其H值是一样的!1比2,2比3,3比4,依此类推。因此,overlap
变量始终为false
。sort()
如果Data
比较h值相同的对象,结果将是不同的-但这从未发生!
关于编译器这种行为的任何解释吗?
这是因为您的运算符<取决于很多数据顺序。如果我们用您的数据运行算法,那是预期的输出。
第一个比较是在Data(1,1,2)和Data(2,3,4)之间。根据您的运算符<,Data(2,3,4)较低,因此临时顺序为[Data(2,3,4),Data(1,1,2)]
然后,出现Data(3,1,2)并将其与当前排序列表的最小值进行比较,从而得出Data(2,3,4)。同样,根据您的运算符<,Data(3,1,2)较低,因此无需与列表中的其他值进行比较,新的临时排序列表为[Data(3,1,2),Data(2 ,3,4),Data(1,1,2)]。
然后,每个其他值都是相同的,它们每次都仅与列表中的第一个值进行比较,因为它们较低(根据operator <),因此位于排序列表的前面。
如果您通过以下方式更改初始化列表的顺序:
vector <int> p0 = { 6, 5, 4, 3, 2, 1};
vector <int> p1 = { 3, 1, 3, 1, 3, 1};
vector <int> p2 = { 4, 2, 4, 2, 4, 2};
您将获得预期的输出,因为将进行更多的比较。
但是结果取决于初始化顺序的事实表明,您的operator <函数显然存在缺陷。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句