在地圖中使用數組作爲鍵C++

基本上，我需要找到所有匹配的anagrams單詞。我正在做的是使用一個大小爲26的數組來表示單詞中的字母。例如： abcdefg = {1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ，0,0,0,0} aaaaaaa = {7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ，0,0,0,0,0,0,0}在地圖中使用數組作爲鍵C++

這就是我如何創建數組。

//stringtemp is a C++ string representing the word. 
//letters is a size 26 int array representing all the letters in the string. 
for(int i=0;i<stringtemp.length();i++) 
{ 
    letters[stringtemp[i]-65]+=1; 
}

這就是我將數組存儲在地圖中的方式。

dictionary[letters].push_back(stringtemp);

所以，我做錯了什麼或在C++中是不可能的。在我發現的所有其他答案中，他們建議使用向量作爲關鍵字，但這不適用於我的情況（我認爲）。

來源

2012-09-15 user1525047

正如下面的答案所反映的，C樣式數組不會像您期望的那樣複製。 –

包括「字典」和「字母」的定義將有所幫助。 – Gabriel

地圖中的鍵類型必須爲其定義operator<。你可以爲你的數組類型定義operator<，但是有一種更簡單的方法：將每個單詞中的字母按字母順序排序，並使用該排序的字符串作爲鍵。

來源

2012-09-15 15:29:03

但是，包含12000個「a」的字符串的效率相當低。 –

所有std::array<T, 26>，std::string和std::vector<T>是完全有效的密鑰類型在std::map，因爲它們都定義小於比較運營商。請注意，std::array<T, 26>與std::tuple<T, T, ..., T>類似，並且按字典順序對比較進行了定義，與字符串比較非常相似。

#include <array> 
#include <map> 

typedef std::array<unsigned int, 26> alphabet; 

std::map<alphabet, std::string> dictionary; 

dictionary[{{1, 0, ..., 8}}] = "hello";

有了多一點的工作，你也可以讓所有類型的鍵爲std::unordered_map，但你必須要（用hash_combine）從升壓加一點樣板代碼。

來源

2012-09-15 15:29:11

'std :: string'實際上並不是爭用的關鍵類型。 –

@LucDanton：'string'會在緊縮時執行，而且它是唯一一種爲其定義的現成散列函數的類型。所以如果一個哈希表在計算上是不可缺少的，那麼使用一個字符串會比在一個向量上定義你自己的哈希運算更容易。否則，你有一個有效的課程。 –

@LucDanton：感謝您的修復！我總是忘記那些額外的大括號... –

std::map允許您在構造函數中提供一個Compare運算符。您可能需要提供這樣的比較器才能使兩個數組{1，...}和{1，...}匹配，因爲它們可能是不同的實際對象。

來源

2012-09-15 15:29:49

改變你的int數組與operator <構建：

struct letter_counter { 
    static const unsigned SIZE = 26; 
    int data[SIZE]; 
    friend bool operator < (const letter_counter& l, const letter_counter& r) 
    { 
    for (unsigned i = 0; i < SIZE; ++i) { 
     if (l.data[i] < r.data[i]) 
      return true; 
     if (l.data[i] > r.data[i]) 
      return false; 
    } 
    return false; 
    } 
};

或者，如果你有C++的編譯器中11的支持 - 只需使用std::array<int,26>。

來源

2012-09-15 21:22:32 PiotrNycz

在地圖中使用數組作爲鍵C++

回答

相關問題