如果方法是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 声明为 mutable。这将允许其中的数据发生变化，即使您在 const 函数中也是如此。

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

更难的方法是两全其美。您的向量将保持不变，并且同一函数的第二个运行实际上 return 比第一个更快地得到答案。

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

// 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;
}

Answer 2

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

我们可以做得比仅使用 std::sort 更好一点。我们不需要为了找到中位数而对向量进行完全排序。我们可以使用 std::nth_element to find the middle element. Since the median of a vector with an even number of elements is the average of the middle two, we need to do a little more work to find the other middle element in that case. std::nth_element ensures that all elements preceding the middle are less than the middle. It doesn't guarantee their order beyond that so we need to use 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 3

const 方法是一种只能在它所属的 class 的 const 个实例上调用的方法。所以，如果你已经声明了一个 class Median 并在其上声明了一个 const 方法，那么 它只能用 const 的实例调用Medianclass。不可能影响另一个 class，比如 std::vector。

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

如果你需要对数组进行排序，那么你可以制作一个副本，或者更好的是，考虑使用指向数组元素的指针数组，然后根据指向的值对该数组进行排序到值，然后考虑该数组的中心元素。这样，您就不会触及原始实例，并且仍然可以维护该方法的 const 属性。

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

how to find the median of a vector if the method is const?

c++

sorting

algorithm

constants

median