C ++ строка сортируется как человек?

Question

Я бы хотел отсортировать буквенно-цифровые строки так, как их будет сортировать человек. То есть, «A2» предшествует «A10», а «a» обязательно предшествует «Z»! Есть ли способ обойтись без написания мини-парсера? В идеале было бы также поставить «A1B1» перед «A1B10». Я вижу вопрос "Естественная (человеческая буквенно-цифровая) сортировка в Microsoft SQL 2005" с возможным ответом, но он использует различные библиотечные функции, как и "Сортировка строк для людей с IComparer" .

Ниже приведен тест, который в настоящее время не проходит:

#include <set>
#include <iterator>
#include <iostream>
#include <vector>
#include <cassert>

template <typename T>
struct LexicographicSort {
  inline bool operator() (const T& lhs, const T& rhs) const{
    std::ostringstream s1,s2;
    s1 << toLower(lhs); s2 << toLower(rhs);
    bool less = s1.str() < s2.str();
    //Answer: bool less = doj::alphanum_less<std::string>()(s1.str(), s2.str());
    std::cout<<s1.str()<<" "<<s2.str()<<" "<<less<<"\n";
    return less;
  }

  inline std::string toLower(const std::string& 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<std::string> referenceStrings(&(reference[0]), &(reference[5]));

  //Insert in reverse order so we know they get sorted
  std::set<std::string,LexicographicSort<std::string> > strings(referenceStrings.rbegin(), referenceStrings.rend());

  std::cout<<"Items:\n";
  std::copy(strings.begin(), strings.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
  std::vector<std::string> sortedStrings(strings.begin(), strings.end());
  assert(sortedStrings == referenceStrings);
}

Answer 1

Есть ли способ обойтись без написания мини-парсера?

Пусть кто-нибудь другой сделает это?

Я использую эту реализацию: http://www.davekoelle.com/alphanum.html, Я также изменил ее для поддержки wchar_t.

Answer 2

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

• Обрабатывать строку как последовательность подпоследовательностей, которые являются равномерно буквенными, числовыми или «другими».
• Получите следующую буквенно-цифровую последовательность каждой строки, используя isalnum и проверку возврата для + или -, если это число. Используйте strtold на месте, чтобы найти конец числовой подпоследовательности.
• Если один числовой, а второй буквенный, строка с числовой подпоследовательностью идет первой.
• Если в одной строке не хватает символов, она идет первой.
• Используйте strcoll для сравнения буквенных подпоследовательностей в текущей локали.
• Используйте strtold для сравнения числовых подпоследовательностей в текущей локали.
• Повторяйте, пока не закончите с одной или обеими строками.
• Разорвать связь с strcmp.

Этот алгоритм имеет слабое место при сравнении числовых строк, которые превышают точность long double.

Answer 3

Без синтаксического анализа невозможно сравнить написанные человеком числа (сначала высокие значения с лишенными начальных нулей) и обычные символы как часть одной строки.

Хотя анализ не должен быть ужасно сложным. Простая хеш-таблица для работы с такими вещами, как чувствительность к регистру и удаление специальных символов ('A' = 'a' = 1, 'B' = 'b' = '2, ... или' A '= 1,' a ' = 2, 'B' = 3, ..., '-' = 0 (strip)), переназначить вашу строку в массив хэшированных значений, а затем урезать числа (если встречается число и последний символ был число, умножьте последнее число на десять и добавьте к нему текущее значение).

Оттуда сортируйте как обычно.

Answer 4

Есть ли способ сделать это без написания мини-парсера? Я думаю, что ответ - нет. Но написание парсера не так уж сложно. Я должен был сделать это некоторое время назад, чтобы отсортировать номера акций нашей компании. В основном просто отсканируйте число и превратите его в массив. Проверьте «тип» каждого символа: альфа, число, возможно, у вас есть другие, с которыми вам нужно иметь дело со спец. Как будто я должен был обращаться с дефисами особенным, потому что мы хотели, чтобы A-B-C сортировал до AB-A. Тогда начните отдирать персонажей. Пока они того же типа, что и первый персонаж, они попадают в одно и то же ведро. Как только тип меняется, вы начинаете помещать их в другое ведро. Тогда вам также понадобится функция сравнения, которая сравнивает ведро за ведром. Когда оба сегмента альфа, вы просто делаете нормальное альфа сравнение. Когда оба являются цифрами, преобразуйте оба в целое число и выполните целочисленное сравнение или добавьте более короткую к длине более длинного или что-то эквивалентное. Когда они разных типов, вам нужно правило для их сравнения, например, A-A идет до или после A-1?

Это не тривиальная работа, и вы должны придумать правила для всех странных случаев, которые могут возникнуть, но я думаю, вы могли бы собраться вместе за несколько часов работы.