質問: 中央値計算にstlコンテナーを使用する場合の正しいアプローチは何ですか? 1000000のランダムな数値のシーケンスから中央値を取得する必要があるとしましょう。何かを使用する場合but std::listの場合、中央値計算のためにシーケンスをソートする(組み込み)方法がありません。std::listを使用している場合、値をランダムにアクセスして、ソートされたシーケンスの中央(中央値)を取得することはできません。自分で並べ替えを実装して、たとえば、 std::vector、またはstd::listを使用し、std::list::iteratorを使用してfor-loop-walkで中央値にした方がよいでしょうか?後者はオーバーヘッドが少ないように見えますが、より醜く感じます。それとも私にとってもっと良い選択肢がありますか?
回答: このアルゴリズムは、stl nth_element(amortized 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; }