从向量中提取最小值、最大值和中值的最有效方法是什么

Question

给定一个 vector<T> vec{...} 假设 T 是其中一种数字类型，提取其最小值、最大值和中值的最佳方法是什么？我知道 std::nth_element as well as std::minmax_element 但如果一个接一个地调用它们，它们似乎会做多余的工作。

到目前为止，我想出的最好的主意就是连续调用 std::nth_element 3 次。不过这还是需要3N次比较吧？有什么方法可以重用之前迭代中完成的部分排序吗？

Answer 1

使用std::nth_element进行分区，得到中位数，然后std::min_element在左半部分，std::max_element在右半部分。

如果您需要它比这更快，那么根据 std::nth_element 推出您自己的版本。

Answer 2

另一种选择是为 std::nth_element 指定自定义比较，它会捕获最小值和最大值。它最终可能会进行更多的比较和分支，因此在某些特定硬件上这可能会更慢，这可能取决于缓存了多少数据等，所以 - 一如既往 - 如果你有理由关心，但是对于 non-empty vector a 技术看起来像这样：

int min = a[0], max = a[0];
std::nth_element(a.begin(), a.begin() + n, a.end(),
    [&](int lhs, int rhs) {
        min = std::min(min, std::min(lhs, rhs));
        max = std::max(max, std::max(lhs, rhs));
        return lhs < rhs;
    });

为了它的价值，在我的 (~10yo i5-660) HTPC 上使用 GCC 7.4，在 0 到 1000 之间有 100 万个随机 ints，nth_element 需要大约 36% 的时间min/max 比较没有。

从向量中提取最小值、最大值和中值的最有效方法是什么

What's the most efficient way to extract min, max & median from a vector

c++

algorithm

median