Re: [boost] [sorting] What are the most complicated sorting problems?

From: Michael Lacher (michael.lacher_at_[hidden])
Date: 2007-03-20 06:32:08

Lewis Hyatt wrote:
>> * provide an easy way to sort lists of pointers (without having to make 
>> a custom '<' operator each time).
> 
> this is already in boost:
> 
> some_iterator begin, end;
> std::sort(boost::indirect_iterator(begin), boost::indirect_iterator(end));
> 
nice, didn't know that one  :)

> * Easy way to specify different 
>> comparison operators for various subfields. ie. in stead of one complex 
>> '<' operator, specify one for each subfield and then define sortorder 
>> (which subfield first, ...) on sorttime.
> 
> This is an intriguing possibility, what about some intrusive design, where you
> can tag class members as sort keys?
> 
I'm fine with intrusive, but actually i would prefer an adapter class. 
something like (simplified interface for readability):

template<typename SourceClass,typename FieldType1,typename fieldType2, ...>
class sort_field_adapter
{
        const FieldType1& extractField1(const SourceClass& source);
        const FieldType1& extractField2(const SourceClass& source);
        ...
};

rationale:
This could be used to create sort keys "on the fly" (for example, sort 
by sum of member a+b).

I am not sure if it is possible to define an easy, generic adapter 
interface due to the unknown number and types of the fields.

>> * provide a good set of default '<' operators. at least:
>>    - simple types (strings, numbers, ...)
>>    - pointers to simple types
>>    - pairs of the above
> 
> Simple types and pairs already have operator<, and pointers are handled by
> indirect_iterator.

is it possible to use indirect_iterator (or similar) if only one half of 
a pair is a pointer ?

> 
>> * Specify ascending vs. descending sorting. Trivial criteria really, but 
>> reduces complexity (or number) of the '<' operators.
> 
> std::sort(begin, end, std::greater<type>());
> 
ofc, but what about your custom < operators, functors. You would need to 
supply a second, inverted version.

Michael