C++ calculate median with reference

Question

I try to calculate the median of a vector called median:

std::nth_element(median.begin(), median.begin() + median.size() / 2, median.end());     
medianVal = median[median.size() / 2];  
cout << "The median is " << medianVal << endl;

This works fine. But I need to get the position of the median value in its original vector. How can I do this very fast?

Answer 1

I am assuming you do not want to reorder the original container. If wrong, there are easier ways.

nth_element takes a comparator.

So first create a vector of iterators into the original container, then write a comparator that takes 2 iterators, deferences them, amd compares the result.

template<class C>
auto median(C const& c){
  using std::begin; using std::end;
  auto start = begin(c);
  auto finish = end(c);
  using iterator = decltype(start);
  std::vector<iterator> working;
  for(auto it = start; it != finish; ++it)
    working.push_back(it);
  if (working.empty())
      return start;
  std::nth_element(
      begin(working), begin(working) + working.size() / 2, end(working),
      [](iterator lhs, iterator rhs){
          return *lhs < *rhs;
      }
  );
  return *(begin(working) + working.size() / 2);
}

This does rely on some C++14 (auto return type deduction), but every major compiler (except possibly icc?) has support for it now.

It is flexible enough to work on even C style arrays, and I think it even works with sentinels.

Demo