c++ - 调用 std::nth_element 后第 n 个元素之前的元素顺序

Question

我感兴趣的是找到 vector 中等于中位数的第一个(最左边)元素的最有效方法。找到中位数很简单:

std::nth_element(first, middle, last);
auto median = *middle;

但是如果输入像{2, 2, 2, 2, 1}，那么在调用std::nth_element之后，中间元素之前会有2s。我是否必须搜索中间左侧的所有值？还是保证2s都相邻？

问这个问题的另一种方法是在调用 std::nth_element 之后 {2, 1, 2, 2, 2} 是否可能，或者 {1, 2, 2, 2, 2} 是否有保证？在后一种情况下，我可以从中间向左搜索。前者需要从头到中查找，效率较低。从实证检验来看，后一种情况似乎成立。想知道是否有人有明确的答案，或者我是否遗漏了一些极端情况。

Answer 1

The documentation only guarantees :

• The element pointed at by nth is changed to whatever element would occur in that position if [first, last) was sorted.
• All of the elements before this new nth element are less than or equal to the elements after the new nth element.

请注意，没有保证第 n 个元素之前或之后的元素以任何特定顺序出现，只要之前的元素小于或等于它(并且推而广之，由于由于它是第 n 个元素的性质，它之后的元素大于或等于它)； {2, 1, 2, 2, 2} 和 {1, 2, 2, 2, 2} 都是完全合法的顺序。