Мне нужно использовать структуру данных, которая в среднем поддерживает поиск с постоянным временем.Я думаю, что использование std::unordered_map
- хороший способ сделать это.Мои данные - это «коллекция» чисел.
|115|190|380|265|
Эти цифры не обязательно должны быть в определенном порядке.Мне нужно около O(1)
времени, чтобы определить, существует ли данное число в этой структуре данных.У меня есть идея использовать std::unordered_map
, который на самом деле является хеш-таблицей (я прав?)Таким образом, числа будут ключами, и тогда у меня будут просто фиктивные значения.
Итак, сначала мне нужно определить, существует ли ключ, соответствующий данному номеру, в структуре данных, и я запускаю некоторый алгоритм, основанный на этом.состояние.И независимо от этого условия я также хочу обновить определенный ключ.Допустим, 190
, и я хочу добавить к нему 20
, поэтому теперь ключ будет 210
.И теперь структура данных будет выглядеть так:
|115|210|380|265|
Причина, по которой я хочу это сделать, заключается в том, что у меня есть рекурсивный алгоритм, который пересекает двоичное дерево поиска.Каждый узел имеет int value
и два указателя на левый и правый узлы.Когда достигнут конечный узел, мне нужно создать новое поле в структуре данных «хэш-таблицы», содержащей current_node->value
.Затем, когда я возвращаюсь вверх по дереву в рекурсии, мне нужно последовательно добавлять каждое значение узла к предыдущей сумме, хранящейся в ключе.И причина, по которой моя структура данных (которая, как я предполагаю, должна быть std::unordered_map
) имеет несколько полей чисел, заключается в том, что каждое из них представляет уникальный путь, проходящий от листового узла вверх по дереву до определенного узла в середине.Я проверяю, равна ли сумма всех значений узлов на пути от листа, идущего к данному узлу, значению этого узла.Таким образом, в основном в каждый ключ добавляется текущее значение узла, сохраняя сумму всех узлов на этом пути.Мне нужно отсканировать эту структуру данных, чтобы определить, равно ли какое-либо из полей или ключей значению текущего узла.Также я хочу вставить новые значения в структуру данных в почти постоянное время.Это для конкурентного программирования, и я не хотел бы использовать std::vector
, потому что поиск элемента и вставка элемента, я думаю, занимает линейное время.Это испортило бы мою временную сложность.Может быть, я должен использовать другую структуру данных, отличную от std::unordered_map
?