Why Strings as Classes?

[Benji Smith]

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.

Not a counterargument to what you're saying about performance guarantees 
for indexing and swapping. Just something else to think about.

--benji