Modern C++ is an amazing programming language with many powerful features. In C++, the Standard Template Library or STL has many algorithms for operations like searching, counting, and manipulation of ranges and their elements. C++17 has a new feature in the STL which allows you to sort vectors with the std::sort Parallel Sorting Algorithm. Both vectors and arrays can be sorted by the std::sort parallel sorting Algorithm with an appropriate C++ Compiler which supports C++17 and above.
What is the std::sort parallel sorting algorithm in C++?
The std::sort parallel sorting algorithm sorts the elements in the range from the first member to the last member in a specific order. During the order of equal elements, it is not guaranteed to be preserved. The sequence of the elements depends on the method used to compare them.
The syntax for the std::sort algorithm can be described as below:
|
1 2 3 |
void sort( ExecutionPolicy&& policy, RandomIt first, RandomIt last ); // since C++17 |
As an ExecutionPolicy std::execution::seq is used for sequential execution, std::execution::par is used for the parallel execution . In general, there are 3 ExecutionPolicy values you can use here,
std::execution::seqstd::execution::parstd::execution::par_unseq
Now let’s see how we can use std::sort() with std::vector in some examples.
How to sort std::vector in C++?
Vectors are dynamic arrays included in <vector> library in modern C++ and they can resize themselves automatically when a member of a vector is inserted or deleted. Vectors are the same as dynamic arrays and these dynamic arrays of vectors are handled automatically by the container. Vectors are the way of Modern C++; their members are placed in the contiguous memory storage; thus, they can be resized, and can be accessed and traversed using iterators.
When we Insert data into vectors it may more time than static arrays because of the need of extending the vector array. Vectors have low memory usage as in dynamic array implementations, because of having good data cache utilization and locality of reference. We can easily access an element of a vector by giving its index between ‘[‘ and ‘]’ just as we do with arrays, which means vector members can be referenced by indices.
Vectors allow random access; that is, an element of a vector may be referenced in the same manner as elements of arrays (by array indices). Linked lists and sets, on the other hand, do not support random access or pointer arithmetic. Vectors are very useful for storing data in lists whose number of elements (length in total) may not be known before setting up the list. Because the vector data structure allocates the necessary memory needed for specific data storage erasing and clearing vector elements from a vector does not need to free any of the memory associated with that element. That makes vectors much safer and more modern in C++ than arrays.
A vector can be defined using this syntax,
|
1 2 3 |
std::vector<object type> variable_name; |
we can declare a vec vector with 100 members as below,
|
1 2 3 |
std::vector<int> vec(100); |
Now let’s see how we can sort a lot of vector elements with std::sort algorithm. We can use default sort operator as below,
|
1 2 3 |
std::sort( vec.begin(), vec.end() ); |
Is there a full example of how to sort a std::vector with the STL parallel sorting algorithm in C++?
Now, let’s see how we can sort a lot of vector elements, here is an example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #include <vector> #include <algorithm> #include <ctime> int main() { std::vector<int> vec(100000); // fill vector with random numbers std::srand(unsigned(std::time(nullptr))); std::generate(vec.begin(), vec.end(), std::rand); // sort vector std::sort( vec.begin(), vec.end()); // print first 100 and last 100 members to check if sorted well for(auto it = vec.begin(); it<vec.begin()+100; ++it) std::cout << *it << ','; std::cout << '\n'; for(auto it = vec.end()-100; it<vec.end(); ++it) std::cout << *it << ','; std::cout << '\n'; system("pause"); return 0; } |
We can add execution policy with std::execution::par execution policy as below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #include <vector> #include <algorithm> #include <ctime> int main() { std::vector<int> vec(100000); // fill vector with random numbers std::srand(unsigned(std::time(nullptr))); std::generate(vec.begin(), vec.end(), std::rand); // sort vector std::sort(std::execution::par, vec.begin(), vec.end()); // print first 100 and last 100 members to check if sorted well for(auto it = vec.begin(); it<vec.begin()+100; ++it) std::cout << *it << ','; std::cout << '\n'; for(auto it = vec.end()-100; it<vec.end(); ++it) std::cout << *it << ','; std::cout << '\n'; system("pause"); return 0; } |
Note that, in C++ std::array is on the stack, in other words it has less limits than vectors.
C++ Builder is the easiest and fastest C and C++ IDE for building simple or professional applications on the Windows, MacOS, iOS & Android operating systems. It is also easy for beginners to learn with its wide range of samples, tutorials, help files, and LSP support for code. RAD Studio’s C++ Builder version comes with the award-winning VCL framework for high-performance native Windows apps and the powerful FireMonkey (FMX) framework for cross-platform UIs.
There is a free C++ Builder Community Edition for students, beginners, and startups; it can be downloaded from here. For professional developers, there are Professional, Architect, or Enterprise versions of C++ Builder and there is a trial version you can download from here.
