Can you get a uniformly-random key-value pair from an std::map in sub-linear time?

Given an std::map<K,V> of size n, can you randomly get a key (and value) in the container, portably? Randomly here refers to key's position in the container. Let's say the distribution has to be only close to uniform.

My thinking was that standard library maps are often (always?) implemented as red-black trees, which are decently balanced. So locating an (almost-)uniformly random value could be done in log-time if you can access this underlying structure. It wouldn't be trivial but it could be done (idea: each node can estimate roughly how many child-nodes are left and how many are right of it).

In general one cannot access that information, so the obvious solution is to linearly iterate over it until you find the ith element for some uniformly-random chosen 0 <= i < n. However, as of C++17 there is also the rudimentary node interface that allows one to extract and re-insert nodes. But after some thought I don't see how this would be helpful.

Is there something I am overlooking or is this truly impossible in sub-linear time given the standardised interface of std::map?

---

Note: Obviously, if one wants to get more than, say, n / log n elements, shuffling a vector of map iterators is likely the best option.