如何从 C++ 向量中获取 2 个随机（不同）元素

我想从 std::vector 中获取 2 个随机不同的元素。我怎样才能做到这一点：

• 它很快（在我的算法中已经完成了数千次）
• 它是优雅的
• 元素选择确实是均匀分布的

为了优雅和简单：

void Choose (const int size, int &first, int &second)
{
  // pick a random element
  first = rand () * size / MAX_RAND;
  // pick a random element from what's left (there is one fewer to choose from)...
  second = rand () * (size - 1) / MAX_RAND;
  // ...and adjust second choice to take into account the first choice
  if (second >= first)
  {
     ++second;
  }
}

使用第一个和第二个来索引向量。

对于均匀性来说，这是非常棘手的，因为当大小接近 RAND_MAX 时，将会出现向较低值的偏差，并且如果大小超过 RAND_MAX ，则将存在永远不会被选择的元素。克服这个问题的一种解决方案是使用二分搜索：

int GetRand (int size)
{
  int lower = 0, upper = size;
  do
  {
    int mid = (lower + upper) / 2;

    if (rand () > RAND_MAX / 2) // not a great test, perhaps use parity of rand ()?
    {
       lower = mid;
    }
    else
    {
       upper = mid;
    }
  } while (upper != lower); // this is just to show the idea,
                            // need to cope with lower == mid and lower != upper
                            // and all the other edge conditions

  return lower;
}