std::unordered_map — как отслеживать максимальный/минимальный ключ в любое время

Ваши точные требования не могут быть выполнены: std::unordered_map работает быстро (т. е. O(1) вставка/удаление/поиск), потому что не упорядочивает свои элементы. Это означает, что поиск минимума/максимума занимает O(N).

Цена заказа, уплаченная std::map за то, что вставка/удаление/поиск (включая нахождение минимума/максимума) становится O(log N).

Если вы не возражаете против использования Boost, вы можете взглянуть на Boost.MultiIndex. Это позволяет вам получать доступ к вашим данным через несколько интерфейсов одновременно. Это чрезвычайно универсальная и высокопроизводительная библиотека, которую также можно использовать для структур данных кэша MRU (которые также сочетают в себе быстрый доступ и отслеживание порядка).

Ваш основной интерфейс std::unordered_map предоставляется индексом hashed_unique, где вы используете объект функции identity (предоставляемый Boost.MultiIndex). Ваш вторичный интерфейс будет имитировать std::set. Это позволяет найти минимальное/максимальное значение в O(1) времени как *begin() и *rbegin().

Вы можете сделать это, добавив индекс ordered_unique с определяемым пользователем функциональным объектом MyOrder для вычисления любого критерия, который вы хотите использовать для их упорядочения. Небольшой пример кода (исключая пространство имен boost:: везде)

using MyContainer = multi_index_container<
    Item,
    indexed_by<
        hashed_unique<identity<Item>>, // O(1) erasure/lookup, O(log N) insertion
        ordered_unique<MyOrder<Item>>  // track minimum/maximum in O(log N)
    >
>;

За кулисами Boost.MultiIndex реализует это примерно как std::set<Value> с std::unordered_map<Key, set<Value>::iterator>. Это означает, что и поиск, и стирание O(1). Стирание может быть O(1), потому что unordered_map::erase(value) возвращает итератор в set, а std::set<Value>::erase(iterator) равно O(1).

Однако количество вставок остается O(log N), потому что вы не можете избежать поиска ранга вновь вставленного значения в упорядоченной последовательности за меньшее время.

Это улучшение по сравнению с std::map для поиска/стирания стоит всего несколько указателей на элементное пространство.

Вы можете написать обертку. При этом вы получаете каждую вставку/удаление и можете сохранять минимальные/максимальные значения.

#pragma once

#include <unordered_map>

using std::unordered_map;

class my_unordered_map
{
public:
    void insert(int key, int value)
    {
        _map[key] = value;
        if (_max < value)
            _max = value;
        if (_min> value)
            _min = value;
    }
    int get(int key)
    {
        auto it = _map.find(key);
        if (it != _map.end())
            return it->second;
        return 0; // or some error handling here.
    }
    int getMin()
    {
        return _min;
    }
    int getMax()
    {
        return _max;
    }
    // more functionality here.
private:
    unordered_map<int, int> _map;
    int _min = 0;
    int _max = 0;
};