C++ 使用 STL 容器进行中值计算时，正确的方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1719070/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the right approach when using STL container for median calculation?
提问by sharkin
Let's say I need to retrieve the median from a sequence of 1000000 random numeric values.
假设我需要从 1000000 个随机数值序列中检索中位数。
If using anything butstd::list, I have no (built-in) way to sort sequence for median calculation.
如果使用任何东西，但是std::list，我没有（内置）的方式，为中值计算排序顺序。
If using std::list, I can't randomly access values to retrieve middle (median) of sorted sequence.
如果使用std::list，我不能随机访问值来检索排序序列的中间（中值）。
Is it better to implement sorting myself and go with e.g. std::vector, or is it better to use std::listand use std::list::iteratorto for-loop-walk to the median value? The latter seems less overheadish, but also feels more ugly..
自己实现排序并使用 egstd::vector更好，还是std::list使用std::list::iteratorfor-loop-walk 到中值更好？后者看起来不那么开销，但也感觉更丑陋..
Or are there more and better alternatives for me?
或者对我来说有更多更好的选择吗？
回答by Mike Seymour
Any random-access container (like std::vector) can be sorted with the standard std::sortalgorithm, available in the <algorithm>header.
任何随机访问容器（如std::vector）都可以使用标头中std::sort可用的标准算法进行排序<algorithm>。
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:
为了找到中位数，使用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];
}
回答by Eponymous
The median is more complex than Mike Seymour's answer. The median differs depending on whether there are an even or an odd number of items in the sample. If there are an even number of items, the median is the average of the middle two items. This means that the median of a list of integers can be a fraction. Finally, the median of an empty list is undefined. Here is code that passes my basic test cases:
中位数比 Mike Seymour 的答案更复杂。中位数的不同取决于样本中的项目数是偶数还是奇数。如果有偶数个项目，中位数是中间两个项目的平均值。这意味着整数列表的中位数可以是分数。最后，空列表的中位数是不确定的。这是通过我的基本测试用例的代码：
///Represents the exception for taking the median of an empty list
class median_of_empty_list_exception:public std::exception{
virtual const char* what() const throw() {
return "Attempt to take the median of an empty list of numbers. "
"The median of an empty list is undefined.";
}
};
///Return the median of a sequence of numbers defined by the random
///access iterators begin and end. The sequence must not be empty
///(median is undefined for an empty set).
///
///The numbers must be convertible to double.
template<class RandAccessIter>
double median(RandAccessIter begin, RandAccessIter end)
throw(median_of_empty_list_exception){
if(begin == end){ throw median_of_empty_list_exception(); }
std::size_t size = end - begin;
std::size_t middleIdx = size/2;
RandAccessIter target = begin + middleIdx;
std::nth_element(begin, target, end);
if(size % 2 != 0){ //Odd number of elements
return *target;
}else{ //Even number of elements
double a = *target;
RandAccessIter targetNeighbor= target-1;
std::nth_element(begin, targetNeighbor, end);
return (a+*targetNeighbor)/2.0;
}
}
回答by Alec Jacobson
Here's a more complete version of Mike Seymour's answer:
这是 Mike Seymour 答案的更完整版本：
// Could use pass by copy to avoid changing vector
double median(std::vector<int> &v)
{
size_t n = v.size() / 2;
std::nth_element(v.begin(), v.begin()+n, v.end());
int vn = v[n];
if(v.size()%2 == 1)
{
return vn;
}else
{
std::nth_element(v.begin(), v.begin()+n-1, v.end());
return 0.5*(vn+v[n-1]);
}
}
It handles odd- or even-length input.
它处理奇数或偶数长度的输入。
回答by Matthew Fioravante
This algorithm handles both even and odd sized inputs efficiently using the STL nth_element (amortized O(N)) algorithm and the max_element algorithm (O(n)). Note that nth_element has another guaranteed side effect, namely that all of the elements before nare all guaranteed to be less than v[n], just not necessarily sorted.
该算法使用 STL nth_element（摊销 O(N)）算法和 max_element 算法 (O(n)）有效地处理偶数和奇数大小的输入。请注意， nth_element 有另一个保证的副作用，即之前n的所有元素都保证小于v[n]，只是不一定要排序。
//post-condition: After returning, the elements in v may be reordered and the resulting order is implementation defined.
double median(vector<double> &v)
{
if(v.empty()) {
return 0.0;
}
auto n = v.size() / 2;
nth_element(v.begin(), v.begin()+n, v.end());
auto med = v[n];
if(!(v.size() & 1)) { //If the set size is even
auto max_it = max_element(v.begin(), v.begin()+n);
med = (*max_it + med) / 2.0;
}
return med;
}
回答by Croc Dialer
putting together all the insights from this thread I ended up having this routine. it works with any stl-container or any class providing input iterators and handles odd- and even-sized containers. It also does its work on a copy of the container, to not modify the original content.
把这个线程的所有见解放在一起，我最终有了这个例程。它适用于任何 stl 容器或任何提供输入迭代器的类，并处理奇数和偶数大小的容器。它还对容器的副本进行处理，而不是修改原始内容。
template <typename T = double, typename C>
inline const T median(const C &the_container)
{
std::vector<T> tmp_array(std::begin(the_container),
std::end(the_container));
size_t n = tmp_array.size() / 2;
std::nth_element(tmp_array.begin(), tmp_array.begin() + n, tmp_array.end());
if(tmp_array.size() % 2){ return tmp_array[n]; }
else
{
// even sized vector -> average the two middle values
auto max_it = std::max_element(tmp_array.begin(), tmp_array.begin() + n);
return (*max_it + tmp_array[n]) / 2.0;
}
}
回答by Charles Salvia
You can sort an std::vectorusing the library function std::sort.
您可以std::vector使用库函数对 an进行排序std::sort。
std::vector<int> vec;
// ... fill vector with stuff
std::sort(vec.begin(), vec.end());
回答by ephemient
There exists a linear-time selection algorithm. The below code only works when the container has a random-access iterator, but it can be modified to work without — you'll just have to be a bit more careful to avoid shortcuts like end - beginand iter + n.
存在线性时间选择算法。下面的代码仅在容器具有随机访问迭代器时才有效，但可以对其进行修改以使其工作 - 您只需要更加小心，避免使用end - begin和 之类的快捷方式iter + n。
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <vector>
template<class A, class C = std::less<typename A::value_type> >
class LinearTimeSelect {
public:
LinearTimeSelect(const A &things) : things(things) {}
typename A::value_type nth(int n) {
return nth(n, things.begin(), things.end());
}
private:
static typename A::value_type nth(int n,
typename A::iterator begin, typename A::iterator end) {
int size = end - begin;
if (size <= 5) {
std::sort(begin, end, C());
return begin[n];
}
typename A::iterator walk(begin), skip(begin);
#ifdef RANDOM // randomized algorithm, average linear-time
typename A::value_type pivot = begin[std::rand() % size];
#else // guaranteed linear-time, but usually slower in practice
while (end - skip >= 5) {
std::sort(skip, skip + 5);
std::iter_swap(walk++, skip + 2);
skip += 5;
}
while (skip != end) std::iter_swap(walk++, skip++);
typename A::value_type pivot = nth((walk - begin) / 2, begin, walk);
#endif
for (walk = skip = begin, size = 0; skip != end; ++skip)
if (C()(*skip, pivot)) std::iter_swap(walk++, skip), ++size;
if (size <= n) return nth(n - size, walk, end);
else return nth(n, begin, walk);
}
A things;
};
int main(int argc, char **argv) {
std::vector<int> seq;
{
int i = 32;
std::istringstream(argc > 1 ? argv[1] : "") >> i;
while (i--) seq.push_back(i);
}
std::random_shuffle(seq.begin(), seq.end());
std::cout << "unordered: ";
for (std::vector<int>::iterator i = seq.begin(); i != seq.end(); ++i)
std::cout << *i << " ";
LinearTimeSelect<std::vector<int> > alg(seq);
std::cout << std::endl << "linear-time medians: "
<< alg.nth((seq.size()-1) / 2) << ", " << alg.nth(seq.size() / 2);
std::sort(seq.begin(), seq.end());
std::cout << std::endl << "medians by sorting: "
<< seq[(seq.size()-1) / 2] << ", " << seq[seq.size() / 2] << std::endl;
return 0;
}
回答by Lorah Attkins
Here is an answer that considers the suggestion by @MatthieuM. ie does not modify the input vector. It uses a single partial sort (on a vector of indices) for both ranges of even and odd cardinality, while empty ranges are handled with exceptions thrown by a vector's atmethod:
这是一个考虑了@MatthieuM 建议的答案。即不修改输入向量。它对偶数和奇数基数范围使用单个部分排序（在索引向量上），而空范围使用向量at方法抛出的异常进行处理：
double median(vector<int> const& v)
{
bool isEven = !(v.size() % 2);
size_t n = v.size() / 2;
vector<size_t> vi(v.size());
iota(vi.begin(), vi.end(), 0);
partial_sort(begin(vi), vi.begin() + n + 1, end(vi),
[&](size_t lhs, size_t rhs) { return v[lhs] < v[rhs]; });
return isEven ? 0.5 * (v[vi.at(n-1)] + v[vi.at(n)]) : v[vi.at(n)];
}
