What is the best way traversing an unordered_map with a starting from a random element in C++?

Question

I have an unordered_map of 'n' elements. It has a some eligible elements. I want to write a function such that each time, a random eligible element is picked. Can this be achieved in the following time complexity? Best case: O(1) Avg case: O(1) Worst case: O(n)

Referring - retrieve random key element for std::map in c++, I have come up with the following solution.

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

Can someone suggest if the use of std::advance() here would lead to the avg case time comlexity of O(1)? Or is there a better way of doing this?

Answer 1

std::unordered_map has forward iterators, which do not allow random access. Refer to iterator on the documentation page of the container.

Assuming all elements are eligible, std::advance() will go through size/2 elements on average. Because you only accept eligible elements, you will go through more than that. If you know the probability of the eligibility, you can estimate the average elements searched.

To achieve O(1) in the std::advance() step, you must use a data type with random access iterators, such as std::vector. However, the next step does not have constant compexity. In the worst case, you will go through all ineligible elements (not considering the possibility of an infinite loop if there are no eligible ones). So this approach is still O(n) as whole.

For the best performance, you need two lists: std::vector with only eligible elements, used for finding a random element, and std::unordered_map for other things.