4.4.1
Freundlich's C++ toolkit
Loading...
Searching...
No Matches
Classes | Typedefs | Enumerations | Functions
fcppt.algorithm
fcppt

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.
 

Enumerations

enum class  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.
 
template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > fcppt::algorithm::binary_search (Range &&_range, T const &_value)
 Finds an element by binary search.
 
template<typename Range , typename T >
bool fcppt::algorithm::contains (Range const &_range, T const &_value)
 Checks if a given value is inside a range.
 
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.
 
template<typename Range1 , typename Range2 >
bool fcppt::algorithm::equal (Range1 const &_range1, Range2 const &_range2)
 Compares two ranges for equality.
 
template<typename Range , typename T >
fcppt::iterator::range< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > fcppt::algorithm::equal_range (Range &&_range, T const &_value)
 Returns the equal range of a given range and a value.
 
template<typename Result , typename Range , typename Function >
fcppt::optional::object< Result > fcppt::algorithm::find_by_opt (Range &&_range, Function const &_function)
 Optionally finds an element and transforms it.
 
template<typename Range , typename Comp >
fcppt::optional::object< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > fcppt::algorithm::find_if_opt (Range &&_range, Comp const &_comp)
 Like std::find_if but returns an empty optional on failure.
 
template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > fcppt::algorithm::find_opt (Range &&_range, T const &_value)
 Like std::find but returns an empty optional on failure.
 
template<typename Range , typename State , typename Function >
State fcppt::algorithm::fold (Range &&_range, State _state, Function _function)
 Folds a range into a value.
 
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.
 
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.
 
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.
 
template<typename Range >
fcppt::type_traits::value_type< Range > fcppt::algorithm::join_strings (Range const &_range, fcppt::type_traits::value_type< Range > const &_delim)
 Joins a range of strings, using a delimiter.
 
template<typename Range , typename Body >
void fcppt::algorithm::loop (Range &&_range, Body const &_body)
 Iterates through a range.
 
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.
 
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.
 
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.
 
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.
 
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.
 
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.
 
template<typename Container >
bool fcppt::algorithm::remove (Container &_container, typename Container::const_reference _element)
 Removes all occurrences of a value from a container.
 
template<typename Container , typename Predicate >
bool fcppt::algorithm::remove_if (Container &_container, Predicate const &_predicate)
 Removes all elements from a container matching a predicate.
 
template<typename Count , typename Function >
void fcppt::algorithm::repeat (Count const _count, Function const &_function)
 Calls a function a number of times.
 
template<typename Container >
std::remove_cvref_t< Container > fcppt::algorithm::reverse (Container &&_container)
 Reverses a container.
 
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.
 
template<typename String >
std::vector< String > fcppt::algorithm::split_string (String const &_string, fcppt::type_traits::value_type< String > const _delim)
 Splits a string, using a delimiter.
 
template<typename Container >
void fcppt::algorithm::unique (Container &_container)
 Removes duplicate elements from a container.
 
template<typename Container , typename BinaryPredicate >
void fcppt::algorithm::unique_if (Container &_container, BinaryPredicate const &_predicate)
 Removes duplicate elements from a container. Compares using a predicate.
 

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

enum class fcppt::algorithm::update_action
strong

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).

◆ binary_search()

template<typename Range , typename T >
fcppt::optional::object< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > 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 (T) for all types T that appear in Range.

◆ 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 >
fcppt::iterator::range< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > 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 Result , typename Range , typename Function >
fcppt::optional::object< Result > fcppt::algorithm::find_by_opt ( Range &&  _range,
Function const &  _function 
)
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<Result> (V) for every type V in Range.

◆ find_if_opt()

template<typename Range , typename Comp >
fcppt::optional::object< fcppt::container::to_iterator_type< std::remove_reference_t< Range > > > 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< std::remove_reference_t< Range > > > 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_strings()

template<typename Range >
fcppt::type_traits::value_type< Range > fcppt::algorithm::join_strings ( Range const &  _range,
fcppt::type_traits::value_type< Range > 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{fcppt::algorithm::join_strings(strings, ",")};
// Outputs "ab,cd,efg"
std::cout << result << "\n";
Template Parameters
RangeA range of strings.

◆ 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.

The actual implementation of the algorithm is provided by fcppt::algorithm::map_impl which by default uses fcppt::algorithm::loop.

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).

TODO(philipp): concepts

◆ 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_cvref_t< Container > 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).

◆ split_string()

template<typename String >
std::vector< String > fcppt::algorithm::split_string ( String const &  _string,
fcppt::type_traits::value_type< String > const  _delim 
)

Splits a string, using a delimiter.

Let $ \mathrm{\_string} = (c_1, \dots , c_n)$, where $ n \ge 0 $ and $ p_1 < \dots < p_m $, where $ m \ge 0 $, be the positions of _string with value _delim. Also, let $ p_{m+1} = \mathrm{\_string.size()}$. The result is

\[ (\mathrm{\_string}[0,p_1-1], \mathrm{\_string}[p_1+1,p_2-1], \dots, \mathrm{\_string}[p_m+1,p_{m+1}-1). \]

Note that in case m is 0, the string itself is returned as a single element.

Template Parameters
StringMust be a container, constructible with a pair of iterators.

◆ unique()

template<typename Container >
void fcppt::algorithm::unique ( Container &  _container)
inline

Removes duplicate elements from a container.

Removes duplicate elements from _container.

◆ unique_if()

template<typename Container , typename BinaryPredicate >
void fcppt::algorithm::unique_if ( Container &  _container,
BinaryPredicate const &  _predicate 
)

Removes duplicate elements from a container. Compares using a predicate.

Removes duplicate elements from _container. Elements are compared using _predicate.

Template Parameters
BinaryPredicateA function callable as bool (Container::value_type, Container::value_type).
Generated on Sun Oct 29 2023 09:15:50 for fcppt by   doxygen 1.9.8