的算法匹配前綴和名字名

Question

的名單上有所有文件的std::vector<std::string>在目錄：

// fileList 
folder/file1 
folder/file2 
file3 
file4.ext 

和文件名的std::set<std::string>與同爲所有使用的文件夾前綴：

// set1 
file2 
file4.ext 

// set2 
folder 

我需要生成完整的（相對）路徑在設置1中的所有文件，但看不到這樣做的方式，而不會被fileList.size()

0123上設置2迭代 set1.size()倍，乘以

UPDATE：一些澄清：

預期輸出上面的例子：

folder/file2 
file4.ext 

提案（低效？）溶液，也許太冗長，用笨實現：

// pseudo-code! 
vector<string> allpossibleFullPaths(set1.size()*set2.size()); 
vector<string> output; 
foreach(prefix_in_set2) 
    foreach(filename_in_set1) 
     allpossibleFullpaths.push_back(set2[i] + "/" set1[i]) 

foreach(filename_in_fileList) 
    files.push_back(find(fileList[i] in allpossibleFullPaths)); 

（快速pseudocode- ish） 這看起來效率很低，有沒有更好的方法來進行這些比賽？

謝謝！ PS：更好的辦法是跟蹤雙打，這樣我就可以向用戶發出警告。

Answer 1

的一個領域，你是不是清楚的是：

• 考慮設置1 &如上所述集2，如果有什麼的fileList有「file4.ext」和「文件夾\ file4.ext」。你想要兩個嗎？或者是set1中的文件列表保證是唯一的？

假設你想同時，僞代碼：

foreach(pathname in fileList) 
    separate pathname into path & filename. 
    if path is not empty, but not in set2, skip to next pathname. 
    if filename is in set1, output pathname. 

由於一組查詢應該是O（1），總複雜度爲O（2 * fileList.Length）

如果set1中的文件名是唯一的，您可以計算路徑名輸出的數量，並在達到set1.Length時提前退出。

逐步瀏覽最長的集合看起來反直覺，但它也有最慢的查找，所以對fileList的操作必須最小化。

更新：下面是完整的工作的C++代碼（包括& usings消隱）

void ListFiles() 
{ 
    vector<string> fileList; 
    fileList.push_back("folder/file1"); 
    fileList.push_back("folder/file2"); 
    fileList.push_back("file3"); 
    fileList.push_back("file4.ext"); 

    set<string> set1; 
    set1.insert("file2"); 
    set1.insert("file4.ext"); 

    set<string> set2; 
    set2.insert("folder"); 

    for(vector<string>::iterator iter = fileList.begin(); 
     iter != fileList.end(); 
     ++iter) 
    { 
     string pathname = *iter; 
     string filename; 
     string path; 
     size_t pos = pathname.find('/'); 
     if (pos == string::npos || pos == 0) 
      filename = pathname; 
     else 
     { 
      path = pathname.substr(0, pos); 
      if (set2.find(path) == set2.end()) 
       continue; 
      filename = pathname.substr(pos+1); 
     } 
     if (set1.find(filename) != set1.end()) 
      cout << pathname << endl; 
    } 

} 

Answer 2

簡單：迭代fileList一次，生成前綴（set 2條目）和文件名（set 1條目），並檢查它們是否在它們各自的集合中。如果兩者都是，你有一個匹配，所以回報它;否則，不返回該項目。

此外，這處理你提到的'雙打'問題。

Answer 3

只需使用一個輔助的哈希表來獲得set1.size（）+ fileList.size（）的運行時間

僞代碼：

unordered_set<string, list<string> > hash; 
foreach (i in fileList): 
    (fprex, fname) = split(i) 
    hash[fname].push_back(fprex) 
foreach (j in set1): 
    a = hash.contains(j) 
    if (a != hash.end()) 
    foreach(k in a) 
     print k +'/' + j; 

或者somethng這樣。 unordered_set在Boost（或tr1）中可用，插入/查找操作位於O（1）中。

Answer 4

您預期的結果看起來像你正在尋找文件清單中設置1匹配行時，並設置2是無關緊要的後綴。

set2的大小決定實際匹配的方式。如果它相當小，可以將它轉換爲正則表達式，並添加正則表達式以匹配字符串的末尾或預處理FileList（通過僅提取文件名，但也保留結果的原始字符串）。您也可以在兩個列表中反轉字符串，以便它確實成爲前綴匹配。

如果set2很大，那麼您需要從中構建散列表，在這種情況下，您需要預處理FileList以提取文件名作爲「鍵」，您將嘗試在散列表中「查找」 。確保你處理區分大小寫，如果這是一個潛在的問題（如將所有鍵轉換爲大寫）。有了這個，只需打印出FileList中的每一行，它的關鍵就在集合1的哈希表中。

如果集合2有一些意義（在這種情況下，您的預期結果是錯誤的），那就是第二次過濾第一次過濾結果 - 第二次過濾使用另一個哈希表。