Error in function sort

Question

I'm trying to use the sort function from STL, but it gives me an error during execution.

My compare function returns true if v is smaller then e:

bool smallerThan(VertexEntry &v, VertexEntry &e) {
   if(v.v[0] < e.v[0]) return true;
   else if(v.v[1] < e.v[1]) return true;
   else if(v.v[2] < e.v[2]) return true;
   return false;
}

and here is the call:

sort(vertices.begin(),vertices.end(),smallerThan);

The size of the vector is aprox 400 elements.

Can somebody help me solve my problem? Thank you!!

By the way, I tried debugging and found out that the error is not in the function smallerThan — Sara
– Sara, Commented Apr 18, 2011 at 16:38

Erik · Accepted Answer · 2011-04-18 16:37:10Z

9

Your comparison function is incorrect - it doesn't enforce strict weak ordering.

Use this:

bool smallerThan(VertexEntry const & v, VertexEntry const & e) {
   if (v.v[0] < e.v[0]) 
     return true;
   else if(v.v[0] > e.v[0]) 
     return false;
   else if(v.v[1] < e.v[1]) 
     return true;
   else if(v.v[1] > e.v[1])
     return false;
   else if(v.v[2] < e.v[2])
     return true;
   return false;
}

answered Apr 18, 2011 at 16:37

Erik

91.8k13 gold badges203 silver badges192 bronze badges

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

8 Comments

Potatoswatter Over a year ago

It's better to avoid the > operator as it is often not overloaded when < is.

Erik Over a year ago

@Potatoswatter: I'd say it's better to implement the operators you need, perhaps in terms of operator<. For a template sure, for a specific class, I prefer the above.

Potatoswatter Over a year ago

@ybungalobill, @Erik: It's user-friendly to implement all the operators every time, but it's an impractical amount of work. If you actually do that, more power to you. In this case, operator> is not needed.

Potatoswatter Over a year ago

@Erik: The Standard defines LessThanComparable as a common requirement for templates (17.6.3.1), and that is how ordering relationships are defined. Overloading std::less for a class or defining operator> gets you nowhere with respect to the standard library, or any well-written third-party library.

Potatoswatter Over a year ago

@Erik: Today there's one function or class, tomorrow there might be a dozen. It's called maintainability. Simply put, eliminating a function by rearranging the arguments is a design win.

|

Mark B · Accepted Answer · 2011-04-18 16:42:21Z

2

Your comparison operator doesn't enforce strict weak ordering. If you're able to use boost one trick I've seen is to bind your object to a boost::tuple and use its strict weak operator<.

If you need to write it yourself, something like this should work:

bool smallerThan(const VertexEntry &v, const VertexEntry &e)
{
   if(v.v[0] != e.v[0]) return v.v[0] < e.v[0];
   else if(v.v[1] != e.v[1]) return v.v[1] != e.v[1];
   else return v.v[2] < e.v[2];
}

answered Apr 18, 2011 at 16:42

Mark B

96.5k10 gold badges113 silver badges198 bronze badges

Collectives™ on Stack Overflow

Error in function sort

2 Answers 2

8 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related