c++ 什么是nth_element,它到底做什么?以及如何实现它

czfnxgou  于 11个月前  发布在  其他
关注(0)|答案(3)|浏览(82)

我几乎理解了许多STL算法,直到我达到了std::nth_element算法。我被它卡住了;我不知道它是如何工作的,它确实确实做到了。
为了教育和理解的缘故,有人能给我解释一下算法std::nth_element是如何工作的吗?

std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin() + 2, v.end());

for (auto i : v)
    std::cout << i << " ";
std::cout << '\n';

字符串
输出:

  • 那么nth元素在哪里呢?
  • 算法是如何做的?
  • 它是不是做了某种部分排序?

以下是来自cppreference.com的一些解释:
nth_element是一个部分排序算法,它重新排列[first,last)中的元素,使得:

  • 如果[first,last)被排序,第n个指向的元素将被更改为在该位置出现的任何元素。
  • 这个新的第n个元素之前的所有元素都小于或等于新的第n个元素之后的元素。更正式地说,nth_element按升序对范围[first,last]进行部分排序,使得条件!(*j < *i)(对于第一版本,或者对于第二版本comp(*j, *i) == false)对于范围[first,nth)中的任何i和对于范围[nth,最后一个)。如果范围是完全排序的,那么放置在第n个位置的元素就是将出现在该位置的元素。

第n个可能是结束迭代器,在这种情况下,函数没有效果。

  • 我仍然对它感到困惑。什么是第n个元素以及如何实现一个可能的算法?。为了教育起见,我模仿了许多STL算法。非常感谢!
x33g5p2x

x33g5p2x1#

那么第n个元素在哪里呢?
第n个元素是索引为22,因为这是您传递begin()+2时所要求的。
如果[first,last)被排序,第n个指向的元素将被更改为在该位置出现的任何元素。
这意味着,如果向量被排序,元素的顺序将是

0 1 2 3 4 5 6 7 8 9 
    ^--- begin() + 2

字符串
你要求在索引2(第三个位置)有第三个最大的元素,这就是算法所做的。
此外,它将所有较小的元素放在前面,所有较大的元素放在后面:
!(*j < *i)(对于第一个版本,或者comp(*j, *i) == false对于第二个版本)对于范围[first,nth)中的任何i和范围[nth,last)中的任何j都满足。
让我们使用索引而不是迭代器,那么对于任何i < 2和任何j > 2,它都保持v[i] < v[j]。换句话说,10都小于2 3 6 7 8 5 4 9中的任何元素。

roqulrg3

roqulrg32#

你在第二个参数中指定一个索引,这个索引是所有索引的关键:在这个索引中,在这个例子中,[2] per开始+ 2,会有一个数字,如果这个东西被排序,在它之前和之后,数字的顺序是未知的,但是保证它在右边会更大,在左边会更小。
请考虑:

std::vector<int> v{ 9, 5, 4, 2, 1 };
std::nth_element(v.begin(), v.begin() + 2, v.end());

字符串
在这里,我们看一下索引2。如果整个东西都排序了,那里会有什么元素?我们将标记第n个元素。
于是:

9, 5, *4*, 2, 1


分类:

1,2,3,5,9


如果整件事都被排序了,索引2处的数字是什么,我们可以看到它是3。
现在我们得到:
第三,
在左边,小于3的元素将以未指定的顺序出现,在右边也是如此,但最大。
可能的结果:

  • 2 1 3 5 9
  • 1 2 3 9 5
  • 21395...

第n个元素是如果整个事情被排序的话应该在那里的元素,左边的数字在未指定的顺序中保证较小,右边的数字相同。

mbskvtky

mbskvtky3#

在讨论您的问题之前,我将首先解释我的代码
例如,我有这样的代码

int m_array_biasa[8] {3,2,10,45,33,56,23,47};

字符串
我通常用它

std::nth_element(m_array_biasa, m_array_biasa + 4, m_array_biasa + 8);


所以这里的第n个元素是4[33],std::nth_element的规则是,第n个元素左边的数字必须小于或等于,右边的数字必须大于第n个元素
并且不要忘记,数据必须从小到大排序(默认)
所以最初的数据
3,2,10,45,33,56,23,47
改为
2 3 10 23 33 45 47 56
我的第n个是4[33],所以上面的规则适用(不包括排序结果)
并且结果被
3 2 10 23 33 56 45 47
注意,位置33没有改变,但有时会有点混乱,例如我们将33改为1,然后结果
2 1 3 10 23 45 47 56
这里发生了什么,为什么数字1移动了(被23取代),为什么它没有保持像以前的数字33一样,我之前说过我们必须先对数据进行排序(参见上面的排序),结果发现索引nth[4]是数字23,然后数字1被数字23取代,为什么要取代?,参见nth_element规则
现在回答你的问题。

std::vector<int> v{ 9, 3, 6, 2, 1, 7, 8, 5, 4, 0 };
std::nth_element(v.begin(), v.begin() + 2, v.end());


v.开始()包含9,v.开始()+ 2包含6,记住,nth_element将首先对其排序
0 1 2 3 4 5 6 7 8 9
你的输出是
1 0 2 3 6 7 8 5 4 9
上面的第n个[2](根据你的v.开始()+ 2)p是2,所以2在这里就像是对其他数据的引用,2之前的数据必须小于它,2之后的数据必须大于它

相关问题