有没有办法将nth_element与数据副本一起完成?

Question

我希望从C++的浮点数组中计算中值：

float Median( FloatArray const * constFloatArray )
{
FloatArray    scratch = FloatArray( *constFloatArray );
int64_t const size    = scratch.GetWidth() * scratch.GetHeight();
int64_t const mid     = size / 2;
std::nth_element( scratch.begin(), scratch.begin() + mid, scratch.end() );
return scratch[ mid ];
}

FloatArray 包含一个常规的 C++ 浮点数组。

我正在使用std::nth_element但想知道是否有像nth_element这样的工具可以使用const数据？ 现在，我正在制作一份副本，然后在扔掉副本之前做nth_element。 如果const数据没有类似nth_element的东西，是否有更有效的方法使用复制步骤来计算信息，从而避免潜在的额外 O(n( 循环？ 也许性能影响可以忽略不计？ 我的阵列大小可能在 20 亿左右。

Answer 1

我不确定它是否会更有效率，但您可以使用std::partial_sort_copy节省一半的复制。 我们可以使用std::partial_sort_copy仅将一半的数据复制到一个新数组中，它会在这样做时将其排序到该数组中。 然后，您需要做的就是获取奇数个元素的最后一个元素，或者偶数个元素的最后两个元素的平均值。 使用看起来像

int main() 
{
std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3, 10};
std::vector<int> r(v.size() / 2 + 1);
std::partial_sort_copy(v.begin(), v.end(), r.begin(), r.end());
if (r.size() % 2)
std::cout << r.back();
else
std::cout << (r[r.size() - 1] + r[r.size() - 2]) / 2.0;
}