Сортировка std :: строк с числами в них?

Question

Я сейчас сортирую по оператору std :: string <. Проблема в том, что: </p>

30 <9. 30 появляется до 9, так как 3 <9, Windows 9x имела эту проблему. Как я мог отсортировать их по численности, чтобы «30 лис» появлялись после «9 собак». Я также должен добавить, что я использую кодировку utf 8. </p>

Спасибо

Answer 1

Вы можете создать пользовательскую функцию сравнения для использования с std::sort. Эта функция должна проверить, начинается ли строка с числового значения. Если это так, преобразуйте числовую часть каждой строки в int, используя некоторый механизм, такой как поток строк. Затем сравните два целочисленных значения. Если значения сравниваются одинаково, сравните нечисловую часть строк лексикографически. В противном случае, если строки не содержат числовой части, просто сравните две строки лексикографически, как обычно.

По сути, что-то вроде следующей (непроверенной) функции сравнения:

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());
}

А потом ...

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

РЕДАКТИРОВАТЬ: Конечно, этот алгоритм полезен, только если вы сортируете строки, где числовая часть появляется в начале строки. Если вы имеете дело со строками, где числовая часть может отображаться в любом месте в строке, то вам нужен более сложный алгоритм. См. http://www.davekoelle.com/alphanum.html для получения дополнительной информации.

Answer 2

Если вы ориентируетесь на Windows (XP +) и можете позволить себе конвертировать строки в utf-16, вы можете использовать функцию StrCmpLogicalW из Shlwapi.Подробнее см. msdn .

В противном случае ICU обеспечивает эту функцию в своих сборщиках.Смотри UCOL_NUMERIC_COLLATION.

Answer 3

Вот версия, которая не преобразуется в целое число и, следовательно, работает для длинных строк цифр независимо от sizeof (int).

#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));
}