Efficient/Elegant way to select random entry from Vector Matching Criteria?

[Aaron Vienneau]

Hi,

Given a vector

std::vector<std::pair<std::string, Gender>> myVector = {
{"Aaron", Male},
{"Anna", Female},
{"Bryce", Male},
{"Lynn", Female},
{"Abbie", Female}
};

is there an elegant and efficient way to select a random entry in myVector that matches a certain criteria? Specifically, I'd like to get a random female name from that vector.

EDIT: Currently, the only way I can think of is to randomly select an entry, see if it matches the critiera, and if it doesn't, select another entry and try again, but that is DEFINITELY not efficient, in that, it could bounce back and forth between entries hundreds of times before getting it right.

[jonnin]

well, maybe :)

if the distribution of names is nearly 50%, checking a few until you get one may actually be the most efficient. Odds are in your favor, you have a 50-50 chance and constantly rolling the wrong type is statistically very unlikely.


if they distribution is not even close to 50-50, say 80/20 type split, you should sort them, find the crossover spot, and pick a record in the range either zero-to-split or split-to-end.

you could also do something smarter like make the vector very large and have only even elements be male, or something like that, a pseudo-hash type approach, and a way to have a 'nothing here' entry. Or just have 2 vectors..

for a much, much more complicated problem, say you had 5 criteria, you can build a temporary list of the indices that match the criteria, and pick from those at random, then go to that index back in the original structure. This is very useful if you need to choose many randoms with the same criteria.