Алгоритм связанный с графами?

Допустим есть бинарный файл в нем храниться граф без циклов.
Считываемая структура имеет примерно такой вид:

Последовательно считываю структуры в 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 могут повторяться имена в ссылках.