Обновление одного значения в отсортированной структуре данных

Question

Мне нужна структура данных, которая может:

1. Добавить одно значение
2. Получить минимальное значение
3. Обновить одно значение

Я могу добиться этого, используя std::multiset, где операции выполняются как:

1. multiset::insert()
2. multiset::begin()
3. сначала удалите элементиспользуя multiset::erase(), затем добавьте обновленный элемент, используя multiset::insert()

. Что мне не нравится в multiset, так это то, что для обновления элемента требуется итератор.Было бы неплохо, если бы указателя было достаточно.

Интересно, будет ли лучше использовать std::priority_queue, алгоритмы std heap или что-то еще для требуемых операций и как это сделать.Первые две операции просты для std::priority_queue или алгоритмов кучи, но третья операция (обновление) является проблемой.Есть ли другие структуры, которые можно использовать?Каковы их преимущества в производительности по сравнению с multiset?

Answer 1

std::priority_queue даст вам эффективные вставки и запросы с наименьшим значением, но обновления будут медленными.Вы можете сделать обновления эффективными, сохраняя указатели в PQ и std::vector и используя вектор для выполнения обновлений.Чтобы выполнить обновление, пометьте запись как устаревшую и вставьте новую обновленную копию.Затем при запросе наименьшего значения игнорируйте устаревшие записи.

Answer 2

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

Вам нужно будет подумать, какие операции должны выполняться быстрее.Если обновление относительно редко, priority_queue может быть лучше.Если вы используете priority_queue один вариант, чтобы сделать update более быстрым, просто пометьте старый элемент как недействительный (при условии, что у вас есть ссылка / указатель на него) и добавьте новый элемент + повторную генерацию.Затем, когда вы вытаскиваете самый низкий элемент, сначала убедитесь, что он не был помечен как недействительный, прежде чем использовать его (иначе получите следующий самый низкий элемент).Этот метод полезен в любое время, когда довольно сложно вынуть предмет из контейнера.