Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext

is_palindrome

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

PrevUpHomeNext