как найти медиану вектора, если метод 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;
}