2.6.0
Freundlich's C++ toolkit
Classes | Typedefs | Enumerations | Functions
fcppt.algorithm

Description

General-purpose algorithms.

C++'s standard algorithms use iterators both for function inputs and outputs. This makes functional programming hard in two ways:

This module provides a collection of very common algorithms over ranges that fix both problems. Prominent examples are fcppt::algorithm::fold and fcppt::algorithm::map. To get the most out of them, these can be used in conjunction with a range library (like Boost.Range).

Classes

struct  fcppt::algorithm::loop_break_impl< Range, Enable >
 Customization point for ranges. More...
 

Typedefs

template<typename Range >
using fcppt::algorithm::range_element_type = decltype(*std::declval< Range >().begin())
 The type of a range element. More...
 

Enumerations

enum  fcppt::algorithm::update_action { fcppt::algorithm::update_action::keep, fcppt::algorithm::update_action::remove }
 Update action for container iteration. More...
 

Functions

template<typename Range , typename Pred >
bool fcppt::algorithm::all_of (Range const &_range, Pred const &_pred)
 Checks if a given predicate is true for all elements of a range. More...
 
template<typename DestContainer , typename Source >
void fcppt::algorithm::append (DestContainer &_dest, Source &&_src)
 Appends two sequences. More...
 
template<typename TargetArray , typename SourceType1 , typename SourceType2 , std::size_t SourceCount, typename Function >
TargetArray fcppt::algorithm::array_binary_map (std::array< SourceType1, SourceCount > const &_source1, std::array< SourceType2, SourceCount > const &_source2, Function const &_function)
 Applies a function to each pair of elements of two arrays and returns an array containing the results. More...
 
template<typename Array , typename Function >
Array fcppt::algorithm::array_init (Function const &_function)
 Constructs an array by calling a function with static indices. More...
 
template<typename Array >
Array fcppt::algorithm::array_init_const (typename Array::value_type const &_value)
 Constructs an array from a value. More...
 
template<typename Array , typename Function >
Array fcppt::algorithm::array_init_move (Function const &_function)
 Constructs an array by calling a function for every element. More...
 
template<typename TargetArray , typename SourceType , std::size_t SourceCount, typename Function >
TargetArray fcppt::algorithm::array_map (std::array< SourceType, SourceCount > const &_source, Function const &_function)
 Applies a function to every element of an array and returns an array of the results. More...
 
template<typename SourceType , std::size_t SourceCount>
std::array< SourceType, SourceCount+1u > fcppt::algorithm::array_push_back (std::array< SourceType, SourceCount > const &_source, SourceType const &_element)
 Pushes a new element to the back of an array. More...
 
template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::binary_search (Range &&_range, T const &_value)
 Finds an element by binary search. More...
 
template<typename Range , typename T >
bool fcppt::algorithm::contains (Range const &_range, T const &_value)
 Checks if a given value is inside a range. More...
 
template<typename Range , typename Pred >
bool fcppt::algorithm::contains_if (Range const &_range, Pred const &_pred)
 Checks if a given value is inside a range, using a predicate. More...
 
template<typename Range1 , typename Range2 >
bool fcppt::algorithm::equal (Range1 const &_range1, Range2 const &_range2)
 Compares two ranges for equality. More...
 
template<typename Range , typename T >
boost::iterator_range< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::equal_range (Range &&_range, T const &_value)
 Returns the equal range of a given range and a value. More...
 
template<typename Range , typename Function >
auto fcppt::algorithm::find_by_opt (Range &&_range, Function const &_function) -> decltype(_function(*_range.begin()))
 Optionally finds an element and transforms it. More...
 
template<typename Range , typename Comp >
fcppt::optional::object< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::find_if_opt (Range &&_range, Comp const &_comp)
 Like std::find_if but returns an empty optional on failure. More...
 
template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::find_opt (Range &&_range, T const &_value)
 Like std::find but returns an empty optional on failure. More...
 
