C++算法 nth_element()函数用于按升序对第一个元素与第n个元素之间的元素进行排序,而对第n个元素与最后一个元素之间的元素不进行排序。但是,第n个元素和最后一个元素之间的元素都不比第一个元素和第n个元素之间的元素小。
default (1) template <class RandomAccessIterator> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); custom (2) template <class RandomAccessIterator, class Compare> void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);
first:一个随机访问迭代器,指向要使用的参数内的第一个元素。
last:一个随机访问迭代器,指向要使用的参数中的最后一个最后一个元素。
comp :用户定义的二进制谓词函数,该函数接受两个参数,如果两个参数顺序正确,则返回true,否则返回false。
nth :一个随机访问迭代器,该迭代器将访问包含已排序元素的参数[first,last)中的位置。
没有
让我们看一个简单的示例来演示nth_element()的用法:
#include <iostream> #include <vector> #include <algorithm> using namespace std; void print(vector<int> ar) { for(auto x : ar) cout << x << " "; cout << endl; } int main() { vector<int> ar = {1, 3, 6, 1, 2, 4, 7, 0}; cout<<"Before: "; //will print 1 3 6 1 2 4 7 0 print(ar); //mid = 5th element (ar.begin() + 4) auto mid = ar.begin() + distance(ar.begin(), ar.end())/2; //lets nth_element ar to mid nth_element(ar.begin(), mid, ar.end()); cout<<"\nAfter: "; //will print 2 0 1 1 3 4 7 6 //mid points to element 3 print(ar); return 0; }
输出:
Before: 1 3 6 1 2 4 7 0 After: 2 0 1 1 3 4 7 6
让我们看另一个简单的例子:
#include <iostream> #include <vector> #include <algorithm> #include <functional> using namespace std; int main() { vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3}; cout<<"Elements are: "; for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it) cout << ' ' << *it; cout << '\n'; nth_element(v.begin(), v.begin() + v.size()/2, v.end()); cout << "The median is " << v[v.size()/2] << '\n'; nth_element(v.begin(), v.begin()+1, v.end(), greater<int>()); cout << "The second largest element is " << v[1] << '\n'; return 0; }
输出:
Elements are: 5 6 4 3 2 6 7 9 3 The median is 5 The second largest element is 7
让我们看另一个简单的例子:
#include <iostream> //std::cout #include <algorithm> //std::nth_element, std::random_shuffle #include <vector> //std::vector using namespace std; bool myfunction (int i,int j) { return (i<j); } int main () { vector<int> myvector; //set some values: for (int i=1; i<10; i++) myvector.push_back(i); //1 2 3 4 5 6 7 8 9 random_shuffle (myvector.begin(), myvector.end()); //using default comparison (operator <): nth_element (myvector.begin(), myvector.begin()+5, myvector.end()); //using function as comp nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction); //print out content: cout << "myvector contains:"; for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) cout << ' ' << *it; cout << '\n'; return 0; }
输出:
myvector contains: 5 2 3 1 4 6 7 8 9
让我们看另一个简单的例子:
#include <vector> #include <algorithm> #include <functional> //For greater<int>( ) #include <iostream> // Return whether first element is greater than the second bool UDgreater ( int elem1, int elem2 ) { return elem1 > elem2; } int main() { using namespace std; vector <int> v1; vector <int>::iterator Iter1; int i; for ( i = 0 ; i <= 5 ; i++ ) v1.push_back( 3 * i ); int ii; for ( ii = 0 ; ii <= 5 ; ii++ ) v1.push_back( 3 * ii + 1 ); int iii; for ( iii = 0 ; iii <= 5 ; iii++ ) v1.push_back( 3 * iii +2 ); cout << "Original vector:\n v1 = ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")" << endl; nth_element(v1.begin( ), v1.begin( ) + 3, v1.end( ) ); cout << "Position 3 partitioned vector:\n v1 = ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")" << endl; //To sort in descending order, specify binary predicate nth_element( v1.begin( ), v1.begin( ) + 4, v1.end( ), greater<int>( ) ); cout << "Position 4 partitioned (greater) vector:\n v1 = ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")" << endl; random_shuffle( v1.begin( ), v1.end( ) ); cout << "Shuffled vector:\n v1 = ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")" << endl; //A user-defined (UD) binary predicate can also be used nth_element( v1.begin( ), v1.begin( ) + 5, v1.end( ), UDgreater ); cout << "Position 5 partitioned (UDgreater) vector:\n v1 = ( " ; for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ ) cout << *Iter1 << " "; cout << ")" << endl; return 0; }
输出:
Original vector: v1 = ( 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 17 ) Position 3 partitioned vector: v1 = ( 1 0 2 3 8 5 9 4 7 6 10 16 13 15 12 11 14 17 ) Position 4 partitioned (greater) vector: v1 = ( 16 17 14 15 13 12 11 9 7 8 10 6 1 4 5 3 2 0 ) Shuffled vector: v1 = ( 13 10 6 3 5 2 0 17 11 8 15 9 7 14 16 1 12 4 ) Position 5 partitioned (UDgreater) vector: v1 = ( 14 17 15 16 13 12 10 11 9 8 0 2 7 5 3 1 6 4 )
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)