Lexicographical ordering of multiple doubles

Question

Consider a class of type doubles

class path_cost {
   double length;
   double time;
};

If I want to lexicographically order a list of path_costs, I have a problem. Read on :)

If I use exact equal for the equality test like so

bool operator<(const path_cost& rhs) const {
   if (length == rhs.length) return time < rhs.time;
   return length < rhs.length;
}

the resulting order is likely to be wrong, because a small deviation (e.g. due to numerical inaccuracies in the calculation of the length) may cause the length test to fail, so that e.g.

{ 231.00000000000001, 40 } < { 231.00000000000002, 10 }

erroneously holds.

If I alternatively use a tolerance like so

bool operator<(const path_cost& rhs) const {
   if (std::fabs(length-rhs.length)<1-e6)) return time < rhs.time;
   return length < rhs.length;
}

then the sorting algorithm may horribly fail since the <-operator is no longer transitive (that is, if a < b and b < c then a < c may not hold)

Any ideas? Solutions? I have thought about partitioning the real line, so that numbers within each partition is considered equal, but that still leaves too many cases where the equality test fails but should not.

(UPDATE by James Curran, hopefully explaining the problem): Given the numbers:

• A = {231.0000001200, 10}
• B = {231.0000000500, 40}

• C = {231.0000000100, 60}

  • A.Length & B.Length differ by 7-e7, so we use time, and A < B.
  • B.Length & C.Length differ by 4-e7, so we use time, and B < C.
  • A.Length & C.Length differ by 1.1-e6, so we use length, and A > C.

(Update by Esben Mose Hansen) This is not purely theoretical. The standard sort algorithms tends to crash or worse when given a non-transitive sort operator. And this is exactly what I been contending with (and boy was that fun to debug ;) )

Answer 1

Do you really want just a compare function?

Why don't you sort by length first, then group the pairs into what you think are the same length and then sort within each group by time?

Once sorted by length, you can apply whatever heuristic you need, to determine 'equality' of lengths, to do the grouping.