c++ - 如果方法是const，如何找到 vector 的中值？

Question

我创建了一个名为 Collect 的方法，它将一堆值添加到 vector 中(如下所示)

void Median::Collect(double datum)
{
  myVector.push_back(datum);
}

我需要创建一个方法来计算我在上述方法中收集到的 vector 中的所有值的中位数。函数定义写在下面

/* Calculates the median of the data (datum) from the Collect method.
 */
 double Median::Calculate() const
{

}

所以我知道我首先需要对 vector 进行排序才能找到中位数。以下是我的尝试:

    double Median::Calculate() const
  {
    std::sort(myVector.begin(), myVector.end());
    double median;
    if (myVector.size() % 2 == 0)
    {// even
        median = (myVector[myVector.size() / 2 - 1] + myVector[myVector.size() / 2]) / 2;
    }
    else
    {// odd
        median = myVector[myVector.size() / 2];
    }
    return median;
  }

但我意识到这不是编译，因为该方法是 const，因此对 vector 的值进行排序会改变 vector ，这在 const 函数中是不允许的。那么我应该为这个方法做什么？

Answer 1

复制myVector，对其进行排序，然后计算其中值。

我们可以比仅仅使用 std::sort 做得更好。我们不需要为了找到中位数而对 vector 进行完全排序。我们可以使用 std::nth_element找到中间元素。由于具有偶数个元素的 vector 的中值是中间两个元素的平均值，因此在这种情况下我们需要做更多的工作才能找到另一个中间元素。 std::nth_element 确保中间之前的所有元素都小于中间。它不能保证超出此范围的顺序，因此我们需要使用 std::max_element找到中间元素之前的最大元素。

您可能没有考虑过的另一件事是 myVector 为空的情况。找到一个空 vector 的中位数并没有任何意义。对于这个例子，我只是使用了一个 assert 但你可能想抛出一个异常或其他东西。

double Median::calculate() const {
  assert(!myVector.empty());
  std::vector<double> myVectorCopy = myVector;
  const auto middleItr = myVectorCopy.begin() + myVectorCopy.size() / 2;
  std::nth_element(myVectorCopy.begin(), middleItr, myVectorCopy.end());
  if (myVectorCopy.size() % 2 == 0) {
    const auto leftMiddleItr = std::max_element(myVectorCopy.begin(), middleItr);
    return (*leftMiddleItr + *middleItr) / 2.0;
  } else {
    return *middleItr;
  }
}

另一种选择是使用不同的容器来确保元素始终排序。您可以考虑使用 std::set .当您插入 std::set 时，该集合保持排序，因此不必使用 std::sort、std::nth_element 或 std::max_element 找到中位数。你会得到中间的元素。