Вставьте и ищите быстро

Question

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

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

Спасибо Авинаш

Answer 1

Если одна и та же структура данных должна выполнять обе операции, то это должна быть карта хеша .

Answer 2

по моему мнению hash_map

Answer 3

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

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

вектор [N]

Чтобы вставить ребро из узла x в узел y, вы используете:

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

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

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

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