C++ Randomly select non-empty element of std::vector

I am given a large vector that itself contains vectors of a specific data type e.g. std::vector<std::vector<double> > foo. I am trying to retrieve a random element foo[idx] from foo such that foo[idx] is non-empty or respectively foo[idx].empty() == false.

My naive guess would be to select random elements from foo until my constraint foo[idx].empty() == false is fulfilled.

However it is very likely the case that foo is very sparsely filled with non-empty vectors. Hence, my approach would quite likely be devastatingly slow.

Are there better approaches or should i think of a completely different data structure?