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

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

Make a copy of myVector, sort it and then calculate the median of that.

We can do a little better than just using std::sort. We don't need to sort the vector completely in order to find the median. We can use 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 to find the largest element preceding the middle element.

Another thing that you may not have considered is the case where myVector is empty. Finding the median of an empty vector doesn't really make any sense. For this example, I just used an assert but you might want to throw an exception or something.

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

Another option is to use a different container to ensure that elements are always sorted. You might consider using std::set. When you insert into an std::set, the set remains sorted so don't have to use std::sort, std::nth_element or std::max_element to find the median. You would get the middle element.