Why Strings as Classes?

[superdan]

Benji Smith Wrote:

> superdan wrote:
> > now take sort. sort says. my input is a range that supports indexing and swapping independent of the range size. if you don't have that just let me know and i'll use a totally different method. just don't pretend.
> > 
> > with that indexing and swapping complexity ain't implementation detail. they're part of the spec. guess stepanov's main contribution was to clarify that.
> 
> The other variable cost operation of a sort is the element comparison. 
> Even if indexing and swapping are O(1), the cost of a comparison between 
> two elements might be O(m), where m is proportional to the size of the 
> elements themselves.
> 
> And since a typical sort algorithm will perform n log n comparisons, the 
> cost of the comparison has to be factored into the total cost.
> 
> The performance of sorting...say, an array of strings based on a 
> locale-specific collation...could be an expensive operation, if the 
> strings themselves are really long. But that wouldn't make the 
> implementation incorrect, and I'm always glad when a sorting 
> implementation provides a way of passing a custom comparison delegate 
> into the sort routine.

good points. i only know of one trick to save on comparisons. it's that -1/0/1 comparison. you compare once and get info on less/equal/greater. that cuts comparisons in half. too bad std.algorithm don't use it.

then i moseyed 'round std.algorithm and saw all that schwartz xform business. not sure i grokked it. does it have to do with saving on comparisons?