介绍尺寸等于set的数组。使数组元素保存集合中每个元素的地址。生成由数组/集合大小限定的随机整数 R ，在由 R 索引的数组元素中选择地址并取消引用set的元素。

This question with an added constraint.

I'm willing to allow not-uniform selection as long as it's not to lop sided.

Given that "sets are typically implemented as binary search trees" and I expect they will contain some kind of depth or size information for balancing, I would expect you could do some sort of weighted random walk of the tree. However I don't know of any remotely portable way to do that.

Edit: The constraint is NOT for the amortized time.

Introduce array with size equal to set. Make array elements hold addresses of every element in set. Generate random integer R bounded by array/set size, pick address in array's element indexed by R and dereference it to obtain set's element.