我有一个由'n'个元素组成的unordered_map。它有一些合格的元素。我想写一个函数，每次都随机挑选一个合格的元素。这能在下面的时间复杂度内实现吗？最好的情况是：O（1）平均情况：O（1）最差情况：时间复杂度O（n）
在C++中引用- retrieve random key元素为std：：map时，我想出了下面的解决办法。

#include <iostream>
#include <unordered_map>
#include <random>
using namespace std;
 
void select_random_best(const std::unordered_map<std::string, int>& umap, const int random_start)
{
  cout << "Selected random number " << random_start << endl; 
  auto it = umap.begin();
  std::advance(it, random_start);
  for(int i = 0; i < umap.size(); i++, it++) {
      if(it == umap.end())
        it = umap.begin();
    // Check if the selected element satisfies the eligibility criteria.
    // For the sake of simplicity, I am taking the following example.
    if(it->second % 3 == 0) {
        cout << it->first << ", " <<
            it->second << endl;
        return;
    }
    // Element not found continue searching
  }
}

int main()
{
  srand(time(0));
  unordered_map<string, int> umap;
 
  // inserting values by using [] operator
  umap["a"] = 6;
  umap["b"] = 3;
  umap["f"] = 9;
  umap["c"] = 2;
  umap["d"] = 1;
  umap["e"] = 3;
 
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution<> distrib(0, umap.size() - 1);
  const int random_start = distrib(gen);
            
  select_random_best(umap, distrib(gen));
  
  // another iteration         
  select_random_best(umap, distrib(gen));
  cout << "Full list :" << endl;
 
  // Traversing an unordered map
  for (auto x : umap)
    cout << x.first << ", " <<
            x.second << "\t";
  
}

如果在这里使用std::advance()会导致平均时间复杂度为O（1），有没有更好的方法？