Мне нужно использовать структуру данных, которая в среднем поддерживает поиск с постоянным временем. Я думаю, что использование 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?
