Now that I understand Barius' method, I think it comes out cleanly ahead of SiCrane's.

CM

Conner McCloud: There's no way to do any useful caching. The set is effectively arbitrary each time I want to pick N items out of it.

Zahlman's explanation of Barius' method clears up my misinterpretation of the original suggestion, and a quick test seems to produce good results.

I'm a bit disheartened that an order N solution doesn't seem to exist, but I suppose that's asking a bit much (though feel free to suggest anything better than order M, anyone...).

Thanks all.

If your set's contents are fairly stable over time (i.e. you don't mind slow insertion/deletion), you might try using a sorted_vector instead, and then just invoking std::random_sample (if you have it) on the result. Actually, it appears you could invoke std::random_sample directly on the set. But then, given the SGI description of the computational complexity of std::random_sample, it looks like it basically implements the algorithm Barius cited (being described as single-pass, order M). But that saves you from writing it at least ;) (Again, if you have it ^^; )

(Man, I really hope C++0x adds SGI's extensions to the library; some of them - in particular, copy_n - would seriously relieve some of my annoyances at least as well as some of the Boost features they're considering.)