template<typename Range , typename State , typename Function >
State fcppt::algorithm::fold (Range &&_range, State _state, Function _function)
 Folds a range into a value. More...
 
template<typename Range , typename State , typename Function >
State fcppt::algorithm::fold_break (Range &&_range, State _state, Function _function)
 Folds a range into a value, can break out early. More...
 
template<typename TargetContainer , typename Function >
TargetContainer fcppt::algorithm::generate_n (std::size_t const _count, Function const &_function)
 Generates a container by calling a function a number of times. More...
 
template<typename Range , typename T >
fcppt::optional::object< typename Range::size_type > fcppt::algorithm::index_of (Range const &_range, T const &_value)
 Returns the index of the first element found in a sequence. More...
 
template<typename Container , typename... Args>
std::decay< Container >::type fcppt::algorithm::join (Container &&_first, Args &&..._args)
 Joins two containers. More...
 
template<typename Range >
Range::value_type fcppt::algorithm::join_strings (Range const &_range, typename Range::value_type const &_delim)
 Joins a range of strings, using a delimiter. More...
 
template<typename Range >
boost::range_size< Range >::type fcppt::algorithm::levenshtein (Range const &source, Range const &target)
 Calculates the Levenshtein distance. More...
 
template<typename Range , typename Body >
void fcppt::algorithm::loop (Range &&_range, Body const &_body)
 Iterates through a range. More...
 
template<typename Range , typename Body >
void fcppt::algorithm::loop_break (Range &&_range, Body const &_body)
 Iterates through a range with the ability to break out of the loop. More...
 
template<typename TargetContainer , typename SourceRange , typename Function >
TargetContainer fcppt::algorithm::map (SourceRange &&_source, Function const &_function)
 Transforms a range to another container by applying a function to every element. More...
 
template<typename TargetContainer , typename Range , typename Function >
TargetContainer fcppt::algorithm::map_concat (Range &&_range, Function const &_function)
 Maps a range to other sequences and joins them. More...
 
template<typename Map , typename UpdateAction >
void fcppt::algorithm::map_iteration (Map &_map, UpdateAction const &_update_action)
 Iterates over a map with the possibility of erasing elements. More...
 
template<typename Map , typename UpdateAction >
void fcppt::algorithm::map_iteration_second (Map &_map, UpdateAction const &_update_action)
 Iterates over a map with the possibility of erasing elements, passing second. More...
 
template<typename TargetContainer , typename Source , typename Function >
TargetContainer fcppt::algorithm::map_optional (Source &&_source, Function const &_function)
 Transforms a range to another container by applying a function to every element, only inserting the results that are not empty optionals. More...
 
template<typename Container >
bool fcppt::algorithm::remove (Container &_container, typename Container::const_reference _element)
 Removes all occurrences of a value from a container. More...
 
template<typename Container , typename Predicate >
bool fcppt::algorithm::remove_if (Container &_container, Predicate const &_predicate)
 Removes all elements from a container matching a predicate. More...
 
template<typename Count , typename Function >
void fcppt::algorithm::repeat (Count const _count, Function const &_function)
 Calls a function a number of times. More...
 
template<typename Container >
std::remove_reference< Container >::type fcppt::algorithm::reverse (Container &&_container)
 Reverses a container. More...
 
template<typename Sequence , typename UpdateAction >
void fcppt::algorithm::sequence_iteration (Sequence &_sequence, UpdateAction const &_update_action)
 Iterates over a sequence with the possibility of erasing elements. More...
 
template<typename Set >
Set fcppt::algorithm::set_difference (Set const &_a, Set const &_b)
 Returns the difference of two sets. More...
 
template<typename Set >
Set fcppt::algorithm::set_intersection (Set const &_a, Set const &_b)
 Returns the intersection of two sets. More...
 
template<typename Set >
Set fcppt::algorithm::set_union (Set const &_a, Set const &_b)
 Returns the union of two sets. More...
 
