natural-sort.cpp

#include <string>
#include <stdlib.h>

namespace {
static const char * const DIGITS = "0123456789";
}

/// Use with std::sort(start, end, NaturalComparator())
class NaturalComparator
{
  public:
    bool operator()(const std::string& a, const std::string& b)
    {
        size_t offsetA = 0;
        size_t offsetB = 0;
        while (offsetA < a.length() && offsetB < b.length()) {
            size_t posA = a.find_first_of(DIGITS, offsetA);
            size_t posB = b.find_first_of(DIGITS, offsetB);
            if (posA == offsetA && posB == offsetB) {
                char* endA;
                char* endB;
                unsigned long valA = strtoul(a.c_str() + offsetA, &endA, 10);
                unsigned long valB = strtoul(b.c_str() + offsetB, &endB, 10);
                if (valA != valB) {
                    return valA < valB;
                }
                offsetA = endA - a.c_str();
                offsetB = endB - b.c_str();
            } else {
                int comp = a.compare(offsetA, posA - offsetA, b, offsetB, posB - offsetB);
                if (comp != 0) {
                    return comp < 0;
                }
                offsetA = posA;
                offsetB = posB;
            }
        }
        return (offsetA >= a.length());
    }
};