Random iterator from a range with a predicate

I have a container, and I'd like to choose an iterator that satisfies a predicate at random. If it helps to be specific, the container is a map.

Naively, I would say this:

std::count_if to get the number of elements in the range.

Choose a random number btwn 0 and num_elements-1.

Create a lambda to make a stateful predicate that counts up to the random number and only returns true then.

std::find_if with the lambda.

Will this work, and is there a better way? Alternatively, I could use count instead of count_if and regenerate the number if it fails the predicate. Could be useful if the predicate is mostly true I suppose, but wouldn't work well for my purposes.