Aubrey Jaffer <ajaffer_at_clearmethods.com> writes:
> | The key should be extracted exactly once for each element.
>
> Because there are potentially more than O(N) comparisons, keys are
> potentially accessed more than once. So the sort routines would need
> to allocate O(N) storage to hold the keys to meet this requirement.
If an implementation extracts keys once, I have a choice: for a fast
key extraction function I can pass a comparator which extracts keys
on each comparison to save some memory, and for a slow key extraction
I can rely on the variant with a key extractor doing the appropriate
thing.
If an implementation extract keys on each comparison, both methods
of specifying the keys are essentially equivalent. In order to
avoid extracting keys many times, I have to manually apply the
decorate-sort-undecorate pattern.
--
__("< Marcin Kowalczyk
\__/ qrczak_at_knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Received on Thu Oct 12 2006 - 19:24:30 UTC