如何使用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;
}