title: C++ string sort like a human being?
body: <p>I would like to sort alphanumeric strings the way a human being would sort them. I.e., "A2" comes before "A10", and "a" certainly comes before "Z"! Is there any way to do with without writing a mini-parser? Ideally it would also put "A1B1" before "A1B10". I see the question <a href="https://stackoverflow.com/questions/34509/natural-human-alpha-numeric-sort-in-microsoft-sql-2005">"Natural (human alpha-numeric) sort in Microsoft SQL 2005"</a> with a possible answer, but it uses various library functions, as does <a href="http://www.codeproject.com/KB/dotnet/SortingStringsForHumans.aspx" rel="nofollow noreferrer">"Sorting Strings for Humans with IComparer"</a>.</p>
  
  <p>Below is a test case that currently fails:</p>
  
  <pre><code>#include &lt;set&gt;
  #include &lt;iterator&gt;
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;cassert&gt;
  
  template &lt;typename T&gt;
  struct LexicographicSort {
    inline bool operator() (const T&amp; lhs, const T&amp; rhs) const{
      std::ostringstream s1,s2;
      s1 &lt;&lt; toLower(lhs); s2 &lt;&lt; toLower(rhs);
      bool less = s1.str() &lt; s2.str();
      //Answer: bool less = doj::alphanum_less&lt;std::string&gt;()(s1.str(), s2.str());
      std::cout&lt;&lt;s1.str()&lt;&lt;" "&lt;&lt;s2.str()&lt;&lt;" "&lt;&lt;less&lt;&lt;"\n";
      return less;
    }
  
    inline std::string toLower(const std::string&amp; str) const {
      std::string newString("");
      for (std::string::const_iterator charIt = str.begin();
           charIt!=str.end();++charIt) {
            newString.push_back(std::tolower(*charIt));
          }
          return newString;
        }
  };
  
  
  int main(void) {
    const std::string reference[5] = {"ab","B","c1","c2","c10"};
    std::vector&lt;std::string&gt; referenceStrings(&amp;(reference[0]), &amp;(reference[5]));
  
    //Insert in reverse order so we know they get sorted
    std::set&lt;std::string,LexicographicSort&lt;std::string&gt; &gt; strings(referenceStrings.rbegin(), referenceStrings.rend());
  
    std::cout&lt;&lt;"Items:\n";
    std::copy(strings.begin(), strings.end(), std::ostream_iterator&lt;std::string&gt;(std::cout, "\n"));
    std::vector&lt;std::string&gt; sortedStrings(strings.begin(), strings.end());
    assert(sortedStrings == referenceStrings);
  }
  </code></pre>