c++ - 如何从std::set绘制n个元素的样本

Question

我具有以下功能，可以从std::set中选择一个随机元素:

int pick_random(const std::set<int>& vertex_set) {
  std::uniform_int_distribution<std::set<int>::size_type> dist(0, vertex_set.size() - 1);
  const std::set<int>::size_type rand_idx = dist(mt);
  std::set<int>::const_iterator it = vertex_set.begin();
  for (std::set<int>::size_type i = 0; i < rand_idx; i++) {
    it++;
  }
  return *it;
}

但是，我不知道如何从集合中正确绘制 n元素样本。使用C++ 17编译器，我可以使用 std::sample函数，但是这里不是这种情况，因为我有C++ 11编译器。

Answer 1

如果您不介意副本，一个简单的方法是从std::vector创建一个std::set，使用 std::shuffle 对其进行混洗，然后采用第一个n元素:

std::vector<int> pick_random_n(const std::set<int>& vertex_set, std::size_t n) {
    std::vector<int> vec(std::begin(vertex_set), std::end(vertex_set));
    std::shuffle(std::begin(vec), std::end(vec), mt);
    vec.resize(std::min(n, vertex_set.size()));
    return vec;
}

如果您不想要多余的副本，可以查看 std::sample 的实现，例如从 libc++并为 std::set实现自己的实现:

std::vector<int> pick_random_n(const std::set<int>& vertex_set, std::size_t n) {
    auto unsampled_sz = vertex_set.size();
    auto first = std::begin(vertex_set);

    std::vector<int> vec;
    vec.reserve(std::min(n, unsampled_sz));

    for (n = std::min(n, unsampled_sz); n != 0; ++first) {
        auto r =
            std::uniform_int_distribution<std::size_t>(0, --unsampled_sz)(mt);
        if (r < n) {
            vec.push_back(*first);
            --n;
        }
    }
    return vec;
}