iterator over non-existing sequence

I have K objects (K is small, e.g. 2 or 5) and I need to iterate over them N times in random order where N may be large. I need to iterate in a foreach loop and for this I should provide an iterator.

So far I created a std::vector of my K objects copied accordingly, so the size of vector is N and now I use begin() and end() provided by that vector. I use std::shuffle() to randomize the vector and this takes up to 20% of running time. I think it would be better (and more elegant, anyways) to write a custom iterator that returns one of my object in random order without creating the helping vector of size N. But how to do this?