Re: [boost] [MultiIndex] "Compatible Sorting Criterion"

Subject: Re: [boost] [MultiIndex] "Compatible Sorting Criterion"
From: David Abrahams (dave_at_[hidden])
Date: 2008-11-02 08:44:02

on Sat Nov 01 2008, Joaquin M Lopez Munoz <joaquin-AT-tid.es> wrote:

> David Abrahams <dave <at> boostpro.com> writes:
>
>> 
>> 
>> The docs mention that the definition is cumbersome.  I think you could
>> probably do much better with a formulation that relies on the concept of
>> being partitioned with respect to a predicate function.  See
>> 
>>   www.open-std.org/jtc1/sc22/wg21/docs/papers/2001/n1313.html
>> 
>> and the wording changes (now in the standard) at:
>> 
>>   http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#270
>
> I'm glad you bring this up: I already knew your work on N1313
> by the time I was writing the compatible sorting thing, and decided
> to go for my formulation instead because the partition phrasing
> obscures, in my opinion, the intuition behind this: One
> can use a sorted range of X's to find embedded Y's if sorting of
> X's implies sorting of Y's. This intuition is a strong leit motif
> in composite keys, for instance.

Interesting you should say so.  IMO thinking of partitioning reveals
much more about the fundamental requirements related to "ordered
search."  

> The partition formulation is undeniably neater technically but
> IMHO it leaves the reader perplexed as to what their actual
> applications are. All of this is highly subjective, of course.

Yes.

> Off topic: It is a pity that the partition-based semantic extension
> to binary_search and similar was not also applied somehow to
> std::[multi]set, as the motivations in N1313 extend naturally to
> this case. Boost.MultiIndex ordered indices do provide this
> extension and I know this has been the reason for its usage
> in certain contexts besides its multi-indexing capabilities.

Good point.  I suggest you write a proposal for the committee.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com