Добрый день! Есть следующий вопрос - мне нужно составить из списка наподобие этого
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. Проблема в том, что это долго, изначальный список может быть с любыми уровнями вложенности и любого размера. Есть какой-нибудь алгоритм, который будет быстрее такой сортировки "в лоб"? буст не предлагать, пишу на чистом с++.

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


Это сообщение отредактировал(а) xvr - 26.10.2018, 14:42

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

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


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