C++ Algorithm partialsortcopy function is similar to partialsort function which is used to rearrange the elements in the range[first, last), in such a way that the elements between the first and middle will be sorted and the elements between middle and last will be in an unspecified order. But partialsortcopy function puts the result in a new range[resultfirst, result_last).
The elements are compared using operator < for the first version, and comp for the second version.
Syntax
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);
Parameter
first : An input iterator pointing to the first element in the source range to be partially sorted.
last : A random access iterator pointing to the past last element in the source range to be partially sorted.
result_first : A random access iterator pointing to the first element in the sorted destination range.
result_last : A random access iterator pointing to the past last element in the sorted destination range.
comp : A user-defined binary predicate function that accepts two arguments and returns true if the two arguments are in order and false otherwise. It follows the strict weak ordering to order the elements.
Return value
It returns an iterator addressing to the element that follows the last element written in the result sequence.
Complexity
Average Complexity is less than linearithmic in the distance between first and last. Performs up to N*log (min (N, M)) element comparisons where N = last - first and M = middle - first.
Data races
The objects in the range [first, last) are altered.
Exceptions
This function throws an exception if any of element comparisons, the element swaps (or moves) or an operation on iterator throws an exception.
Please note that invalid parameters cause an undefined behavior.
Example 1
Let's see the simple example to demonstrate the use of partialsortcopy:
#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;
}
Output:
myvector contains: 1 2 3 4 5
Example 2
Let's see another simple example for the default version:
#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;
}
Output:
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 }
Example 3
Let's see a simple example for custom (predicate) version:
#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;
}
Output:
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 }
Example 4
Let's see another example:
#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;
}
Output:
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