Этот вопрос с добавленным ограничением.
Я готов разрешить неравномерный отбор, если он не будет терпеть неудачу.
Учитывая, что " наборы обычно реализуются как деревья двоичного поиска", и я ожидаю, что они будут содержать информацию о глубине или размере для балансировки, Я бы ожидал, что вы сможете сделать какое-то взвешенное случайное блуждание дерева. Однако я не знаю ни одного отдаленно портативного способа сделать это.
Изменить: ограничение не является допустимым временем.
Ввести массив с размером, равным заданному. Элементы массива содержат адреса каждого элемента в наборе. Генерируйте случайное целое число R, ограниченное размером массива/набора, выберите адрес в элементе массива, индексированный с помощью R, и разыщите его для получения заданного элемента.
Я не вижу, как это сделать только с std::set, поэтому вам, вероятно, нужна другая структура данных. Как сказал Виктор Сорокин, вы можете комбинировать набор с вектором. Вместо set<T> используйте map<T, size_t>, плюс vector< map<T, size_t>::iterator >. Значение для каждого ключа является индексом в векторе, и каждый элемент вектора указывает на элемент карты. Элементы вектора не имеют особого порядка. Когда вы добавляете элемент, поместите его в конец вектора. Когда вы удаляете элемент, а не последний в векторе, переместите последний элемент в позицию удаленного элемента.
Если вы знаете распределение элементов в наборе, вы можете случайно выбрать ключ (с тем же распределением) и использовать std::set::lower_bound. Это много, если хотя.
int main() {
std::set<float> container;
for(float i=0; i<100; i += .01)
container.insert(i);
//evenish distribution of 10000 floats between 0 and 100.
float key = std::rand() *10000f / RAND_MAX; //not random, sue me
std::set<float>::iterator iter = container.lower_bound(key); //log(n)
std::cout << *iter;
return 0;
}
Вы можете сделать случайно упорядоченную копию карты с помощью этого конструктора
template <class InputIterator>
set(InputIterator f, InputIterator l,
const key_compare& comp)
.. и передача компаратора, который сравнивает хэши ключей (или некоторую другую детерминированную функцию расширения). Затем возьмите "самые маленькие" ключи в соответствии с этой новой картой.
Вы можете построить карту один раз и амортизировать затраты на несколько запросов для "случайного" элемента.
Для std::unordered_set<int> s:
1) возьмем случайный R в min(s)..max(s)
2) если R в s: return R
3)
newIter = s.insert(R).first;
newIter++;
if (newIter == s.end()) {
newIter = s.begin();
}
auto result = *newIter;
s.erase(R);
return result;
Для упорядоченного множества (std:: set) вероятность будет зависеть от расстояния между элементами. unordered_set рандомизируется хешем.
Надеюсь, это поможет.
Преобразование PS std::set<V> в std::set<std::pair<int, V>> (где первый элемент в паре является хэшем второго) делает этот метод подходящим для любого хэшируемого V.