template<typename Tuple , typename AnchorFunction , typename ElementFunction >
decltype(auto) fcppt::algorithm::vararg_map (Tuple &&_tuple, AnchorFunction const &_anchor, ElementFunction const &_element)
 Map a fusion sequence to variadic arguments. More...
 

Typedef Documentation

◆ range_element_type

template<typename Range >
using fcppt::algorithm::range_element_type = typedef decltype( *std::declval< Range >().begin() )

The type of a range element.

Depending on the range, this can be a reference, const reference or an object type.

Enumeration Type Documentation

◆ update_action

Update action for container iteration.

Enumerator
keep 

Keep the element.

remove 

Remove the element.

Function Documentation

◆ all_of()

template<typename Range , typename Pred >
bool fcppt::algorithm::all_of ( Range const &  _range,
Pred const &  _pred 
)
inline

Checks if a given predicate is true for all elements of a range.

Template Parameters
PredA function callable as bool (Range::value_type).

◆ append()

template<typename DestContainer , typename Source >
void fcppt::algorithm::append ( DestContainer &  _dest,
Source &&  _src 
)
inline

Appends two sequences.

Appends the sequence _src to _dest.

Example:

std::vector<int> v{1,2,3};
std::vector<int> w{4,5};
v,
w);
// Now v contains: 1,2,3,4,5
Template Parameters
DestContainerMust have an insert function taking three iterators (like the std containers all do).

◆ array_binary_map()

template<typename TargetArray , typename SourceType1 , typename SourceType2 , std::size_t SourceCount, typename Function >
TargetArray fcppt::algorithm::array_binary_map ( std::array< SourceType1, SourceCount > const &  _source1,
std::array< SourceType2, SourceCount > const &  _source2,
Function const &  _function 
)

Applies a function to each pair of elements of two arrays and returns an array containing the results.

Calls _function(element1, element2) for every element1 of _source1 and element2 of _source2.

Template Parameters
TargetArrayMust be a std::array.
SourceCountThe number of elements in the source arrays.
FunctionMust be a function callable as TargetArray::value_type (SourceType1, SourceType2).

◆ array_init()

template<typename Array , typename Function >
Array fcppt::algorithm::array_init ( Function const &  _function)
inline

Constructs an array by calling a function with static indices.

Constructs an array of type Array by calling _function(std::integral_constant<std::size_t, Index>) for every index.

Template Parameters
ArrayMust be a std::array
FunctionMust be a function callable as Array::value_type (std::integral_constant<std::size_t, I>).

◆ array_init_const()

template<typename Array >
Array fcppt::algorithm::array_init_const ( typename Array::value_type const &  _value)
inline

Constructs an array from a value.

Constructs an array of type Array by initializing every element with _value.

Template Parameters
ArrayMust be a std::array.

◆ array_init_move()

template<typename Array , typename Function >
Array fcppt::algorithm::array_init_move ( Function const &  _function)
inline

Constructs an array by calling a function for every element.

Constructs an array of type Array by initializing every element with _function().

Template Parameters
ArrayMust be a std::array
FunctionA function callable as Array::value_type ().

◆ array_map()

template<typename TargetArray , typename SourceType , std::size_t SourceCount, typename Function >
TargetArray fcppt::algorithm::array_map ( std::array< SourceType, SourceCount > const &  _source,
Function const &  _function 
)
inline

Applies a function to every element of an array and returns an array of the results.

Calls _function(element) for every element of _source.

Example:

typedef
std::array<int,3>
three_ints;
three_ints const a{{ 1,2,3 }};
three_ints const b(
fcppt::algorithm::array_map<three_ints>(
a,
[](int const _arg) { return _arg * 3; }
)
);
// b now contains: 3, 6, 9
Template Parameters
TargetArrayMust be a std::array
SourceTypeCan be any type
SourceCountThe number of elements in the source array
FunctionMust be a function callable as TargetArray::value_type (SourceType).

◆ array_push_back()

template<typename SourceType , std::size_t SourceCount>
std::array< SourceType, SourceCount + 1u> fcppt::algorithm::array_push_back ( std::array< SourceType, SourceCount > const &  _source,
SourceType const &  _element 
)

