1

This code is written in C++. I've the following structure:

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

The operator< will be used for sorting. The idea is to sort from highest-h to lowest-h, unless there is any overlapping between either b or w in comparing variables. Remaining code:

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

The way the I've written the operator< function, the code should output 2 4 6 1 3 5. But the output is 6 5 4 3 2 1. I'm using Visual Studio 2013 Ultimate.

After debugging the operator< function, I found out that it is being called for Data object as follows:

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

Note that when Data objects' h values are 1, 3 or 5, their b and w values are same. They will be sorted by ascending order of h. Same goes true for Data objects whose h values are 2, 4 and 6. But in the operator<() no two Data objects are ever compared whose h values are same! 1 compared to 2, 2 compared to 3, 3 compared to 4 and so on. So the overlap variable is always false. The outcome of sort() would be different if Data objects whose h values are same got compared - but that never happened!

Any explanation of this behavior of compiler?

Improve this question
6
  • 7
    Your operator< does not satisfy the requirements of strict weak ordering. For one thing, it's not transitive. Imagine three blocks, A(h==20), B(h==10) and C(h==30). B and C overlap, A doesn't overlap either. Then, according to your ordering, A < B and B < C but !(A < C) Commented Apr 14, 2015 at 13:42
  • Regardless: overlap can be calculated much easier: bool overlap = other.b <= w && other.w >= b; (assuming b <= w) Commented Apr 14, 2015 at 13:49
  • @IgorTandetnik: Any link to guidance on it? Commented Apr 14, 2015 at 14:36
  • 1
    The idea is to sort from highest-h to lowest-h, unless there is any overlapping And if there is overlapping, then what? You need to figure out meaningful ordering for this case. I can't help you there, because I don't have any idea what real-world phenomena all those numbers are supposed to represent. Commented Apr 14, 2015 at 14:41
  • the code should output 2 4 6 1 3 5 Why is that? The block H5 with height of 5 doesn't overlap the block H2 with height of 2, and its height is greater, so H5 should precede H2 in the sorted order, shouldn't it? How come you expect a result that doesn't match your own explanation? It appears that you yourself haven't yet figured out exactly what you are trying to achieve. Commented Apr 14, 2015 at 14:49

1 Answer 1

Reset to default
1

It is because your operator< depends a lot of the data order. If we run you're algorithm with your data, it's the expected output.

The first comparaison is between Data(1,1,2) and Data(2,3,4). According to your operator<, Data(2,3,4) is the lower so the temp order is [Data(2,3,4), Data(1,1,2)]

Then, Data(3,1,2) comes and is compared against the lowest value of the current sorted list, so Data(2,3,4). Again, according to your operator<, Data(3,1,2) is lower so no need to compare against the other values in the list and the new temp ordered list is [Data(3,1,2),Data(2,3,4), Data(1,1,2)].

Then it's the same for each other value, they are each time only compared to the first value in the list since they are lower (according to operator<) and so put in front of the sorted list.

If you change your init list order with:

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

you'll have the expected output since there will be more comparaison involved.

But the fact that the result depend on the init order show there is clearly a flaw in your operator< function.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.