使用STL容器进行中值计算时，正确的方法是什么？ [英] What is the right approach when using STL container for median calculation?

问题描述

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

如果使用任何但 STL :: list ，我没有（内置）的方式排序序列中值计算。

如果使用STL :: list，我不能随机访问值来检索中间（中位数）的排序序列。

它是更好地实现排序自己，去与eg STL :: vector，还是最好使用STL :: list并使用STL :: list :: iterator来循环遍历中值？

还是有更多更好的替代品吗？

std :: vector ）可以使用标准

为了找到中值，可以更快地使用 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]; 
} 
  

Let's say I need to retrieve the median from a sequence of 1000000 random numeric values.

If using anything but STL::list, I have no (built-in) way to sort sequence for median calculation.

If using STL::list, I can't randomly access values to retrieve middle (median) of sorted sequence.

Is it better to implement sorting myself and go with e.g. STL::vector, or is it better to use STL::list and use STL::list::iterator to for-loop-walk to the median value? The latter seems less overheadish, but also feels more ugly..

Or are there more and better alternatives for me?

解决方案

Any random-access container (like std::vector) can be sorted with the standard std::sort algorithm, available in the <algorithm> header.

For finding the median, it would be quicker to use std::nth_element; this does enough of a sort to put one chosen element in the correct position, but doesn't completely sort the container. So you could find the median like this:

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

这篇关于使用STL容器进行中值计算时，正确的方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！