C++根据引用计算中位数

Question

我尝试计算一个名为 median 的 vector 的中位数:

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

这很好用。但我需要得到中值在其原始 vector 中的位置。我怎样才能非常快地做到这一点？

Answer 1

我假设您不想重新订购原始容器。如果错误，还有更简单的方法。

nth_element 采用比较器。

因此，首先在原始容器中创建一个迭代器 vector ，然后编写一个接受 2 个迭代器的比较器，对它们进行引用，然后比较结果。

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

这确实依赖于一些 C++14(自动返回类型推导)，但每个主要编译器(可能除了 icc？)现在都支持它。

它足够灵活，甚至可以处理 C 风格的数组，我认为它甚至可以处理哨兵。

Demo