Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > сотавление дерева из списка файлов

Автор: Proxin 26.10.2018, 13:32

Добрый день! Есть следующий вопрос - мне нужно составить из списка наподобие этого
a/b/c
c/a/k
d/o/v
a/b/d
d/h

древовидную стуктуру
a
  +b
    +c
    +d
c
  +a
     +k
d
   +o
     +v
   +h
Немного путано обяьснил, но думаю задача ясна. ближайшая аналогия - дерево папок. формат исходного списка менять я не могу.
Пробовал в лоб - list из структур, у которых есть имя и свой дочерний лист, поиском на каждую строку, разбивая её по подстрокам, и сравнивая с существующими названиями путём strcmp. Проблема в том, что это долго, изначальный список может быть с любыми уровнями вложенности и любого размера. Есть какой-нибудь алгоритм, который будет быстрее такой сортировки "в лоб"? буст не предлагать, пишу на чистом с++.

Автор: xvr 26.10.2018, 14:41

Делаете дерево из std::map. Как то так:

Код


class Node {
  std::map<std::string, std::shared_ptr<Node>> node;
};

Далее разбиваете свои строки по '/' и складываете в Node::node

Автор: Proxin 28.10.2018, 18:08

Спасибо! Прирост скорости заметен.
Тут по мапу такой вопрос - у меня ключ завязан на текст в ноде ( высчитывается как срс32 от текста ), текст можно будет редактировать. Соответственно хотелось бы иметь возможность изменять этот ключ. Нет другого варианта, кроме как удалять и вставлять ноду заново, или здесь лучше использовать другой тип контейнера?

Автор: xvr 29.10.2018, 11:36

Цитата(Proxin @ 28.10.2018, 18:08

)

Нет другого варианта, кроме как удалять и вставлять ноду заново, или здесь лучше использовать другой тип контейнера?

При изменении ключа вся ветка может переехать в совершенно другое место. Т.е. вам придется найти новое место (при любой реализации контейнеров), а это будет O(N*log N)
Удаление и вставка в map так же будет O(N*log N), так что искать какие то другие контейнеры смысла нет.

Цитата(Proxin @ 28.10.2018, 18:08

)

Тут по мапу такой вопрос - у меня ключ завязан на текст в ноде ( высчитывается как срс32 от текста )

Тогда вместо std::map возьмите std::unordered_map - будет быстрее