极客笔记C++ 算法 partial_sort_copy()函数
C++算法 partial_sort_copy() 函数类似于partial_sort()函数，用于重新排列范围[first, last)之间的元素，使得第一个和中间之间的元素被排序，而中间和最后之间的元素呈未指定顺序。但是partial_sort_copy()函数将结果放在一个新的范围[result_first, result_last)中。
使用运算符 < 进行元素比较，第二个版本使用 comp 进行比较。
语法
default (1) template <class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy (InputIterator first,InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
custom (2) template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
partial_sort_copy (InputIterator first,InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
参数
first ：一个指向源范围中要部分排序的第一个元素的输入迭代器。
last ：一个指向源范围中要部分排序的最后一个元素后面的随机访问迭代器。
result_first ：一个指向排序后目标范围中第一个元素的随机访问迭代器。
result_last ：一个指向排序后目标范围中最后一个元素后面的随机访问迭代器。
comp ：一个用户定义的二元谓词函数，如果两个参数按顺序排列则返回true，否则返回false。它遵循严格弱排序来对元素进行排序。
返回值
它返回一个指向结果序列中最后一个写入元素后面的迭代器。
复杂度
平均复杂度小于first和last之间距离的对数线性。进行了最多N * log(min(N, M))次元素比较，其中N = last – first，M = middle – first。
数据竞争
范围[first, last)中的对象将被修改。
异常
如果任何元素比较、元素交换（或移动）或迭代器上的操作引发异常，此函数将抛出异常。
请注意，无效的参数会导致未定义的行为。
示例1
让我们看一个简单的示例来演示partial_sort_copy()的使用：
#include <iostream> // std::cout
#include <algorithm> // std::partial_sort_copy
#include <vector> // std::vector
using namespace std;
bool myfunction (int i,int j) { return (i<j); }
int main () {
int myints[] = {9,8,7,6,5,4,3,2,1};
vector<int> myvector (5);
// using default comparison (operator <):
partial_sort_copy (myints, myints+9, myvector.begin(), myvector.end());
// using function as comp
partial_sort_copy (myints, myints+9, myvector.begin(), 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: 1 2 3 4 5
示例2
让我们看看默认版本的另一个简单示例：
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std ;
int main()
{
const int VECTOR_SIZE = 8 ;
// Define a template class vector of int
typedef vector<int> IntVector ;
//Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;
IntVector Numbers(VECTOR_SIZE) ;
IntVector Result(4) ;
IntVectorIt start, end, it ;
// Initialize vector Numbers
Numbers[0] = 4 ;
Numbers[1] = 10;
Numbers[2] = 70 ;
Numbers[3] = 30 ;
Numbers[4] = 10;
Numbers[5] = 69 ;
Numbers[6] = 96 ;
Numbers[7] = 7;
start = Numbers.begin() ; // location of first
// element of Numbers
end = Numbers.end() ; // one past the location
// last element of Numbers
cout << "Before calling partial_sort_copy\n" << endl ;
// print content of Numbers
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
// sort the smallest 4 elements in the Numbers
// and copy the results in Result
partial_sort_copy(start, end, Result.begin(), Result.end()) ;
cout << "After calling partial_sort_copy\n" << endl ;
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
cout << "Result { " ;
for(it = Result.begin(); it != Result.end(); it++)
cout << *it << " " ;
cout << " }\n" << endl ;
return 0;
}
输出：
Before calling partial_sort_copy
Numbers { 4 10 70 30 10 69 96 7 }
After calling partial_sort_copy
Numbers { 4 10 70 30 10 69 96 7 }
Result { 4 7 10 10 }
示例3
让我们看一个简单的自定义（谓词）版本的示例：
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std ;
int main()
{
const int VECTOR_SIZE = 8 ;
// Define a template class vector of int
typedef vector<int> IntVector ;
//Define an iterator for template class vector of strings
typedef IntVector::iterator IntVectorIt ;
IntVector Numbers(VECTOR_SIZE) ;
IntVector Result(4) ;
IntVectorIt start, end, it ;
// Initialize vector Numbers
Numbers[0] = 4 ;
Numbers[1] = 10;
Numbers[2] = 70 ;
Numbers[3] = 30 ;
Numbers[4] = 10;
Numbers[5] = 69 ;
Numbers[6] = 96 ;
Numbers[7] = 7;
start = Numbers.begin() ; // location of first
// element of Numbers
end = Numbers.end() ; // one past the location
// last element of Numbers
cout << "Before calling partial_sort_copy\n" << endl ;
// print content of Numbers
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
// sort the smallest 4 elements in the Numbers
// and copy the results in Result
partial_sort_copy(start, end, Result.begin(),Result.end(),less<int>());
cout << "After calling partial_sort_copy\n" << endl ;
cout << "Numbers { " ;
for(it = start; it != end; it++)
cout << *it << " " ;
cout << " }\n" << endl ;
cout << "Result { " ;
for(it = Result.begin(); it != Result.end(); it++)
cout << *it << " " ;
cout << " }\n" << endl ;
return 0;
}
输出：
Before calling partial_sort_copy
Numbers { 4 10 70 30 10 69 96 7 }
After calling partial_sort_copy
Numbers { 4 10 70 30 10 69 96 7 }
Result { 4 7 10 10 }
示例4
让我们看另一个示例：
#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;
vector<int>::iterator it;
void print(vector<int> & v)
{
for (it = v.begin(); it != v.end(); it++) {
cout << *it << ' ';
}
cout << '\n';
}
int main()
{
vector<int> v0{4, 2, 5, 1, 3};
vector<int> v1{10, 11, 12};
vector<int> v2{10, 11, 12, 13, 14, 15, 16};
cout << "v0 : ";
print(v0);
cout << "v1 : ";
print(v1);
cout << "v2 : ";
print(v2);
it = partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
cout << "Writing v0 to v1 in ascending order gives: ";
print(v1);
it = partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
std::greater<int>());
cout << "Writing v0 to v2 in descending order gives: ";
print(v2);
return 0;
}
输出：
v0 : 4 2 5 1 3
v1 : 10 11 12
v2 : 10 11 12 13 14 15 16
Writing v0 to v1 in ascending order gives: 1 2 3
Writing v0 to v2 in descending order gives: 5 4 3 2 1 15 16