Допустим есть бинарный файл в нем храниться граф без циклов.
Считываемая структура имеет примерно такой вид:
Последовательно считываю структуры в std::list
str1-str2-str3-..-strN
после того как считал какую либо str считываю её refs.
Структура str имеет вид
std::string name;
std::list refs;
Ref имеет вид
std::string sname;
Datatype data;
sname это имя str в изначальном списке и я хочу избавиться от имени,а просто проставить ссылку на структуру в спике, т.е. сделать
Ref
Str* pstr;
Datatype data;
причем еще у разных Ref в списке могут быть одинаковые sname и я хочу объединить их, по идее это сэкономит немного памяти(не будут дублироваться ссылки).
Ref
Str* pstr;
std::vector datavec;
Так вот что выгодней, сразу считать всё в std::list и потом с этим как то работать или добавлять итеративно поштучно.
Считывает и кладём итеративно алгоритм:
1.Считали str добавили в конец главного списка.
2.Начинаем считывать ref.
2.1 просматриваем список ref у текущей str, если нашли с таким же именем добавляем в std::vector, если не нашли, то проходим по списку всех str, создаем новый ref , проставляем ссылку на найденную str.
Сначала считываем, потом работаем алгоритм:
Считываем всё, получаем список str и у каждого str список ref, должны избавиться от строк и проставить ссылки.
1.Сортируем по строке списки ref у каждого, объединяем с одинаковыми именами (как лучше?).
2.Проходимся по новому списку ref у каждой str и для каждого ref проходимся по списку str и находим по имени нужную str и проставляем ссылку.
Обилие поисков по строке как бы намекает, что нужно использовать std::map( или что получше есть?) вместо std::list.
Или может для этого есть какой то специальный алгоритм.
Граф(дерево) скорее широкое чем глубокое и еще по моим наблюдениям скорее разреженное.
Kол-во структур str около 10k, а кол-во ref около 90kk.
Заранее не известно кол-во str'ов и ref'ов, они считываются последовательно.
Простой пример для наглядности:
1. считали "структура1", положили в в список std::list strs;
2. далее считываем ref'ы от "структура1",
"s_структура2" , "s_структура2" , "s_структура5",
положилив std::list str.refs
3. Повторяем такие же шаги для следующих структур.
Так вот во-первых меня напрягает, то что std::list требует на каждый элемент доп. память + мне еще надо избавиться от ссылкок путем строчных имён, а проставить настоящие ссылки, а для этого я должен искать как минимум по strs, а возможно еще и по refs у текущего str, т.к. у ref могут повторяться имена в ссылках.
не знаю как насчет максимальный, но вот файл с которым я работаю сейчас, кол-во str <10k , а кол-во ref около 90kk , т.е. граф(дерево) скорее широкое чем глубокое.
Раз этот огромный граф хранится на диске и вас беспокоит память для std::list, то можно, например, сохранить на диск (или попробовать в память) матрицу смежности, для которой пишутся базовые алгоритмы. Конечно, не совсем ясна задача, но это вариант "в лоб", для базовых вещей.
