How to implement a natural sort algorithm in c++?

Several natural sort implementations for C++ are available. A brief review:

• natural_sort<> - based on Boost.Regex.
  • In my tests, it's roughly 20 times slower than other options.
• Dirk Jagdmann's alnum.hpp, based on Dave Koelle's alphanum algorithm
  • Potential integer overlow issues for values over MAXINT
• Martin Pool's natsort - written in C, but trivially usable from C++.
  • The only C/C++ implementation I've seen to offer a case insensitive version, which would seem to be a high priority for a "natural" sort.
  • Like the other implementations, it doesn't actually parse decimal points, but it does special case leading zeroes (anything with a leading 0 is assumed to be a fraction), which is a little weird but potentially useful.
  • PHP uses this algorithm.

This is known as natural sorting. There's an algorithm here that looks promising.

Be careful of problems with non-ASCII characters (see Jeff's blog entry on the subject).

I asked this exact question (although in Java) and got pointed to http://www.davekoelle.com/alphanum.html which has an algorithm and implementations of it in many languages.