Как изменить ключ в unordered_map? - PullRequest
Новая
       31

Как изменить ключ в unordered_map?

0 голосов
/ 25 сентября 2018

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

Ответы [ 2 ]

0 голосов
/ 25 сентября 2018

Вы можете использовать unordered_map :: erase и unordered_map :: insert для обновления ключа.Средняя сложность по времени составляет O (1) (кстати, худшее - O (n)).Если вы используете C ++ 17, вы также можете использовать unordered_map :: extract для обновления ключа.Временная сложность та же.

Однако, поскольку вам нужен только набор чисел, я думаю, что unordered_set больше подходит для вашего алгоритма.

0 голосов
/ 25 сентября 2018 
#include <unordered_map>
#include <iostream>

int main()
{
    std::unordered_map<int, int> m;
    m[42];  // add
    m[69];  // some
    m[90];  // keys

    int value = 90;  // value to check for
    auto it = m.find(90);

    if (it != m.end()) {
        m.erase(it);      // remove it
        m[value + 20];    // add an altered value
    }
}
...