Frage Std :: strings mit Zahlen sortieren?


Ich sortiere derzeit nach dem Operator std :: string <. Das Problem damit ist, dass:

30 <9. Die 30 erscheint vor der 9 seit 3 ​​<9, Windows 9x hatte dieses Problem zu. Wie könnte ich sie numerisch so sortieren, dass "30 Füchse" nach "9 Hunden" auftaucht. Ich sollte auch hinzufügen, dass ich utf 8 Codierung verwende.

Vielen Dank


7
2018-01-07 04:29


Ursprung


Antworten:


Sie können eine benutzerdefinierte Vergleichsfunktion für die Verwendung erstellen std::sort. Diese Funktion müsste prüfen, ob die Zeichenfolge mit einem numerischen Wert beginnt. Wenn dies der Fall ist, konvertieren Sie den numerischen Teil jeder Zeichenfolge in eine int einen Mechanismus wie einen Stringstream verwenden. Dann vergleiche die zwei ganzzahligen Werte. Wenn die Werte gleich sind, vergleichen Sie den nicht numerischen Teil der Strings lexikographisch. Andernfalls, wenn die Strings keinen numerischen Teil enthalten, vergleichen Sie einfach die beiden Strings lexikographisch wie normal.

Grundsätzlich so etwas wie die folgende (ungetestete) Vergleichsfunktion:

bool is_not_digit(char c)
{
    return !std::isdigit(c);
}

bool numeric_string_compare(const std::string& s1, const std::string& s2)
{
    // handle empty strings...

    std::string::const_iterator it1 = s1.begin(), it2 = s2.begin();

    if (std::isdigit(s1[0]) && std::isdigit(s2[0])) {
        int n1, n2;
        std::stringstream ss(s1);
        ss >> n1;
        ss.clear();
        ss.str(s2);
        ss >> n2;

        if (n1 != n2) return n1 < n2;

        it1 = std::find_if(s1.begin(), s1.end(), is_not_digit);
        it2 = std::find_if(s2.begin(), s2.end(), is_not_digit);
    }

    return std::lexicographical_compare(it1, s1.end(), it2, s2.end());
}

Und dann...

std::sort(string_array.begin(), string_array.end(), numeric_string_compare);

EDIT: Natürlich ist dieser Algorithmus nur nützlich, wenn Sie Zeichenfolgen sortieren, wo der numerische Teil am Anfang der Zeichenfolge angezeigt wird. Wenn Sie mit Strings arbeiten, in denen der numerische Teil erscheinen kann irgendwo In der Zeichenfolge benötigen Sie einen ausgefeilteren Algorithmus. Sehen http://www.davekoelle.com/alphanum.html für mehr Informationen.


7
2018-01-07 04:35



Wenn Sie auf Windows (XP +) abzielen und es sich leisten können, Ihre Strings in utf-16 zu konvertieren, können Sie das verwenden StrCmpLogicalW Funktion von Shlwapi. Sehen msdn für Details.

Andernfalls, Intensivstation stellt diese Funktionalität in seinen Collators bereit. Sehen UCOL_NUMERIC_COLLATION.


4
2018-01-07 10:11



Hier ist eine Version, die nicht in Ganzzahl konvertiert und daher für lange Ziffernfolgen unabhängig von der Größe von (int) funktioniert.

#include <cctype>
#include <cstddef>
#include <cstring>
#include <string>

int numcmp(const char *a, const char *aend, const char *b, const char *bend)
{
  for (;;) {
    if (a == aend) {
      if (b == bend)
        return 0;
      return -1;
    }
    if (b == bend)
      return 1;
    if (*a == *b) {
      ++a, ++b;
      continue;
    }
    if (!isdigit((unsigned char) *a) || !isdigit((unsigned char) *b))
      return *a - *b;

    // skip leading zeros in both strings
    while (*a == '0' && ++a != aend)
      ;
    while (*b == '0' && ++b != aend)
      ;

    // skip to end of the consecutive digits
    const char *aa = a;
    while (a != aend && isdigit((unsigned char) *a))
      ++a;
    std::ptrdiff_t alen = a - aa;

    const char *bb = b;
    while (b != bend && isdigit((unsigned char) *b))
      ++b;
    std::ptrdiff_t blen = b - bb;

    if (alen != blen)
      return alen - blen;

    // same number of consecutive digits in both strings
    while (aa != a) {
      if (*aa != *bb)
        return *aa - *bb;
      ++aa, ++bb;
    }
  }
}

int numcmp(const std::string& a, const std::string& b)
{
  return numcmp(a.data(), a.data() + a.size(),
                b.data(), b.data() + b.size());
}

int numcmp(const char *a, const char *b)
{
  return numcmp(a, a + strlen(a), b, b + strlen(b));
}

2
2017-12-10 21:21