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

Question

I'm sorting strings that are comprised of text and numbers. I want the sort to sort the number parts as numbers, not alphanumeric.

For example I want: abc1def, ..., abc9def, abc10def

instead of: abc10def, abc1def, ..., abc9def

Does anyone know an algorithm for this (in particular in c++)

Thanks

Answer 1

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.

Answer 2

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.