Three easy steps to modernize your C++ algorithms

Algorithms are used for calculation, data processing, and automated reasoning. Programming them is not always an easy task and it depends on their complexity. In 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 C++ project design and implementation.

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 implementation:

// The partition function
int partition(int* input,int p,int r){
        int pivot = input[r];
        while( p < r ){
                 while( input[p]< pivot )
                     p++;
                 while( input[r]> pivot )
                    r--;
                if( input[p]== input[r])
                    p++;
                elseif( p < r ){
                     int tmp = input[p];
                     input[p]= input[r];
                     input[r]= tmp;
                }
        }
         return r;
}
// The quicksort recursive function
void quicksort(int* input,int p,int r){
        if( p < r ){
              int j = partition(input, p, r);        
              quicksort(input, p, j-1);
              quicksort(input, j+1, r);
        }
}

 After all,  what the common traits of algorithms?

• Using containers of  an element kind and Iterating over them.
• Comparison between elements.
• And of course some  treatments over elements.

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.

Let’s try to improve each one of these traits:

Step1: Replace containers by iterators

Using not generic containers will force us to use a specific element kind. To 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.

A raw array or an std::vector  is just one possibility between many others to represent a set of elements, we can also apply the same algorithm to a linked list, a queue or whatever any other container. For this needs the iterator is the best choice to abstract the container used.

An iterator is 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). Iterators are classified into five categories depending on the functionality they implement: Input, Output, Forward, Bidirectional and random access.

In our algorithm we have to specify which kind of iterator to use. For that we have to detect  which iterations are used. For the quick sort algo the  increment and  decrement iterations are applied. Therefore, a bidirectional iterator is needed. Using iterators we can  define the method like this:

template< typename BidirectionalIterator >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last )

Step2: Make the comparator generic if possible

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.

The quick sort algo could also be applied to a list of strings, Therefore it’s better to have a generic comparator.

After using a generic comparator, the definition could be modified like this:

template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp )

Step3: Replace treatments by standard ones

Most 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.

In our case we can use the swap method from the STL than creating our specific method.

std::iter_swap( pivot, left );

And here’s the modified result after these three steps:

#include <functional>
#include <algorithm>
#include <iterator>
 
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
    if( first != last ) {
        BidirectionalIterator left  = first;
        BidirectionalIterator right = last;
        BidirectionalIterator pivot = left++;
 
        while( left != right ) {
            if( cmp( *left, *pivot ) ) {
                ++left;
            } else {
                while( (left != right) && cmp( *pivot, *right ) )
                    --right;
                std::iter_swap( left, right );
            }
        }
 
        --left;
        std::iter_swap( pivot, left );
 
        quick_sort( first, left, cmp );
        quick_sort( right, last, cmp );
    }
}
 
template< typename BidirectionalIterator >
    inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
        quick_sort( first, last,
                std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
                );
    }

This implementation has the following advantages:

• Could be applied to many element kind.
• The container could be vector, set, list or whatever container with a biderectional iterator.
• It uses a well optimized and tested standard functions.

Conclusion

The Modern C++ design brings many advantages. Moreover no advanced techniques are needed to modernize a C++ algorithm, and it’s worth to change their implementations to use the Modern C++ recommendations.