Вставка и быстрый поиск

Question

Что является лучшими структурами данных для выполнения следующей операции быстро

• Вставить
• Найти.

Благодаря Авинаш

Answer 1

Хорошая реализация для списков смежности графа использует динамически выделенные векторы целых чисел.

Предположим, что на вашем графике имеется не более N узлов. Вы можете сохранить граф в массиве из N динамически выделенных векторов целых чисел. Это будет выглядеть следующим образом:

вектор [N]

Для вставки края от узла к узлу х у вы используете:

вектор [х] .С (у)

Это если граф разрежен (не имеет много ребер), вы можете быстро найти все исходящие края узла.

Если вы хотите найти, существует ли граница между x и y, вам нужно пройти через вектор [x] и выполнить поиск. Если вы хотите ускорить это, вы можете дополнительно использовать 2-мерный булевский массив, если число узлов невелико (менее 1000 - разумно).

Если у вас много узлов и вы хотите ускорить эту операцию, вы можете использовать хэш-карту.

Answer 2

по мне hash_map

Answer 3

Если же структура данных должна делать обе операции, то она должна быть hash map.