[boost] Re: lexicographic: review request?

From: Jan Langer (jan_at_[hidden])
Date: 2003-08-31 14:53:04

Brian McNamara wrote:
>>The point is, that Jan proposed to add something which has a hidden 
>>overhead and I'm not sure it's a good idea. Instead of nested 
>>if-else-cascades, the user could also write:
>>
>>bool operator<( const person& lhs, const person& rhs )
>>{
>>   return
>>      lhs.lastname != rhs.lastname ? lhs.lastname < rhs.lastname :
>>      lhs.firstname != rhs.firstname ? lhs.firstname < rhs.firstname :
>>      lhs.age < rhs.age;
>>}
> 
> 
> I am (re)appearing mid-thread, so I may have missed something along the
> way, but...
> 
> What's with "!="?  I think lexicographical orderings are built only on
> the assumptions of operator<, yes?  For two objects x and y, if neither
>    x < y
> nor
>    y < x
> is true, then they are in the same equivalence class, but this is not
> the same thing as equality or inequality.
> 
> I just want to make sure the template parameter constraints (or macro
> parameter constraints, as the case may be) are the right ones.

you are right. lexicographic only needs the operator < or the functor.

btw. i made some performance checks. for those who are interested the 
code is in lex_performance_test.cpp in the libs/utility/test in the 
sandbox. it just sorts a big vector of int for four criteria.

the outcome is as follows (linux/g++ 3.2.2, release build):
boost::lexicographic, division - 2.11
boost::lexicographic, no division - 1.21
boost::lexicographic emulation, no division - 0.68
if cascade, division - 0.92
if cascade, no division - 0.54

where emulation is the same algorithm as lexicographic, but everything 
is written inline (by hand). and the diference between division and no 
division is as follows.

division:

boost::lexicographic
   (a / 1000, b / 1000)
   (b / 100, a / 100)
   (a / 10, b / 10)
   (b, a)

no division:

boost::lexicographic
   (a, b)
   (b, a)
   (a, b)
   (b, a)

the result makes me think, that the comparison code is in fact not 
really inlined (1.21 with lexicographic to 0.68 with the emulation). and 
my unexperienced look into the assembly code acknowledges this.

maybe someone with a different compiler can run the test.

jan

-- 
jan langer ... jan_at_[hidden]
"pi ist genau drei"