Pushes a new element to the back of an array.

Pushes _element to the back of _source.

◆ binary_search()

template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::binary_search ( Range &&  _range,
T const &  _value 
)

Finds an element by binary search.

If there is exactly one element that is uncomparable to _value, returns an iterator to that element. Otherwise, returns the empty optional.

Template Parameters
TMust be less-than comparable to the range's value type.

◆ contains()

template<typename Range , typename T >
bool fcppt::algorithm::contains ( Range const &  _range,
T const &  _value 
)
inline

Checks if a given value is inside a range.

Template Parameters
TMust be equality comparable to the range's value type.

◆ contains_if()

template<typename Range , typename Pred >
bool fcppt::algorithm::contains_if ( Range const &  _range,
Pred const &  _pred 
)
inline

Checks if a given value is inside a range, using a predicate.

Template Parameters
PredA function callable as bool (Range::value_type).

◆ equal()

template<typename Range1 , typename Range2 >
bool fcppt::algorithm::equal ( Range1 const &  _range1,
Range2 const &  _range2 
)
inline

Compares two ranges for equality.

◆ equal_range()

template<typename Range , typename T >
boost::iterator_range< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::equal_range ( Range &&  _range,
T const &  _value 
)
inline

Returns the equal range of a given range and a value.

Template Parameters
TMust be less-than comparable to the range's value type.

◆ find_by_opt()

template<typename Range , typename Function >
auto fcppt::algorithm::find_by_opt ( Range &&  _range,
Function const &  _function 
) -> decltype( _function( *_range.begin() ) )
inline

Optionally finds an element and transforms it.

Returns the first element in _range for which _function does not return an empty optional, if there is any. Otherwise, returns the empty optional.

Template Parameters
FunctionA function callable as fcppt::optional::object<R> (Range::value_type), where R is the result type.

◆ find_if_opt()

template<typename Range , typename Comp >
fcppt::optional::object< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::find_if_opt ( Range &&  _range,
Comp const &  _comp 
)
inline

Like std::find_if but returns an empty optional on failure.

Template Parameters
CompMust be a function callable as bool (Range::value_type).

◆ find_opt()

template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< typename std::remove_reference< Range >::type >> fcppt::algorithm::find_opt ( Range &&  _range,
T const &  _value 
)

Like std::find but returns an empty optional on failure.

Template Parameters
TMust be equality-comparable to Range::value_type.

◆ fold()

template<typename Range , typename State , typename Function >
State fcppt::algorithm::fold ( Range &&  _range,
State  _state,
Function  _function 
)
inline

Folds a range into a value.

Like fold_left in a functional programming language, this function starts with _state as cur_state, and calls cur_state = _function(element, cur_state) for every element of _range.

Template Parameters
StateHas to be movable
FunctionMust be callable as State (Range::value_type, State).

◆ fold_break()

template<typename Range , typename State , typename Function >
State fcppt::algorithm::fold_break ( Range &&  _range,
State  _state,
Function  _function 
)
inline

Folds a range into a value, can break out early.

Let [e_1,...,e_n] be the input range and s_0 = _state.

This function calls (l_i, s_i) = function(e_i,s{i-1}) for i = 1,...,x where x <= n is the largest number such that l_j = loop::continue_ for all 1 <= j < x.

Template Parameters
StateHas to be movable
FunctionMust be callable as std::pair<fcppt::loop, State> (Range::value_type,State).

◆ generate_n()

template<typename TargetContainer , typename Function >
TargetContainer fcppt::algorithm::generate_n ( std::size_t const  _count,
Function const &  _function 
)

Generates a container by calling a function a number of times.

Calls _function _count times and collects the results into a container.

Template Parameters
FunctionA function callable as TargetContainer::value_type().

◆ index_of()

template<typename Range , typename T >
fcppt::optional::object< typename Range::size_type> fcppt::algorithm::index_of ( Range const &  _range,
T const &  _value 
)
inline

