Как мне управлять путями каталогов с помощью std :: map или set? - PullRequest
Новая
       39

Как мне управлять путями каталогов с помощью std :: map или set?

3 голосов
/ 20 июля 2011

Я бы хотел использовать 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?
Если бы вы были мной, как бы вы решили эту проблему? Любая идея, пожалуйста.

1 Ответ

5 голосов
/ 20 июля 2011

Использование 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() для ваших нужд, которая не работает строго путем лексикографической сортировки элементов, чтобы найти верхнюю границу.На самом деле, я бы даже не использовал поиск в верхнем регистре.

Лучше было бы использовать 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;
}
...