Algorithms are used for calculation, data processing, and automated reasoning. Programming them\u00a0is not always an easy task and it depends on their complexity.\u00a0In C++ many efforts was done to simplify their implementation and to make them more powerful. Indeed, during the last ten years many C++ experts promotes the use of “Modern C++ Design” to improve the quality of the\u00a0C++ project design and\u00a0implementation.<\/p>\n
In this post we will discover three steps to modernize a C++ algorithm, for that we take as example the quick sort algorithm. Here’s a classic\u00a0implementation:<\/p>\n
\/\/ The partition function\r\n<\/span>int<\/span> partition<\/span>(<\/span>int<\/span>*<\/span> input<\/span>,<\/span>int<\/span> p<\/span>,<\/span>int<\/span> r<\/span>)<\/span>{\r\n<\/span> int<\/span> pivot <\/span>=<\/span> input<\/span>[<\/span>r<\/span>];\r\n<\/span> while<\/span>(<\/span> p <\/span><<\/span> r <\/span>)<\/span>{\r\n<\/span> while<\/span>(<\/span> input<\/span>[<\/span>p<\/span>]<\/span><<\/span> pivot <\/span>)<\/span>\r\n p<\/span>++;\r\n<\/span> while<\/span>(<\/span> input<\/span>[<\/span>r<\/span>]<\/span>><\/span> pivot <\/span>)<\/span>\r\n r<\/span>--;\r\n<\/span> if<\/span>(<\/span> input<\/span>[<\/span>p<\/span>]<\/span>==<\/span> input<\/span>[<\/span>r<\/span>]<\/span>)<\/span>\r\n p<\/span>++;\r\n<\/span> else<\/span>if<\/span>(<\/span> p <\/span><<\/span> r <\/span>)<\/span>{\r\n<\/span> int<\/span> tmp <\/span>=<\/span> input<\/span>[<\/span>p<\/span>];<\/span>\r\n input<\/span>[<\/span>p<\/span>]<\/span>=<\/span> input<\/span>[<\/span>r<\/span>];<\/span>\r\n input<\/span>[<\/span>r<\/span>]<\/span>=<\/span> tmp<\/span>;\r\n<\/span> }\r\n<\/span> }\r\n<\/span> return<\/span> r<\/span>;\r\n<\/span>}\r\n<\/span>\/\/ The quicksort recursive function\r\n<\/span>void<\/span> quicksort<\/span>(<\/span>int<\/span>*<\/span> input<\/span>,<\/span>int<\/span> p<\/span>,<\/span>int<\/span> r<\/span>)<\/span>{\r\n<\/span> if<\/span>(<\/span> p <\/span><<\/span> r <\/span>)<\/span>{\r\n<\/span> int<\/span> j <\/span>=<\/span> partition<\/span>(<\/span>input<\/span>,<\/span> p<\/span>,<\/span> r<\/span>);<\/span> \r\n quicksort<\/span>(<\/span>input<\/span>,<\/span> p<\/span>,<\/span> j<\/span>-<\/span>1<\/span>);<\/span>\r\n quicksort<\/span>(<\/span>input<\/span>,<\/span> j<\/span>+<\/span>1<\/span>,<\/span> r<\/span>);\r\n<\/span> }\r\n<\/span>}<\/span><\/code><\/pre>\n\u00a0<\/span><\/code>After all, \u00a0what the common traits of algorithms?<\/p>\n\n- Using containers of \u00a0an element kind and Iterating over\u00a0them.<\/li>\n
- Comparison between elements.<\/li>\n
- And of course some \u00a0treatments over elements.<\/li>\n<\/ul>\n
In our implementation the container is a raw array of int, we iterate thought increment and decrement. We compare using “<” and “>”, and we have some traitements like swaping data.<\/p>\n
Let’s try to improve each one of these traits:<\/p>\n
Step1: Replace containers by iterators<\/strong><\/p>\nUsing not generic containers will force us to use a specific element kind.\u00a0To apply the same algorithm to other types, we have to copy\/paste the code. The generic containers resolve this issue, and permit to use any element kind, for example for our quick sort algorithm, we can use std::vector<T> as container instead of a raw array.<\/p>\n
A raw array or an std::vector \u00a0is just one possibility between many others to represent a set of elements, we can also apply the same algorithm to\u00a0a linked list, a queue or whatever any other container. For this needs the iterator is the best choice to abstract the container used.<\/p>\n
An\u00a0iterator\u00a0is any object that, pointing to some element in a range of elements , has the ability to iterate through the elements of that range using a set of operators (with at least the increment (++) and dereference (*) operators).\u00a0Iterators are classified into five categories depending on the functionality they implement: Input, Output, Forward, Bidirectional and random access.<\/p>\n
In our algorithm\u00a0we have to specify which kind of iterator to use. For that we have to detect \u00a0which iterations are used.\u00a0For the quick sort algo the \u00a0increment and \u00a0decrement iterations are applied. Therefore, a bidirectional iterator is needed.\u00a0Using iterators we can \u00a0define the method like this:<\/p>\n
template<\/span><<\/span> typename<\/span> BidirectionalIterator ><\/span>\r\nvoid<\/span> quick_sort(<\/span> BidirectionalIterator first, BidirectionalIterator last )<\/span><\/pre>\nStep2: Make the comparator generic if possible<\/strong><\/p>\nFor some algorithms, the elements treated are not only numbers, they could be string or a class. In this case make the comparator generic will permit us to have a more generic algorithm.<\/p>\n
The quick sort algo could also be applied to a list of strings, Therefore it’s better to have a generic comparator.<\/p>\n
After using a\u00a0generic comparator, the definition could be modified like this:<\/p>\n
template<\/span><<\/span> typename<\/span> BidirectionalIterator, typename<\/span> Compare ><\/span>\r\nvoid<\/span> quick_sort(<\/span> BidirectionalIterator first, BidirectionalIterator last, Compare cmp )<\/span><\/pre>\nStep3: Replace treatments by standard ones<\/strong><\/p>\nMost algorithms use recurrent traitements like min, max and swap. for these operations it’s preferable to not reinvent the wheel, and uses the standard implementation existing in the <algorithm> header.<\/p>\n
In our case we can use the swap method from the STL than creating our specific method.<\/p>\n
std::<\/span>iter_swap<\/span>(<\/span> pivot, left )<\/span>;<\/span><\/pre>\nAnd here’s the modified result after these three steps:<\/p>\n
#include <functional><\/span>\r\n#include <algorithm><\/span>\r\n#include <iterator><\/span>\r\n \r\ntemplate<\/span><<\/span> typename<\/span> BidirectionalIterator, typename<\/span> Compare ><\/span>\r\nvoid<\/span> quick_sort(<\/span> BidirectionalIterator first, BidirectionalIterator last, Compare cmp )<\/span> {<\/span>\r\n if<\/span>(<\/span> first !<\/span>=<\/span> last )<\/span> {<\/span>\r\n BidirectionalIterator left =<\/span> first;<\/span>\r\n BidirectionalIterator right =<\/span> last;<\/span>\r\n BidirectionalIterator pivot =<\/span> left++<\/span>;<\/span>\r\n \r\n while<\/span>(<\/span> left !<\/span>=<\/span> right )<\/span> {<\/span>\r\n if<\/span>(<\/span> cmp(<\/span> *<\/span>left, *<\/span>pivot )<\/span> )<\/span> {<\/span>\r\n ++<\/span>left;<\/span>\r\n }<\/span> else<\/span> {<\/span>\r\n while<\/span>(<\/span> (<\/span>left !<\/span>=<\/span> right)<\/span> &&<\/span> cmp(<\/span> *<\/span>pivot, *<\/span>right )<\/span> )<\/span>\r\n --<\/span>right;<\/span>\r\n std::<\/span>iter_swap<\/span>