如果方法是const，如何找到向量的中位数？

Question

我创建了一个名为Collect的方法，它为向量添加了一堆值（如下所示）

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

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

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

}

所以我知道我首先需要对矢量进行排序以找到中位数。以下是我的尝试：

    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，所以对向量的值进行排序会改变向量，这在const函数中是不允许的。那么我应该为这种方法做些什么呢？

Answer 1

制作myVector的副本，对其进行排序，然后计算其中位数。

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

您可能没有考虑的另一件事是myVector是空的情况。找到空向量的中位数并没有任何意义。对于这个例子，我只是使用了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来查找中位数。你会得到中间元素。

Answer 2

const方法是一种只能在它所属的类的const实例上调用的方法。所以，如果你声明了一个类Median并且你声明了一个const方法，那么它只能用const类的Median实例调用。没有可能影响到不同的类别，比如std::vector。

无论如何，如果您决定从std::vector派生一个新类并考虑添加一个方法median来计算中位数，您最好将其声明为const。这样做的原因是你不需要修改数组来获得它的中位数（见下文）。

在您需要对数组进行排序的情况下，您可以复制，甚至更好地考虑使用指向数组元素的指针数组，然后根据指向的值的值对该数组进行排序，然后考虑该数组的核心元素。这样，您不会触及原始实例，仍然可以维护该方法的const属性。

Answer 3

你可以宣布你的myVector为mutable。这将允许数据在其中发生变化，即使您处于const函数中也是如此。

如果由于某种原因，这不是一个选项，您可以考虑使用一些数据类型来保持数据排序并将新数据插入正确的位置。然后，每次运行此函数时都不需要对其进行排序，但是会减慢插入速度。考虑更频繁发生的事情：插入或获得中位数。

---

更难的方法是拥有两全其美。你的向量将保持不变，同一函数的第二次运行实际上会比第一次更快地返回答案。

然后，您可以执行以下操作：

// Median.hpp
class Median
{
  std::vector<double> myVector;
  mutable double median;
  mutable bool medianCalculated;
// the rest is the same
};

// Median.cpp
double Median::calculate() const
{
  if(!medianCalculated)
  {
    std::vector<double> copyVector = myVector;
    std::sort(copyVector.begin(), copyVector.end();
    const auto m1 = copyVector.begin() + (copyVector.size() / 2);
    const auto m2 = copyVector.begin() + ((copyVector.size() + 1) / 2);
    median = (*m1 + m2) / 2; // m1==m2 for even sized vector m1+1==m2 for odd sized
    medianCalculated=true;
  }
  return median;  
}
void Median::Collect(double datum)
{
  myVector.push_back(datum);
  medianCalculated=false;
}