使用STL容器进行中值计算时正确的方法是什么？

小编典典

algorithm

假设我需要从1000000个随机数值序列中检索中位数。

如果使用任何东西 ，但是 std::list，我没有（内置）的方式，为中值计算排序顺序。

如果使用std::list，则无法随机访问值以检索排序序列的中间（中位数）。

它是更好地实现自己的排序，并与如去std::vector，或者是它更好地使用std::list和利用std::list::iterator，为环步行至中值？后者似乎开销较小，但也感觉较丑。

还是我有更多更好的选择？

阅读 235

2020-07-28

共1个答案

小编典典

std::vector可以std::sort使用<algorithm>标头中提供的标准算法对任何随机访问容器（如）进行排序。

为了找到中位数，使用起来会更快std::nth_element。这足以将一个选定的元素放置在正确的位置，但是并不能完全对容器进行排序。因此，您可以找到这样的中位数：

int median(vector<int> &v)
{
    size_t n = v.size() / 2;
    nth_element(v.begin(), v.begin()+n, v.end());
    return v[n];
}

2020-07-28