The BooSTL Algorithms: Boost Algorithms That Extend the STL (3/3)

The BooSTL algorithms are what we can call the Boost algorithms which are in the same spirit as those of the STL. They encapsulate operations on collections, and being able to use them allows to write (or re-write) more expressive code. To cover all their contents, we split up the articles of the BooSTL into three parts:

• the BooSTL algorithms on sorting and partitioning,
• the BooSTL algorithms on searching,
• the other BooSTL algorithms.

So here we go to cover the rest of the BooSTL algorithms which are not in sorting, partitioning nor searching.

gather

gather consists in rearranging a range so that its elements satisfying a certain predicate are grouped around a specified position, and keep the same relative order: So, after applying gather, the above collection would look like this:   Here is the above transformation translated into code:

#include <iostream>
#include <vector>
#include <boost/algorithm/gather.hpp>

int main()
{
    std::vector<int> numbers = { 0, 1, 1, 1, 0, 0, 1, 0, 1 };
    
    boost::algorithm::gather(begin(numbers), end(numbers),
                             begin(numbers) + 5,
                             [](int n){ return n == 1; });
    
    for (auto number : numbers) std::cout << number << ' ';
}

This code outputs:

0 0 1 1 1 1 1 0 0

The implementation of gather is not easy to find, but easy to understand when you read it:

template <
    typename BidirectionalIterator,  // Iter models BidirectionalIterator
    typename Pred>                   // Pred models UnaryPredicate
std::pair<BidirectionalIterator, BidirectionalIterator> gather 
        ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred )
{
//  The first call partitions everything up to (but not including) the pivot element,
//  while the second call partitions the rest of the sequence.
    return std::make_pair (
        std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )),
        std::stable_partition ( pivot, last,   boost::bind<bool> ( pred, _1 )));
}

It considers the part of the collection before the grouping points and the one after it, and partitions the first according to “being not blue” and the second to “being blue”. Note that in C++17, the inversion of the predicate !boost::bind<bool> ( pred, _1 ) can be done with not_fn(pred). And the second bind, boost::bind<bool> ( pred, _1 ) deosn’t alter the predicate. I suppose it is here for symmetry only (if you see another reason, please drop a comment!).

boost::algorithm::gather is available in the header boost/algorithm/gather.hpp.

one_of and the *_of_equal

You know std::all_of, std::any_of and std::none_of from the STL? boost::algorithm::one_of does something in the same spirit. one_of returns true if there is exactly one element in the range that satisfies a predicate.

Before we look at the implementation, I suggest that you make a quick attempt of writing it yourself. It doesn’t take more than a few minutes, but if you implement it naively like I did you’ll be surprised at how expressive the STL implementation is. Let’s have a look at its implementation:

template<typename InputIterator, typename Predicate> 
bool one_of ( InputIterator first, InputIterator last, Predicate p )
{
    InputIterator i = std::find_if (first, last, p);
    if (i == last)
        return false;    // Didn't occur at all
    return boost::algorithm::none_of (++i, last, p);
}

This is an elegant implementation. No counter, no bookkeeping, and just one if statement that tests the predicates. This implementation tells that it does the right thing, don’t you think?

boost::algorithm::one_of is located in boost/algorithm/cxx11/one_of.hpp. The “cxx11” in the path looks as though one_of was thought to be added to C++11 like all_of and the others, but that it didn’t in the end.

Now that we’re acquainted with this fourth algorithm testing a predicate on a range, meet their *_equal counterparts:

• boost::algorithm::all_of_equal from header boost/algorithm/cxx11/all_of.hpp,
• boost::algorithm::any_of_equal from header boost/algorithm/cxx11/any_of.hpp
• boost::algorithm::none_of_equal from header boost/algorithm/cxx11/none_of.hpp
• boost::algorithm::one_of_equal from header boost/algorithm/cxx11/one_of.hpp

None_of those have equivalents in the STL. They take a value instead of a predicate, and behave like their STL counterparts but with a predicate being “equal to that value”.

