Algorithms

Description

Templates for algorithms used to manipulate data.

Functions
template<typename T >
unsigned int	Common::distance (T *first, T *last)
template<typename T >
unsigned int	Common::distance (T first, T last)
template<typename T >
T *	Common::sortChoosePivot (T *first, T *last)
template<typename T >
T	Common::sortChoosePivot (T first, T last)
template<typename T , class StrictWeakOrdering >
T	Common::sortPartition (T first, T last, T pivot, StrictWeakOrdering &comp)
template<class T >
T	Common::gcd (T a, T b)
template<class T >
T	Common::nextHigher2 (T v)
template<class It , class Dat >
void	Common::replace (It begin, It end, const Dat &original, const Dat &replaced)
template<class It , class T >
It	Common::remove (It first, It last, const T &val)
template<typename RandomIt , typename V , typename Comp = Less<V>>
RandomIt	Common::lowerBound (RandomIt first, RandomIt last, const V &val, Comp comp={})
template<typename RandomIt , typename V , typename Comp = Less<V>>
RandomIt	Common::upperBound (RandomIt first, RandomIt last, const V &val, Comp comp={})

Copy templates
template<class In , class Out >
Out	Common::copy (In first, In last, Out dst)
template<class In , class Out >
Out	Common::copy_backward (In first, In last, Out dst)
template<class In , class Out , class Op >
Out	Common::copy_if (In first, In last, Out dst, Op op)

Fill templates
template<class Value >
signed char *	Common::fill (signed char *first, signed char *last, Value val)
template<class Value >
unsigned char *	Common::fill (unsigned char *first, unsigned char *last, Value val)
template<class Value >
char *	Common::fill (char *first, char *last, Value val)

Range templates
template<class In , class Value >
In	Common::fill (In first, In last, const Value &val)
template<class In , class T >
In	Common::find (In first, In last, const T &v)
template<class In , class Pred >
In	Common::find_if (In first, In last, Pred p)
template<class In , class Op >
Op	Common::for_each (In first, In last, Op f)

Sorting templates
template<typename T , class StrictWeakOrdering >
void	Common::sort (T first, T last, StrictWeakOrdering comp)
template<typename T >
void	Common::sort (T *first, T *last)
template<class T >
void	Common::sort (T first, T last)

Function Documentation

copy()

template<class In , class Out >

Out Common::copy	(	In	first,
		In	last,
		Out	dst
	)

Copy data from the range [first, last) to [dst, dst + (last - first)).

The function requires the range [dst, dst + (last - first)) to be valid. It also requires dst not to be in the range [first, last).

copy_backward()

template<class In , class Out >

Out Common::copy_backward	(	In	first,
		In	last,
		Out	dst
	)

Copy data from the range [first, last) to [dst - (last - first), dst).

The function requires the range [dst - (last - first), dst) to be valid. It also requires dst not to be in the range [first, last).

Unlike copy, copy_backward copies the data from the end to the beginning.

copy_if()

template<class In , class Out , class Op >

Out Common::copy_if	(	In	first,
		In	last,
		Out	dst,
		Op	op
	)

Copy data from the range [first, last) to [dst, dst + (last - first)).

The function requires the range [dst, dst + (last - first)) to be valid. It also requires dst not to be in the range [first, last).

Unlike copy or copy_backward, it does not copy all data. It only copies a data element when operator() of the op parameter returns true for the passed data element.

fill() [1/4]

template<class Value >

signed char* Common::fill	(	signed char *	first,
		signed char *	last,
		Value	val
	)

A 'fill' template for signed char arrays.

Since C++ does not currently support partial specialized template functions, this solution is implemented. With this template, the usage of memset is assured, which is faster than a simple loop like for the generic 'fill'.

fill() [2/4]

template<class Value >

unsigned char* Common::fill	(	unsigned char *	first,
		unsigned char *	last,
		Value	val
	)

A 'fill' template for unsigned char arrays.

Since C++ does not currently support partial specialized template functions, this solution is implemented. With this template, the usage of memset is assured, which is faster than a simple loop like for the generic 'fill'.

fill() [3/4]

template<class Value >

char* Common::fill	(	char *	first,
		char *	last,
		Value	val
	)

A 'fill' template for char arrays.

Since C++ does not currently support partial specialized template functions, this solution is implemented. With this template, the usage of memset is assured, which is faster than a simple loop like for the generic 'fill'.

