使用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 :: 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屋!