is_palindrome

A palindrome is a string that is equal to its reverse. For example, “level”, “madam” or “step on no pets” are palindromes. To identify if a given string is a palindrome we could naively just:

• make a copy of the string,
• std::reverse the copy,
• compare the string and the copy with std::equal.

But this is more work that necessary since it makes numerous traversals of the string and needs extra memory. Boost offers boost::algorithm::is_palindrome that does the job much more efficiently. Here is its implementation:

template <typename BidirectionalIterator, typename Predicate>
bool is_palindrome(BidirectionalIterator begin, BidirectionalIterator end, Predicate p)
{
    if(begin == end)
    {
        return true;
    }

    --end;
    while(begin != end)
    {
        if(!p(*begin, *end))
        {
            return false;
        }
        ++begin;
        if(begin == end)
        {
            break;
        }
        --end;
    }
    return true;
}

No elegant calls to STL algorithms for this one. Just walking back and forth from the beginning and the end, until the two ends meet. boost::algorithm::is_palindrome is available in boost/algorithm/is_palindrome.hpp.

hex and unhex

hex does not convert a decimal number into an hexadecimal one. Rather, it converts characters from the ASCII table into their hexadecimal number counterpart. For example, ‘B’ corresponds to 42, ‘o’ to 6F, S to 53, T to 54 and L to 4C. So here is how to convert the string “BooSTL” into hexadecimal:

#include <iostream>
#include <iterator>
#include <string>
#include <boost/algorithm/hex.hpp>

int main()
{    
    std::string BooSTL_Hex;
    boost::algorithm::hex("BooSTL", std::back_inserter(BooSTL_Hex));
    std::cout << BooSTL_Hex << '\n';
}

And this code outputs:

426F6F53544C

Note that hex can also write into a collection of ints:

#include <iostream>
#include <iterator>
#include <vector>
#include <boost/algorithm/hex.hpp>

int main()
{    
    std::vector<int> BooSTL_Hex;
    boost::algorithm::hex("BooSTL", std::back_inserter(BooSTL_Hex));
    
    for (auto n : BooSTL_Hex)
    {
        std::cout << n << ' ';
    }
}

Here is what the above code outputs:

52 50 54 70 54 70 53 51 53 52 52 67

Wonder what that means? This corresponds to the string output that we got before ("426F6F53544C"), with each of its letter considered as an ASCII character and converted to decimal. So ‘4’ is 52, ‘2’ is 50, and so on. unhex does the reverse operation of hex. To illustrate, let’s feed to unhex the output that we got from hex:

#include <iostream>
#include <iterator>
#include <string>
#include <boost/algorithm/hex.hpp>

int main()
{    
    std::string BooSTL_Unhex;
    boost::algorithm::unhex("426F6F53544C", std::back_inserter(BooSTL_Unhex));
    
    std::cout << BooSTL_Unhex << '\n';
}

The above code outputs:

BooSTL

boost::algorithm::hex and boost::algorithm::unhex are available in the boost/algorithm/hex.hpp header.

clamp

Let’s finish with an easy one. To clamp an object means to lock it between two pieces of metal. In this spirit, clamping a value x between a and b returns:

• a if x < a,
• b if b < x,
• x otherwise.

Boost offers the function boost::algorithm::clamp that does just that, and accompanies it with boost::algorithm::clamp_range, which applies clamp to every value of a range and produce the clamped values through an output iterator. Conceptually, clamp_range is equivalent to std::transform with clamp as a transforming function.

What now?

I think we have covered all the STL-like algorithms that Boost has. If you see any one missing, let me know and I’ll add it. Now that we know the BooSTL algorithms, where next do you think we should look to expand our vocabulary of C++ algorithms?

Related articles:

• the BooSTL algorithms on sorting and partitioning,
• the BooSTL algorithms on searching,
• the other BooSTL algorithms.

Don't want to miss out ? Follow:   
Share this post!