fill() [4/4]

template<class In , class Value >

In Common::fill	(	In	first,
		In	last,
		const Value &	val
	)

Set all elements in the range [first, last) to val.

find()

template<class In , class T >

In Common::find	(	In	first,
		In	last,
		const T &	v
	)

Find the first data value in the range [first, last) matching v. For data comparison, it uses operator == of the data elements.

find_if()

template<class In , class Pred >

In Common::find_if	(	In	first,
		In	last,
		Pred	p
	)

Find the first data value in the range [first, last), for which the specified predicate p returns true.

for_each()

template<class In , class Op >

Op Common::for_each	(	In	first,
		In	last,
		Op	f
	)

Apply the function f on all elements from the range [first, last). The processing order is from beginning to end.

sort() [1/3]

template<typename T , class StrictWeakOrdering >

void Common::sort	(	T	first,
		T	last,
		StrictWeakOrdering	comp
	)

Simple sorting function, modeled after std::sort.

This function compares data with the given comparator object comp.

Like std::sort, this is not guaranteed to be stable.

Two quotes from Wikipedia about stability:

Stable sorting algorithms maintain the relative order of records with equal keys.

Unstable sorting algorithms may change the relative order of records with equal keys, but stable sorting algorithms never do so.

For more information, see: http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Note

Currently, this implementation is unstable.

Parameters

[in]	first	First element to sort.
[in]	last	Last element to sort.
[in]	comp	Comparator object.

sort() [2/3]

template<typename T >

void Common::sort	(	T *	first,
		T *	last
	)

Simple sorting function, modeled after std::sort.

Parameters

[in]	first	First element to sort.
[in]	last	Last element to sort.

sort() [3/3]

template<class T >

void Common::sort	(	T	first,
		T	last
	)

Simple sorting function, modeled after std::sort.

Parameters

[in]	first	First element to sort.
[in]	last	Last element to sort.

gcd()

template<class T >

T Common::gcd	(	T	a,
		T	b
	)

Euclidean algorithm to compute the greatest common divisor.

nextHigher2()

template<class T >

T Common::nextHigher2

(

T

v

)

Get the next highest power of 2.

replace()

template<class It , class Dat >

void Common::replace	(	It	begin,
		It	end,
		const Dat &	original,
		const Dat &	replaced
	)

Replacement algorithm for iterables.

Replaces all occurrences of "original" in [begin, end) with occurrences of "replaced".

Parameters

[in,out]	begin	First element to be examined.
[in]	end	Last element in the subsection. Not examined.
[in]	original	Elements to be replaced.
[in]	replaced	Element to replace occurrences of original.

Note

Usage examples and unit tests may be found in "test/common/algorithm.h"

remove()

template<class It , class T >

It Common::remove	(	It	first,
		It	last,
		const T &	val
	)

Removes all elements that are equal to value from the range [first, last). This function is the equivalent of std::remove.

Parameters

[in]	first	Iterator to the first position to be examined.
[in]	last	Iterator to the last position.
[in]	val	Value to be removed.

Returns

An iterator to the new end of the range.

lowerBound()

template<typename RandomIt , typename V , typename Comp = Less<V>>

RandomIt Common::lowerBound	(	RandomIt	first,
		RandomIt	last,
		const V &	val,
		Comp	comp = {}
	)

Returns an iterator to the first item in the range [first, last) for which comp(item, val) (item < val by default) is false, or last if no such item is found. Items in the range [first, last) need to be partitioned by comp(item, val), that is, all items for which comp(item, val) is true (items that are less than val) come before all items for which the expression is false (items that are bigger than or equal to val). A sorted range conforms to the requirement.

This function is the equivalent of std::lower_bound for random access iterators.

upperBound()

template<typename RandomIt , typename V , typename Comp = Less<V>>

RandomIt Common::upperBound	(	RandomIt	first,
		RandomIt	last,
		const V &	val,
		Comp	comp = {}
	)

Returns an iterator to the first item in the range [first, last) for which comp(val, item) (val < item by default) is true, or last if no such item is found. Items in the range [first, last) need to be partitioned by !comp(val, item), that is, all items for which !comp(val, item) is true (items that are less than or equal to val), come before all items for which the expression is false (items that are greater than val). A sorted range conforms to the requirement.

This function is the equivalent of std::upper_bound for random access iterators.