Boost C++ Libraries

The header file clamp.hpp contains two functions for "clamping" a value between a pair of boundary values.

clamp

The function clamp (v, lo, hi) returns:

Note: using clamp with floating point numbers may give unexpected results if one of the values is NaN.

There is also a version that allows the caller to specify a comparison predicate to use instead of operator <.

template<typename T>
const T& clamp ( const T& val, const T& lo, const T& hi );

template<typename T, typename Pred>
const T& clamp ( const T& val, const T& lo, const T& hi, Pred p );

The following code:

int foo = 23;
foo = clamp ( foo, 1, 10 );

will leave foo with a value of 10

Complexity: clamp will make either one or two calls to the comparison predicate before returning one of the three parameters.

clamp_range

There are also four range-based versions of clamp, that apply clamping to a series of values. You could write them yourself with std::transform and bind, like this: std::transform ( first, last, out, bind ( clamp ( _1, lo, hi ))), but they are provided here for your convenience.

template<typename InputIterator, typename OutputIterator>
OutputIterator clamp_range ( InputIterator first, InputIterator last, OutputIterator out,
    typename std::iterator_traits<InputIterator>::value_type lo,
    typename std::iterator_traits<InputIterator>::value_type hi );

template<typename Range, typename OutputIterator>
OutputIterator clamp_range ( const Range &r, OutputIterator out,
	typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type lo,
	typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type hi );

template<typename InputIterator, typename OutputIterator, typename Pred>
OutputIterator clamp_range ( InputIterator first, InputIterator last, OutputIterator out,
    typename std::iterator_traits<InputIterator>::value_type lo,
    typename std::iterator_traits<InputIterator>::value_type hi, Pred p );

template<typename Range, typename OutputIterator, typename Pred>
OutputIterator clamp_range ( const Range &r, OutputIterator out,
	typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type lo,
	typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type hi,
	Pred p );

The header file 'boost/algorithm/gather.hpp' contains two variants of a single algorithm, gather.

gather() takes a collection of elements defined by a pair of iterators and moves the ones satisfying a predicate to them to a position (called the pivot) within the sequence. The algorithm is stable. The result is a pair of iterators that contains the items that satisfy the predicate.

Interface

The function gather returns a std::pair of iterators that denote the elements that satisfy the predicate.

There are two versions; one takes two iterators, and the other takes a range.

namespace boost { namespace algorithm {

template <typename BidirectionalIterator, typename Pred>
std::pair<BidirectionalIterator,BidirectionalIterator>
gather ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred );

template <typename BidirectionalRange, typename Pred>
std::pair<typename boost::range_iterator<const BidirectionalRange>::type, typename boost::range_iterator<const BidirectionalRange>::type>
gather ( const BidirectionalRange &range, typename boost::range_iterator<const BidirectionalRange>::type pivot, Pred pred );

}}

Examples

Given an sequence containing:

0 1 2 3 4 5 6 7 8 9

a call to gather ( arr, arr + 10, arr + 4, IsEven ) will result in:

1 3 0 2 4 6 8 5 7 9
    |---|-----|
  first |  second
      pivot

where first and second are the fields of the pair that is returned by the call.

Iterator Requirements

gather work on bidirectional iterators or better. This requirement comes from the usage of stable_partition, which requires bidirectional iterators. Some standard libraries (libstdc++ and libc++, for example) have implementations of stable_partition that work with forward iterators. If that is the case, then gather will work with forward iterators as well.

Storage Requirements

gather uses stable_partition, which will attempt to allocate temporary memory, but will work in-situ if there is none available.

Complexity

If there is sufficient memory available, the run time is linear: O(N)

If there is not any memory available, then the run time is O(N log N).

Exception Safety

Notes

The header file 'boost/algorithm/hex.hpp' contains three variants each of two algorithms, hex and unhex. They are inverse algorithms; that is, one undoes the effort of the other. hex takes a sequence of values, and turns them into hexadecimal characters. unhex takes a sequence of hexadecimal characters, and outputs a sequence of values.

hex and unhex come from MySQL, where they are used in database queries and stored procedures.

interface

The function hex takes a sequence of values and writes hexadecimal characters. There are three different interfaces, differing only in how the input sequence is specified.

The first one takes an iterator pair. The second one takes a pointer to the start of a zero-terminated sequence, such as a c string, and the third takes a range as defined by the Boost.Range library.

template <typename InputIterator, typename OutputIterator>
OutputIterator hex ( InputIterator first, InputIterator last, OutputIterator out );

template <typename T, typename OutputIterator>
OutputIterator hex ( const T *ptr, OutputIterator out );

template <typename Range, typename OutputIterator>
OutputIterator hex ( const Range &r, OutputIterator out );

hex writes only values in the range '0'..'9' and 'A'..'F', but is not limited to character output. The output iterator could refer to a wstring, or a vector of integers, or any other integral type.

The function unhex takes the output of hex and turns it back into a sequence of values.

The input parameters for the different variations of unhex are the same as hex.

template <typename InputIterator, typename OutputIterator>
OutputIterator unhex ( InputIterator first, InputIterator last, OutputIterator out );