Returns the index of the first element found in a sequence.

Searches for _value in _range and returns the index of the first occurrence if there is any, otherwise returns the empty optional.

Template Parameters
RangeA random access range.
TA type equality-comparable to the ranges's value type.

◆ join()

template<typename Container , typename... Args>
std::decay< Container>::type fcppt::algorithm::join ( Container &&  _first,
Args &&...  _args 
)
inline

Joins two containers.

Joins containers _first and all containers from _args, by inserting the containers from _args into _first.

Parameters
_firstThe left container.
_argsThe other containers, which will be inserted into the left container.
Template Parameters
ContainerA container class that supports insert of iterator ranges.

◆ join_strings()

template<typename Range >
Range::value_type fcppt::algorithm::join_strings ( Range const &  _range,
typename Range::value_type const &  _delim 
)

Joins a range of strings, using a delimiter.

Joins _range, inserting _delim between every pair of consecutive elements.

Example:

std::vector<std::string> strings{
"ab",
"cd",
"efg"
};
std::string const result{
strings,
","
)
};
// Outputs "ab,cd,efg"
std::cout << result << "\n";
Template Parameters
RangeA range of strings.

◆ levenshtein()

template<typename Range >
boost::range_size<Range>::type fcppt::algorithm::levenshtein ( Range const &  source,
Range const &  target 
)

Calculates the Levenshtein distance.

See http://en.wikipedia.org/wiki/Levenshtein_distance for an explanation of the algorithm.

Precondition
  • Range::size_type and Range::value_type exist
  • bool Range::empty() const exists
  • size_type Range::size() const exists
  • Range::operator[] exists
  • Range::value_type has to have an operator==
Note
The code is taken quite literally from: http://www.merriampark.com/ldcpp.htm

◆ loop()

template<typename Range , typename Body >
void fcppt::algorithm::loop ( Range &&  _range,
Body const &  _body 
)
inline

Iterates through a range.

Iterates through _range, calling _body for every element of the range. The implementation for a specific range type is handled by fcppt::algorithm::loop_break_impl.

Template Parameters
BodyA function callable as void (T) for every type T in Range.

◆ loop_break()

template<typename Range , typename Body >
void fcppt::algorithm::loop_break ( Range &&  _range,
Body const &  _body 
)
inline

Iterates through a range with the ability to break out of the loop.

Iterates through _range, calling _body for every element of the range as long as _function returns fcppt::loop::continue_. The implementation for a specific range type is handled by fcppt::algorithm::loop_break_impl.

Template Parameters
BodyA function callable as fcppt::loop (T) for every type T in Range

◆ map()

template<typename TargetContainer , typename SourceRange , typename Function >
TargetContainer fcppt::algorithm::map ( SourceRange &&  _source,
Function const &  _function 
)

Transforms a range to another container by applying a function to every element.

For every element e in _source, _function(e) is inserted into the result container.

Note
As an optimization the result container has its capacity set to the source range's size at the start, if possible. For this to work, the result container needs a reserve function, and the source range needs a size function or must be a random access range.
Template Parameters
FunctionA function callable as TargetContainer::value_type (SourceRange::value_type).

◆ map_concat()

template<typename TargetContainer , typename Range , typename Function >
TargetContainer fcppt::algorithm::map_concat ( Range &&  _range,
Function const &  _function 
)

Maps a range to other sequences and joins them.

For every element in _range (a_1, ..., a_n), _function(a_1), ..., _function(a_n) is called, yielding (r_1, ..., r_n). The result is join(r_1, r_2, ..., r_n).

Template Parameters
FunctionA function callable as TargetContainer (Range::value_type).

◆ map_iteration()

template<typename Map , typename UpdateAction >
void fcppt::algorithm::map_iteration ( Map &  _map,
UpdateAction const &  _update_action 
)

Iterates over a map with the possibility of erasing elements.

Iterates over _map, applying _update_action to each element. If _update_action returns fcppt::algorithm::update_action::remove, the element is deleted from the map.

