Re: [Boost-users] Overloading operators with multi index container?

Subject: Re: [Boost-users] Overloading operators with multi index container?
From: pdovydaitis (pdovydaitis_at_[hidden])
Date: 2010-04-29 11:18:33

Joaquin M Lopez Munoz wrote:
> 
> Paul Dovydaitis <pdovydaitis <at> jumptrading.com> writes:
> 
>> 
>> We are using a multi index container to store some data indexed
>> both by a text key and by a timestamp.
>> [...] Â 
>> To do this, we tried to overload operator< in the following way:
>> Â 
>> bool MyTransaction::operator<(const Transaction & rhs) const {
>> Â Â Â  const std::time_t WINDOW = 2;
>> Â Â Â  Â Â 
>> Â Â Â  if (getHashKey() == rhs.getHashKey()) {
>> Â Â Â Â Â Â Â  Â 
>> Â Â Â Â Â Â Â  if ((epochTime() - WINDOW) <= rhs.epochTime() &&
>> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  (epochTime() + WINDOW) >= rhs.epochTime())
>> Â Â Â Â Â Â Â  {
>> Â Â Â Â Â Â Â Â Â Â Â  return false;
>> Â Â Â Â Â Â Â  } else {
>> Â Â Â Â Â Â Â Â Â Â Â  return (epochTime() < rhs.epochTime());
>> Â Â Â Â Â Â Â  }
>> Â Â Â  } else {
>> Â Â Â Â Â Â Â  return (getHashKey() < rhs.getHashKey());
>> Â Â Â  }
>> }
> 
> This less-than operator is ill-defined according to the semantics
> expected by Boost.MultiIndex indexed indices (as well as STL
> associative containers and a number of stdlib algorithms).
> In particular the operator must implement a strict weak ordering:
> 
> http://cpp-next.com/archive/2010/02/order-i-say/
> 
> Among other, a strict weak ordering has the property that
> "equivalence" defined as x~y := !(x<y) && !(y<x) is *transitive*,
> i.e. if x~y and y~z then x~z. Now consider three transactions
> x y and z with the same hash key and epoch times
> 
>   0,2,4,
> 
> respectively. According to your definition of operator<,
> x~y (their epoch times are within a distance of 2) and y~z
> (same argument), *but* x is *not* equivalent to z (the
> distance between their epoch times is 4).
> 
> If your operator< does not implement a strict weark ordering,
> then ordered indices' behavior is undefined. Trying to analyze
> what happens under these conditions is basically pointless.
> 
> Joaquín M López Muñoz
> Telefónica, Investigación y Desarrollo
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 

Awesome answer, thanks Joaquín.  We had overlooked the fact that operator<
needs to implement a strict weak ordering - given that, I can see why what
we are doing would have undefined behavior.

We'll have to revisit what we're trying to do and find a different way to
achieve our goal.

-- 
View this message in context: http://old.nabble.com/Overloading-operators-with-multi-index-container--tp28392488p28401966.html
Sent from the Boost - Users mailing list archive at Nabble.com.