C++ string вроде человека?

Question

Я хотел бы сортировать буквенно-цифровые строки таким образом, чтобы человек сортировал их. I.e., «A2» предшествует «A10», а «a», безусловно, предшествует «Z»! Есть ли способ сделать это без написания мини-парсера? В идеале он также поставил бы «A1B1» перед «A1B10». Я вижу вопрос "Natural (human alpha-numeric) sort in Microsoft SQL 2005" с возможным ответом, но он использует различные библиотечные функции, как и "Sorting Strings for Humans with 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

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

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

Answer 3

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

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

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

Answer 4

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

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

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