Ответ 1

Вы можете использовать метод std::advance.

#include <set>
#include <algorithm>

int main() {
  using namespace std;
  // generate a set...
  set<int> s;
  for( int i = 0; i != 10; ++i ) s.insert(i);
  auto r = rand() % s.size(); // not _really_ random
  auto n = *select_random(s, r);
}

куда

template<typename S>
auto select_random(const S &s, size_t n) {
  auto it = std::begin(s);
  // 'advance' the iterator n times
  std::advance(it,n);
  return it;
}

Ответ 2

Если случайный доступ важен, и вы можете жить с O (N) средним усилием для вставки, тогда обходной путь, приведенный в в этой статье может быть удобно.

Основная идея заключается в использовании отсортированного вектора, а затем для поиска функции std::lower_bound. Таким образом, поиск выполняет O (log N) так же, как и в обычном наборе. Кроме того, (случайная) вставка принимает O (N), так как все следующие элементы должны быть сдвинуты точно так же, как в нормальном векторе (и, возможно, выполняется перераспределение). Однако вставка на задней панели является постоянной (за исключением перераспределения. Это можно избежать, позвонив reserve() с достаточно большим объемом памяти).

Наконец, главный вопрос: случайный доступ - O (1). Просто нарисуйте случайное число i из равномерного распределения в [0, V.size()-1] и верните соответствующий элемент V[i].

Вот основа кода из статьи, которая реализует этот отсортированный вектор. Расширьте его по мере необходимости:

template <class T, class Compare = std::less<T> >
struct sorted_vector {
 using std::vector;
 using std::lower_bound;
 vector<T> V;
 Compare cmp; 
 typedef typename vector<T>::iterator iterator;
 typedef typename vector<T>::const_iterator const_iterator;
 iterator begin() { return V.begin(); }
 iterator end() { return V.end(); }
 const_iterator begin() const { return V.begin(); }
 const_iterator end() const { return V.end(); }

 //...if needed, implement more by yourself

 sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {}
 template <class InputIterator>
 sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare())
 : V(first, last), cmp(c)
 {
 std::sort(begin(), end(), cmp);
 }

 //...

 iterator insert(const T& t) {
     iterator i = lower_bound(begin(), end(), t, cmp);
     if (i == end() || cmp(t, *i))
        V.insert(i, t);
      return i;
 }
 const_iterator find(const T& t) const {
     const_iterator i = lower_bound(begin(), end(), t, cmp);
      return i == end() || cmp(t, *i) ? end() : i;
 }
};

Для более сложной реализации вы можете также рассмотреть эту страницу.

EDIT: или даже лучше, используйте boost::container::flat_set, который реализует набор, используя вышеприведенную идею, т.е. как отсортированный вектор.

Ответ 3

Первое решение: O (log n) во времени / O (1) в пространстве (неравномерно!)

Предполагаемый в комментарии выше, это можно сделать в O (log (n)) (vs O (n) для std::advance) без вектора (используя O (n) больше пространства), используя метод я описать здесь.

По существу, вы:

• проверить, является ли набор пустым (если есть, нет надежды)
• генерирует случайное значение
• если он уже вернулся, добавьте его
• получить один итератор it на нем
• получить случайный элемент как *(it++) или *(set.begin()), если it в конце
• верните его не перед удалением элемента, который вы вставили.

n.b: Как указал Аарон, элемент не выбирается равномерно случайным образом. Вам нужно построить случайный элемент с тем же распределением, что и элементы в наборе, чтобы приблизиться к равномерному опросу.

Второе решение: O (1) во времени / O (n) в пространстве (равномерное)

davidhigh уже дал решение с вектором, но есть проблема, потому что, когда вы набираете элемент своего стека, вам придется выполнять линейный поиск в O (n), или вы можете перестраивать свой вектор каждый раз, когда хотите получить случайный элемент, но это также O (n).

Чтобы избежать этой проблемы и сохраните вставку/удаление в O (log n), вы можете сохранить std::unordered_set и использовать аналогичный метод для первого решения для получения случайного элемента в O (1).

p.s: Если ваши элементы большие, вы можете использовать неупорядоченный набор указателей (с измененным хэшером), чтобы освободить некоторую память.

Ответ 4

int GetSample(const std::set<int>& s) {
  double r = rand() % s.size();
  std::set<int>::iterator it = s.begin();
  for (; r != 0; r--) it++;
  return *it;
}

будет одним из способов сделать это, хотя и не очень,

Ответ 5

С++ 17 std::sample

Это будет удобный, хотя и не очень эффективный (O (n)) метод:

#include <algorithm>
#include <iostream>
#include <random>
#include <set>
#include <vector>

int main() {
    std::set<int> in{1, 2, 3, 5, 7};
    std::vector<int> out;
    std::sample(in.begin(), in.end(), std::back_inserter(out),
                3, std::mt19937{std::random_device{}()});
    for (auto i : out)
        std::cout << i << std::endl;
}

Но я думаю, что для эффективности вам просто нужно скопировать в другой тип структуры: Как выбрать случайный элемент в std:: set меньше времени O (n)?