Советы о том, какую структуру данных использовать для быстрого поиска C ++

Question

Я сейчас нахожусь в процессе обдумывания структуры данных, которую я мог бы использовать для текущего проекта. Мне не нужно удалять элементы, так как я загружаю базу данных, использую ее и затем покидаю программу. Единственное ограничение касается времени поиска. (Память во второй раз, но в основном время).

Обзор того, что я собираюсь сделать. Я анализирую файлы и извлекаю информацию, которую использую для создания различных объектов. После прочтения файлов и создания объектов у меня есть набор из нескольких объектов, которые ссылаются на другой в виде строки.

Цель - найти, какая сеть переходит из одного домена в другой

Например: текстовый файл ввода:

module Blabla 
netTomodule Foo
domain 1
..../*Other parameters of the module*/
end module

module Foo 
netTomodule Blabla
netTomodule Foo2
domain 2
..../*Other parameters of the module*/
end module

module Foo2
netTomodule Foo
domain 2
..../*Other parameters of the module*/
end module

После прочтения я получаю 3 объекта модуля Foo Foo2 и Blabla и их атрибуты следующие:

class Module{
private :
string name;
int domain;
netlist * mynetlist;
...
}  

Мое мнение и вопрос, по которому я хочу получить совет:

Подумав об этом, я думаю, что мой лучший шанс:

1. При чтении файла и извлечении информации я должен создать связанный список модулей.
2. Затем с номером прочитанного Модуля я создаю массив, который в два раза больше этого размера.
3. Для каждого модуля я использую хеш-функцию для хеширования имени модуля и помещаю указатель на этот модуль по указанному индексу в массиве
4. Теперь, когда я захочу найти модуль, мне просто нужно вычислить значение хеш-функции и получить указатель на заданный индекс (или увеличить его, если это не очень хороший модуль из-за коллизии, ранее созданной в массиве)

Это в основном реализация хеш-таблицы или, по крайней мере, то, что я знаю о хеш-таблице из моего предложения.

Мой вопрос Это хорошая мысль? Есть ли библиотека хеш-таблиц, которую я могу использовать для этого? (я слышал и искал unordered_map и map, но я не знаю, подходит ли она мне очень хорошо)

Это огромный текст, поэтому я надеюсь, что он достаточно подробный, поэтому спасибо, если у вас хватит смелости прочитать все!

Answer 1

Просто используйте любую хеш-таблицу, которая входит в вашу стандартную библиотеку или из boost . У большинства будет unordered_map (как указано TR1 и предложено для C ++ 0x), как и Boost, но у некоторых будет std::hash_map или stdext::hash_map с различной реализацией, немного отличающейся, например оригинальный SGI против Microsoft.

Вам не нужно создавать список, просто поместите объекты непосредственно в хеш-таблицу; это позволяет последовательную итерацию, хотя это будет в некотором фиксированном случайном порядке.

Answer 2

вы можете поддерживать хеш-таблицу (string => указатель на объект типа Module) вместо списка ссылок.

Снова внутри класса Module, снова поддерживать хэш-карту или карту строки => pointer

Answer 3

Если вас также интересуют косвенные отношения (Foo2 -> Foo -> BlaBla), у вас, по сути, есть график.В этом случае вы можете использовать Boost.Graph .