C++字符串排序像一個人？

我想按照人類排序的方式對字母數字字符串進行排序。即，「A2」出現在「A10」之前，「a」肯定出現在「Z」之前！如果不編寫小型解析器，有什麼辦法嗎？理想情況下，它也會在「A1B10」之前放置「A1B1」。我看到"Natural (human alpha-numeric) sort in Microsoft SQL 2005"這個問題有一個可能的答案，但它使用各種庫函數，就像"Sorting Strings for Humans with IComparer"一樣。C++字符串排序像一個人？

下面是目前未能通過測試案例：

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

來源

2010-05-06 Walter Nissen

你有沒有使用'set'而不是'sort'' vector'的原因？ – 2010-05-06 19:32:45

首先，A1B2將如何相對於A2B1進行排序？我從來沒有這樣做過，但我可能會先把你的字符串分成幾塊。文本，數字，文本，數字等等。然後，按照與多個成員的任何其他數據結構相同的方式進行排序，並理解數字位按數字排序而不是字符串。 – 2010-05-06 19:34:10

@Dibling：沒有特別的理由。 @Zickefoose：我將排序（升序）爲：A1B2，A1B10，A2B1。我想你可能是對的，我不得不做一些原始的練習，但是如果我可以幫忙的話，我寧願避免一些容易出錯的地方。 – 2010-05-06 19:44:47

有沒有辦法做，而無需編寫一個小型解析器？

讓別人這樣做呢？

我使用這個實現：http://www.davekoelle.com/alphanum.html，我已經修改了它支持wchar_t的，太。

來源

2010-05-06 20:19:50 peterchen

好吧！正是我一直在尋找，一旦我添加了大小寫不敏感。用'bool less = doj :: alphanum_less （）（s1.str（），s2.str（））;'替換上面的「less」謝謝！ – 2010-05-06 22:47:26

我使用完全相同的鏈接來實現Python中的自然排序，雖然Python積分儘可能大，但要容易得多:) – 2010-05-07 06:56:03

有沒有辦法做到這一點，而無需編寫一個小型解析器？我會認爲答案是否定的。但寫一個解析器並不困難。我不得不這樣做，以便對我們公司的股票數量進行排序。基本上只需掃描數字並將其轉換爲數組。檢查每個字符的「類型」：字母，數字，也許你有其他需要處理的特殊字符。就像我必須特別對待連字符一樣，因爲我們希望A-B-C在AB-A之前排序。然後開始剝離字符。只要它們與第一個字符的類型相同，它們就會進入同一個桶。一旦類型改變，你開始把它們放在不同的桶中。然後你還需要一個比較函數來逐個比較。當兩個桶都是alpha時，只需進行正常的alpha比較。當兩者都是數字時，將兩者都轉換爲整數並進行整數比較，或將較短的長度填充到較長或相當的長度。當他們是不同的類型時，你需要一個規則來比較這些比較，就像A-A在A-1之前或之後一樣？

這不是一個簡單的工作，你必須拿出所有可能出現的多宗個案的規則，但我認爲你能得到它一起工作了幾個小時。

來源

2010-05-06 19:51:45 Jay

沒有任何的分析，有沒有辦法（先用剝離前導零的高值）和正常的字符比較的人寫的號碼爲同一個字符串的一部分。

解析並不需要是非常複雜的，但。一個簡單的哈希表來處理大小寫敏感性和剝離特殊字符（'A'='a'= 1，'B'='b'='2，...或'A'= 1，'a' = 2，'B'= 3，...，' - '= 0（strip）），將您的字符串重新映射到哈希值的數組，然後截斷數字大小寫（如果遇到數字並且最後一個字符是數字，將最後一個數字乘以十，並將當前值添加到它）。

從那裏，按常規排序。

來源

2010-05-06 20:15:07 pdehaan

這真的取決於你的意思是「解析器」。如果你想避免編寫一個解析器，我想你應該利用庫函數。

將字符串視爲一致的字母，數字或「其他」的子序列序列。
使用isalnum獲取每個字符串的下一個字母數字序列，如果它是數字，則返回檢查+或-。使用strtold就地查找數字子序列的結尾。
如果其中一個是數字，另一個是字母，則帶數字子序列的字符串首先出現。
如果一個字符串用完了字符，它首先出現。使用strcoll來比較當前語言環境中的字母順序。
使用strtold來比較當前語言環境中的數字子序列。
重複，直到完成一個或兩個字符串。
與strcmp斷絕關係。

該算法在比較超過long double的精度的數字字符串中有一些弱點。

來源

2010-05-06 20:30:49 Potatoswatter

C++字符串排序像一個人？

回答

相關問題