如何使用std :: map或set來管理目錄的路徑？

Question

我想使用stl :: set來放置一些目錄路徑。 該集有一些特殊的目錄路徑，我把它。 我應該找到一些輸入路徑的特殊父項。

有代碼。我評論了一些觀點。

set<wstring> special_directories; 

void WhoIsMySpecialParent(const wstring& f) 
{ 
    set<wstring>::const_iterator it; 
    it = special_directories.upper_bound(f); 

    if (it == special_directories.begin()) 
    { 
     printf("There isn't any special parent."); 
     return; 
    } 

    --it; 
    wprintf(L"The special parent is <%s>\n", it->c_str()); 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    // These are special directories which I will manage. 
    // "/home" and "/home/benjamin" are not included in the special directories. 
    // If I want to make "/home" as special directory, 
    // I have to add "/home" in the set. 
    special_directories.insert(L"/"); 
    special_directories.insert(L"/bin"); 
    special_directories.insert(L"/etc"); 
    special_directories.insert(L"/home/benjamin/documents"); 
    special_directories.insert(L"/var"); 
    special_directories.insert(L"/var/log"); 

    WhoIsMySpecialParent(L"/bin/ls"); // Okay. It prints /bin 
    WhoIsMySpecialParent(L"/var/log/aaaa"); // Okay. It prints /var/log 
    WhoIsMySpecialParent(L"/var/apache2"); // Okay. It prints /var 

    WhoIsMySpecialParent(L"/bz"); 
    // Wrong. It prints "/bin". It should print "/" 

    WhoIsMySpecialParent(L"/home/benjamin"); 
    // Wrong. It prints "/etc", It should print "/" 

    return 0; 
} 

我認爲這可以用upper_bound處理。但我可能是錯的。
您覺得如何？我應該放棄使用std :: set嗎？
如果你是我，你會如何解決這個問題？請任何想法。

Answer 1

使用std::set<T>::upper_bound()可以簡單地找到詞典排序的排序索引，它是樹數據結構中的數學上界，std::set使用。在這種情況下，「/ etc」是「home/benjamin」的上限，因爲如果通過字母表來計算，「home/benjamin」將會在「home/benjamin/documents」之前出現，並在「/ etc」之後。因此，在排序的樹中，您會發現「/ etc」是搜索參數「home/benjamin」的最小上界。如果你想得到「/」作爲結果，你將不得不在數據結構中找到最大的上界，而不是最小的上界。用「最大」來說，我用數學意義上講，在這種情況下，如果存在這些上限，排序後的樹將創建一個拓撲排序，該排序對於給定的搜索字符串具有N個上限。 std::set<T>::upper_bound()方法找到這些上限的至少，這意味着它從辭典排序中找到第一個可能的上限（因爲它是用於對std::string進行排序的方法）。在您的「/ home/benjamin」情況下，您正在尋找最大的上限，其中包含一個「特殊」目錄的根目錄。但不幸的是，將該標準應用於其他案例會破壞其中的一些（即，它將始終返回「/」）。這意味着您將不得不爲您的需求創建一個upper_bound()類型函數的自定義版本，該版本不能嚴格按照元素的字典排序來查找上限。實際上，我甚至不會使用upper_bound搜索。

更好的方法是使用std::string::find_last_of()，並用它來解析/字符的目錄。這樣做，您可以解析並基本上「剝離」目錄路徑，直到您在std::set中找到完美匹配。例如：

void WhoIsMySpecialParent(const wstring& f) 
{ 
    wstring temp = f; 
    while (temp.size()) 
    { 
     temp = temp.substr(0, temp.find_last_of(L"/")); 

     set<wstring>::const_iterator it; 

     //setup a special case for the root directory 
     if (temp.size()) 
      it = special_directories.find(temp); 
     else 
      it = special_directories.find(L"/"); 

     if (it != special_directories.end()) 
     { 
      wprintf(L"The special parent is <%s>\n", it->c_str()); 
      return; 
     } 
    } 

    printf("There isn't any special parent."); 
    return; 
}