What kind of keys are you going to store? Numbers? Strings? But to compare them, you need different operators. And when dealing with data structures, you'll do lots of comparisons.

Another alternative is to store numeric values so cmp always works, 0 padding numbers if necessary. How would that compare (no pun intended) for performance?

It feels like this is a generalization of the type of problem that the GRT and ST sorting approaches solve.
--
Mike