|
Модераторы: Daevaorn |
|
Proxin |
|
|||
Опытный Профиль Группа: Участник Сообщений: 363 Регистрация: 21.6.2008 Репутация: нет Всего: 3 |
Добрый день! Есть следующий вопрос - мне нужно составить из списка наподобие этого
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 |
|
|||
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Делаете дерево из std::map. Как то так:
Это сообщение отредактировал(а) xvr - 26.10.2018, 14:42 |
|||
|
||||
Proxin |
|
|||
Опытный Профиль Группа: Участник Сообщений: 363 Регистрация: 21.6.2008 Репутация: нет Всего: 3 |
Спасибо! Прирост скорости заметен.
Тут по мапу такой вопрос - у меня ключ завязан на текст в ноде ( высчитывается как срс32 от текста ), текст можно будет редактировать. Соответственно хотелось бы иметь возможность изменять этот ключ. Нет другого варианта, кроме как удалять и вставлять ноду заново, или здесь лучше использовать другой тип контейнера? |
|||
|
||||
xvr |
|
||||
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
При изменении ключа вся ветка может переехать в совершенно другое место. Т.е. вам придется найти новое место (при любой реализации контейнеров), а это будет O(N*log N) Удаление и вставка в map так же будет O(N*log N), так что искать какие то другие контейнеры смысла нет.
Тогда вместо std::map возьмите std::unordered_map - будет быстрее |
||||
|
|||||
Правила форума "С++:Общие вопросы" | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |