Std :: unordered_map - how to "track" the max / min key at any time

Question

I have one std::unordered_map<int, int>. I do not want to use other structures, such as a tree or something else, to cause latent requirements. But at any moment I need to know the current key max and min. How can i do this? The distribution is NOT uniform, instead max and min are often removed and inserted. So I need something smarter than "just scan the entire map for a new max / min while deleting the current max / min."

I do not want to use any other structures. I want to use std::unordered_map!

upd, in accordance with the answer, created the following structure:

struct OrderBookItem {
    int64_t price;
    int32_t lots;
};

typedef multi_index_container
    <OrderBookItem, indexed_by<

    hashed_unique<
    BOOST_MULTI_INDEX_MEMBER(OrderBookItem,int64_t,price)
    >,

    ordered_unique<
    BOOST_MULTI_INDEX_MEMBER(OrderBookItem,int64_t,price),
    std::greater<int64_t>
    >

    >> OrderBookContainer;

Answer 1

: 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) is O(1).

O(log N), .

std::map / .

Answer 2

. / min/max.

#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;
};