c++ - 有没有办法将 nth_element 与数据拷贝一起执行？

Question

我想用 C++ 计算 float 组的中值:

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++ float 组。

我正在使用 std::nth_element 但想知道是否有像 nth_element 这样的工具可以处理 const 数据？现在，我正在制作拷贝，然后在丢弃拷贝之前执行 nth_element。如果 const 数据没有类似 nth_element 的东西，是否有更有效的方法使用复制步骤来计​​算信息，从而避免潜在的额外 O(n)环形？也许性能影响可以忽略不计？我的数组大小可能约为 20 亿。

Answer 1

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

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