C++ Algorithm partialsortcopy function behaves similarly to the partialsort function. It sorts the elements within a specified range [first, last), ensuring that the elements from first up to middle are sorted, while the elements from middle to last remain in an undefined order. However, partialsortcopy function differs in that it stores the sorted result in a different range [resultfirst, result_last).
The components are evaluated with the < operator in the initial iteration, and using comp for the subsequent iteration.
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
An input iterator pointing to the initial element within the origin range that is to be sorted partially.
last : A random access iterator pointing to the element just before the last one in the specified range that is to undergo partial sorting.
result_first: An iterator with random access capability pointing to the initial element within the sorted target range.
result_last : A random access iterator indicating the element after the last one in the sorted destination range.
comp : A custom binary predicate function that takes two parameters and evaluates to true if the two parameters are arranged sequentially, otherwise false. It adheres to the strict weak ordering principle for sorting the elements.
Return value
It yields an iterator pointing to the element succeeding the final element authored within the resultant sequence.
Complexity
The average complexity is below linearithmic concerning the distance from the initial to the final element. It conducts a maximum of N*log (min (N, M)) comparisons between elements, where N equals the last element minus the first element, and M equals the middle element minus the first element.
Data races
The elements within the range [first, last) undergo modification.
Exceptions
This function will raise an exception if an error occurs during comparisons between elements, swapping or moving elements, or while performing any operation on an iterator.
Please note that invalid parameters cause an undefined behavior.
Example 1
Let's explore a basic example to showcase the functionality 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 explore another straightforward illustration for the standard variant:
#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 examine a basic illustration for a 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
