Sorting char arrays

[Magnus Lie Hetland]

On 2012-03-12 17:24:56 +0000, Jonathan M Davis said:

> The problem is that sort requires a random access range, and narrow string
> (string and wstring) aren't, because they're variable length encoded. I'm not
> sure that strings _can_ be efficiently sorted, because of that, but maybe
> there's a sorting algorthm that could do it reasonably efficiently,

I'd certainly think that'd be posible. (Might, in fact, be a nice 
problem for the students in my algorithms class ;)

I guess I'm just tripped up by the fact that char[] is treated as an 
"almost-string", and hence is "infected" by the variable-length 
encoding of string (i.e., const char[]).

This all makes sense, for sure -- at least as a practical tradeoff or 
the like. (After all, UTF-8 is a super-elegant solution to a very 
difficult problem.) It's just so easy to assume that T[] is a 
random-access range. It seems so *obvious*. And it is true for any type 
T except the variable-length chars... :)

In my case, I was just using char literals (and strings) as an easy way 
of encoding test cases for a template class, and the sorting (+ uniq) 
was just a way of removing duplicates. (Could've used a hash, of 
course.) So I was really just treating it as a ubyte[]. Slightly 
Evil[tm], I guess.

> and we could
> special case sort for narrow strings to use that one, but it's a while since I
> messed with sorting algorithms, so I don't remember all of their
> characteristics off of the top of my head. Certainly, with how sort is currenly
> implemented, it can't handle any range which isn't a random access range.

No, I get that. I was just assuming that any T[] could be treated as a 
random access range if I really wanted to ;)

-- 
Magnus Lie Hetland
http://hetland.org