Recently the C++ community\u00a0 promotes the use of\u00a0the new standards to modernize the existing code base.\u00a0 However even before the release of the C++11 standard\u00a0some known\u00a0C++ experts\u00a0like Andrei Alexandrescu, Scott Meyers and Herb Sutter promotes the uses of the generic programming and they qualify it as Modern C++ Design.\u00a0Here\u2019s what say Andrei Alexandrescu about the Modern C++ design:<\/p>\n
Modern C++ Design defines and systematically uses\u00a0generic components<\/i>\u00a0– highly flexible design artifacts that are mixable and matchable to obtain rich behaviors with a small, orthogonal body of code.<\/p><\/blockquote>\n
Three\u00a0assertions are interesting in his point of view:<\/p>\n
\n
- Modern C++ Design defines and\u00a0systematically uses\u00a0<\/strong>generic components<\/strong>.<\/li>\n
- Highly\u00a0flexible<\/strong>\u00a0design.<\/li>\n
- Obtain rich behaviors with a\u00a0small, orthogonal<\/strong>\u00a0body of code.<\/li>\n<\/ul>\n
Modernize your C++ code it’s not only about using the new standards but we can also use some generics programming\u00a0 best practices to improve our code base. Let’s first discover some easy steps to manually modernize our code base and in the second section we will explore how to automatically modernize it.<\/p>\n
II –\u00a0Modernize manually your\u00a0source code<\/strong><\/p>\n
Let’s take as example an algorithm and try to modernize it. 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.<\/p>\n
Let’s\u00a0try to modernize this implementation of\u00a0\u00a0the quick sort algorithm:<\/span><\/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>\nAfter all, here are some\u00a0common 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 \u201c<\u201d and \u201c>\u201d, and we have some treatments like swapping data.<\/p>\n
Let\u2019s try to improve each one of these traits:<\/p>\n
Step1: Replace containers by iterators<\/strong><\/p>\n
Using 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 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>\n
For 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 algorithm could also be applied to a list of strings, Therefore it\u2019s 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>\n
Most algorithms use recurrent treatments like min, max and swap. for these operations it\u2019s 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\u2019s 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>