Template Parameters
MapA map-like container.
UpdateActionA function callable as fcppt::algorithm::update_action (Map::value_type).

◆ map_iteration_second()

template<typename Map , typename UpdateAction >
void fcppt::algorithm::map_iteration_second ( Map &  _map,
UpdateAction const &  _update_action 
)

Iterates over a map with the possibility of erasing elements, passing second.

Iterates over _map, applying _update_action to the mapped object of each element. If _update_action returns fcppt::algorithm::update_action::remove, the element is removed from the map.

Template Parameters
MapA map-like container.
UpdateActionA function callable as fcppt::algorithm::update_action (Map::mapped_type).

◆ map_optional()

template<typename TargetContainer , typename Source , typename Function >
TargetContainer fcppt::algorithm::map_optional ( Source &&  _source,
Function const &  _function 
)

Transforms a range to another container by applying a function to every element, only inserting the results that are not empty optionals.

For every element e in _source, _function(e) is called. If the result is not an empty optional, it is inserted into the result container.

Template Parameters
FunctionA function callable as fcppt::optional::object<TargetContainer::value_type> (Source::value_type).

◆ remove()

template<typename Container >
bool fcppt::algorithm::remove ( Container &  _container,
typename Container::const_reference  _element 
)
inline

Removes all occurrences of a value from a container.

Removes all elements from a _container equal to _element.

Returns
true if something has been removed, false otherwise.

◆ remove_if()

template<typename Container , typename Predicate >
bool fcppt::algorithm::remove_if ( Container &  _container,
Predicate const &  _predicate 
)

Removes all elements from a container matching a predicate.

Removes all elements from _container matching _predicate.

Template Parameters
PredicateA function callable as bool (Container::value_type).
Returns
true if something has been removed, false otherwise.

◆ repeat()

template<typename Count , typename Function >
void fcppt::algorithm::repeat ( Count const  _count,
Function const &  _function 
)

Calls a function a number of times.

Calls _function _count times.

Template Parameters
CountAn integer type
FunctionA function callable as void ().

◆ reverse()

template<typename Container >
std::remove_reference< Container>::type fcppt::algorithm::reverse ( Container &&  _container)
inline

Reverses a container.

Template Parameters
ContainerMust be a bidirectional container

◆ sequence_iteration()

template<typename Sequence , typename UpdateAction >
void fcppt::algorithm::sequence_iteration ( Sequence &  _sequence,
UpdateAction const &  _update_action 
)

Iterates over a sequence with the possibility of erasing elements.

Iterates over _sequence, applying _update_action to each element. If _update_action returns fcppt::algorithm::update_action::remove, the element is removed from the sequence.

Template Parameters
UpdateActionA function callable as fcppt::algorithm::update_action (Sequence::value_type).

◆ set_difference()

template<typename Set >
Set fcppt::algorithm::set_difference ( Set const &  _a,
Set const &  _b 
)

Returns the difference of two sets.

Template Parameters
SetMust be an associative container

◆ set_intersection()

template<typename Set >
Set fcppt::algorithm::set_intersection ( Set const &  _a,
Set const &  _b 
)

Returns the intersection of two sets.

Template Parameters
SetMust be an associative container

◆ set_union()

template<typename Set >
Set fcppt::algorithm::set_union ( Set const &  _a,
Set const &  _b 
)

Returns the union of two sets.

Template Parameters
SetMust be an associative container

◆ vararg_map()

template<typename Tuple , typename AnchorFunction , typename ElementFunction >
decltype( auto ) fcppt::algorithm::vararg_map ( Tuple &&  _tuple,
AnchorFunction const &  _anchor,
ElementFunction const &  _element 
)
inline

Map a fusion sequence to variadic arguments.

Let _tuple be (v_1,...,v_n). The result is _anchor(_element(v_1),...,_element(v_n)).

Note
The main purpose of this function is that the mapping function _element is called in order of the arguments, which is impossible to do with boost.fusion alone.
Template Parameters
TupleA fusion sequence.