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

Subject: Re: [Boost-users] Overloading operators with multi index container?
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2010-04-28 15:33:37

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