template <typename T, typename OutputIterator>
OutputIterator unhex ( const T *ptr, OutputIterator out );

template <typename Range, typename OutputIterator>
OutputIterator unhex ( const Range &r, OutputIterator out );

Error Handling

The header 'hex.hpp' defines three exception classes:

struct hex_decode_error: virtual boost::exception, virtual std::exception {};
struct not_enough_input : public hex_decode_error;
struct non_hex_input : public hex_decode_error;

If the input to unhex does not contain an "even number" of hex digits, then an exception of type boost::algorithm::not_enough_input is thrown.

If the input to unhex contains any non-hexadecimal characters, then an exception of type boost::algorithm::non_hex_input is thrown.

If you want to catch all the decoding errors, you can catch exceptions of type boost::algorithm::hex_decode_error.

Examples

Assuming that out is an iterator that accepts char values, and wout accepts wchar_t values (and that sizeof ( wchar_t ) == 2)

hex ( "abcdef", out )  --> "616263646566"
hex ( "32", out )     --> "3332"
hex ( "abcdef", wout ) --> "006100620063006400650066"
hex ( "32", wout )    --> "00330032"

unhex ( "616263646566", out )  --> "abcdef"
unhex ( "3332", out )          --> "32"
unhex ( "616263646566", wout ) --> "\6162\6364\6566"	( i.e, a 3 character string )
unhex ( "3332", wout )         --> "\3233"				( U+3332, SQUARE HUARADDO )

unhex ( "3", out )            --> Error - not enough input
unhex ( "32", wout )          --> Error - not enough input

unhex ( "ACEG", out )         --> Error - non-hex input

Iterator Requirements

hex and unhex work on all iterator types.

Complexity

All of the variants of hex and unhex run in O(N) (linear) time; that is, that is, they process each element in the input sequence once.

Exception Safety

All of the variants of hex and unhex take their parameters by value or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee. However, when working on input iterators, if an exception is thrown, the input iterators will not be reset to their original values (i.e, the characters read from the iterator cannot be un-read)

Notes

The header file 'is_palindrome.hpp' contains six variants of a single algorithm, is_palindrome. The algorithm tests the sequence and returns true if the sequence is a palindrome; i.e, it is identical when traversed either backwards or frontwards.

The routine is_palindrome takes a sequence and, optionally, a predicate. It will return true if the predicate returns true for tested elements by algorithm in the sequence.

The routine come in 6 forms; the first one takes two iterators to define the range. The second form takes two iterators to define the range and a predicate. The third form takes a single range parameter, and uses Boost.Range to traverse it. The fourth form takes a single range parameter ( uses Boost.Range to traverse it) and a predicate. The fifth form takes a single C-string and a predicate. The sixth form takes a single C-string.

interface

The function is_palindrome returns true if the predicate returns true any tested by algorithm items in the sequence. There are six versions: 1) takes two iterators. 2) takes two iterators and a predicate. 3) takes a range. 4) takes a range and a predicate. 5) takes a C-string and a predicate. 6) takes a C-string.

template<typename BidirectionalIterator>
	bool is_palindrome ( BidirectionalIterator begin, BidirectionalIterator end );
template<typename BidirectionalIterator, typename Predicate>
	bool is_palindrome ( BidirectionalIterator begin, BidirectionalIterator end, Predicate p );
template<typename Range>
	bool is_palindrome ( const Range &r );
template<typename Range, typename Predicate>
	bool is_palindrome ( const Range &r, Predicate p );
template<typename Predicate>
	bool is_palindrome ( const char* str, Predicate p );
bool is_palindrome(const char* str);

Examples

Given the containers: const std::list<int> empty, const std::vector<char> singleElement{'z'}, int oddNonPalindrome[] = {3,2,2}, const int oddPalindrome[] = {1,2,3,2,1}, const int evenPalindrome[] = {1,2,2,1}, int evenNonPalindrome[] = {1,4,8,8}, then

is_palindrome(empty))  --> true //empty range                                                                       
is_palindrome(singleElement))  --> true
is_palindrome(std::begin(oddNonPalindrome), std::end(oddNonPalindrome))) --> false
is_palindrome(std::begin(evenPalindrome), std::end(evenPalindrome))) --> true
is_palindrome(empty.begin(), empty.end(), functorComparator())) --> true //empty range                             
is_palindrome(std::begin(oddNonPalindrome), std::end(oddNonPalindrome), funcComparator<int>)) --> false
is_palindrome(std::begin(oddPalindrome), std::end(oddPalindrome)) --> true
is_palindrome(evenPalindrome, std::equal_to<int>())) --> true
is_palindrome(std::begin(evenNonPalindrome), std::end(evenNonPalindrome)) --> false
is_palindrome("a") --> true
is_palindrome("aba", std::equal_to<char>()) --> true

Iterator Requirements

is_palindrome work on Bidirectional and RandomAccess iterators.

Complexity

All of the variants of is_palindrome run in O(N) (linear) time; that is, they compare against each element in the list once. If any of the comparisons not succeed, the algorithm will terminate immediately, without examining the remaining members of the sequence.

Exception Safety

All of the variants of is_palindrome take their parameters by value, const pointer or const reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.

Notes