Container Utilities

Utility functions for (STL) container access and manipulation. More...

Collaboration diagram for Container Utilities:

Detailed Description

Utility functions for (STL) container access and manipulation.

Classes
class	LRUCache< Key, Value, Hash, KeyEqual >
	Templated container class implementing a Least Recently Used Cache. More...

Search for elements
template<typename ContainerT, typename T>
auto	find (ContainerT &&container, const T &value) -> decltype(container.begin())
	Convenience function wrapping std::find() for the given container.
template<typename ContainerT, typename UnaryPredicate>
auto	findIf (ContainerT &&container, UnaryPredicate &&predicate) -> decltype(container.begin())
	Convenience function wrapping std::find_if() for the given container.
template<typename ContainerT, typename T>
auto	findPtr (ContainerT &&container, T &&pointer) -> decltype(container.begin())
	Convenience function to search for a raw pointer in a container of smart pointers.
template<typename ContainerT, typename ElementType, typename T>
auto	findIfMember (ContainerT &&container, T ElementType::*member, const T &value) -> decltype(container.begin())
	Return an iterator to the first element where member equals value.
template<typename ContainerT, typename T>
int64_t	indexOf (ContainerT &&container, const T &value)
	Find the index of the first element that is equal to value inside container.
template<typename ContainerT, typename UnaryPredicate>
int64_t	indexOfIf (ContainerT &&container, UnaryPredicate &&predicate)
	Find the index of the first element that matches predicate.
template<typename ContainerT, typename T>
int64_t	indexOfPtr (ContainerT &&container, T &&pointer)
	Convenience function to get the index of the first occurence of pointer in a container of smart pointers.
template<typename ContainerT, typename T>
bool	contains (const ContainerT &container, const T &value)
	Return true if container contains value or false otherwise.
template<typename ContainerT, typename UnaryPredicate>
bool	containsIf (const ContainerT &container, UnaryPredicate &&predicate)
	Return true if container contains any value that matches predicate.
template<typename ContainerT, typename T>
bool	containsPtr (const ContainerT &container, T &&pointer)
	Convenience function check whether a container of smart pointers contains a given raw pointer.
template<typename ContainerT, typename ElementType, typename T>
bool	containsIfMember (const ContainerT &container, T ElementType::*member, const T &value)
	Return true if the container contains an element where member equals value.
template<typename ContainerT, typename T>
int64_t	countValue (const ContainerT &c, const T &value)
	Return the number of elements in c that are equal to value.
template<typename ContainerT, class UnaryPredicate>
int64_t	countIf (const ContainerT &c, UnaryPredicate &&pred)
	Return the number of elements in c that match the given predicate.

Erase or extract elements from containers
template<typename ContainerT, typename T>
int64_t	erase (ContainerT &container, T &&value)
	Convenience function to remove and erase all elements matching value from container.
template<typename ContainerT, typename UnaryPredicate>
int64_t	eraseIf (ContainerT &container, UnaryPredicate &&predicate)
	Convenience function to remove and erase all elements from container that match the predicate.
template<typename ContainerT>
int64_t	eraseDuplicates (ContainerT &container)
	Removes all duplicates from the given container by calling std::sort(), std::unique() and std::erase().
template<typename ContainerT>
int64_t	eraseDuplicatesStable (ContainerT &container)
	Removes all duplicates from the given container keeping the original order intact.
template<typename ContainerT, typename UnaryPredicate>
ContainerT	extractIf (ContainerT &container, UnaryPredicate &&predicate)
	Move-extracts all elements from container that match the given predicate.

Transform elements
template<typename ContainerT, typename UnaryOp>
auto	transformed (ContainerT &&container, UnaryOp &&op) -> std::vector< std::decay_t< decltype(op(*std::begin(container)))> >
	A container-based wrapper for std::transform.
template<typename T, class UnaryOperation>
auto	transformed (std::initializer_list< T > elements, UnaryOperation &&op) -> std::vector< std::decay_t< decltype(op(*elements.begin()))> >
	An overload for the container-based wrapper for std::transform, taking an initializer list as the container.
template<typename T, typename U, class BinaryOperation>
auto	transformed (const std::vector< T > &containerA, const std::vector< U > &containerB, BinaryOperation &&op) -> std::vector< std::decay_t< decltype(op(containerA.front(), containerB.front()))> >
	A container-based wrapper for std::transform taking two constainers.
template<typename T, template< typename... > class SmartPtr>
std::vector< T * >	asRawPointers (const std::vector< SmartPtr< T > > &container)
	Converts a vector of smart pointers (such as std::unique_ptr or std::shared_ptr) to a vector of corresponding raw pointers.
template<typename T, typename ContainerT>
std::vector< T >	casted (const ContainerT &container)
	Converts the input container to a std::vector<T> by casting each element to T.
template<typename T, typename U, class BinaryOperation>
void	forEachZip (const std::vector< T > &containerA, const std::vector< U > &containerB, BinaryOperation &&op)
	A convenience function which applies a binary operator to two containers.
template<typename ContainerT, typename UnaryPred>
ContainerT	filtered (const ContainerT &container, UnaryPred &&pred)
	Filters certain elements out of a container.
template<typename ContainerT, typename UnaryPred, typename UnaryOperation>
auto	filteredTransform (const ContainerT &container, UnaryPred &&predicate, UnaryOperation &&op) -> std::vector< std::decay_t< decltype(op(*container.begin()))> >
	Combines filtered() and transformed() into a single pass operation.

Accumulate elements
template<typename ContainerT>
auto	accumulate (const ContainerT &c) -> typename ContainerT::value_type
	A container-based wrapper for std::accumulate.
template<typename ContainerT, typename T>
T	accumulate (const ContainerT &c, T init)
	A container-based wrapper for std::accumulate.
template<typename ContainerT, typename T, typename BinaryOp>
T	accumulate (const ContainerT &c, T init, BinaryOp &&op)
	A container-based wrapper for std::accumulate.

Iterate over a range having acces to both the index and the value of each element.
template<class Iterator>
auto	enumerate (Iterator begin, Iterator end)
	Helper function to have access to both the index and value of each element during iteration.
template<class Container>
auto	enumerate (Container &content)
	Helper function to have access to both the index and value of each element during iteration.
template<class Container>
auto	enumerate (Container &&content)
	Helper function to have access to both the index and value of each element during iteration.

Other Functions
template<typename ContainerT, class UnaryPredicate>
bool	allOf (const ContainerT &container, UnaryPredicate &&predicate)
	Checks whether all elements in container match predicate.
template<typename ContainerT, class UnaryPredicate>
bool	anyOf (const ContainerT &container, UnaryPredicate &&predicate)
	Checks whether any element in container match predicate.
template<typename ContainerT, class UnaryPredicate>
bool	noneOf (const ContainerT &container, UnaryPredicate &&predicate)
	Checks whether no elements in container match predicate.
template<typename ContainerT, class BinaryPredicate>
bool	allEqual (const ContainerT &container, BinaryPredicate &&predicate)
	A container-based algorithms that checks whether all elements in a container are equal to each other.
template<typename ContainerT>
bool	allEqual (const ContainerT &container)
	A container-based algorithm that checks whether all elements in a container are equal to each other.
template<typename ContainerT>
void	naturalSort (ContainerT &container)
	Utility function implementing a "natural sort" algorithm for strings.
template<typename ContainerT>
void	renameKey (ContainerT &container, const typename ContainerT::key_type &oldKey, const typename ContainerT::key_type &newKey)
	Convenience function to change the key for a map entry.

Function Documentation

findPtr()

template<typename ContainerT, typename T>

auto findPtr	(	ContainerT &&	container,
		T &&	pointer ) -> decltype(container.begin())

#include <ImFusion/Core/Container.h>

Convenience function to search for a raw pointer in a container of smart pointers.

std::vector<std::unique_ptr<Element>> elements = ...;
const Element* e = ...;
auto it = Container::findPtr(elements, e);

findIfMember()

template<typename ContainerT, typename ElementType, typename T>

auto findIfMember	(	ContainerT &&	container,
		T ElementType::*	member,
		const T &	value ) -> decltype(container.begin())

#include <ImFusion/Core/Container.h>

Return an iterator to the first element where member equals value.

Use a pointer to member to define which part of the element you want to compare, e.g.

struct SomeStruct { int i; bool b; };
std::vector<SomeStruct> vec;
auto it = Container::findIfMember(vec, &SomeStruct::i, 42);

indexOf()

template<typename ContainerT, typename T>

int64_t indexOf	(	ContainerT &&	container,
		const T &	value )

#include <ImFusion/Core/Container.h>

Find the index of the first element that is equal to value inside container.

Return -1 if the value is not part of the container.

indexOfIf()

template<typename ContainerT, typename UnaryPredicate>

int64_t indexOfIf	(	ContainerT &&	container,
		UnaryPredicate &&	predicate )

#include <ImFusion/Core/Container.h>

Find the index of the first element that matches predicate.

Return -1 if no such element is in the container.

indexOfPtr()

template<typename ContainerT, typename T>

int64_t indexOfPtr	(	ContainerT &&	container,
		T &&	pointer )

#include <ImFusion/Core/Container.h>

Convenience function to get the index of the first occurence of pointer in a container of smart pointers.

Return -1 if no such element is in the container.

std::vector<std::unique_ptr<Element>> elements = ...;
const Element* e = ...;
int64_t index = Container::indexOfPtr(elements, e);

containsPtr()

template<typename ContainerT, typename T>

bool containsPtr	(	const ContainerT &	container,
		T &&	pointer )

#include <ImFusion/Core/Container.h>

Convenience function check whether a container of smart pointers contains a given raw pointer.

std::vector<std::unique_ptr<Element>> elements = ...;
const Element* e = ...;
if (Container::containsPtr(elements, e))
    ...

containsIfMember()

template<typename ContainerT, typename ElementType, typename T>

bool containsIfMember	(	const ContainerT &	container,
		T ElementType::*	member,
		const T &	value )

#include <ImFusion/Core/Container.h>

Return true if the container contains an element where member equals value.

Use a pointer to member to define which part of the element you want to compare, e.g.

struct SomeStruct { int i; bool b; };
std::vector<SomeStruct> vec;
if (Container::containsIfMember(vec, &SomeStruct::i, 42))
  ...

countValue()

template<typename ContainerT, typename T>

int64_t countValue	(	const ContainerT &	c,
		const T &	value )

#include <ImFusion/Core/Container.h>

Return the number of elements in c that are equal to value.

Parameters

c	A container of elements.
value	A single value equals-comparable to the elements in c to count.

countIf()

template<typename ContainerT, class UnaryPredicate>

int64_t countIf	(	const ContainerT &	c,
		UnaryPredicate &&	pred )

#include <ImFusion/Core/Container.h>

Return the number of elements in c that match the given predicate.

Parameters

c	A container of elements.
pred	A unary predicate which takes elements of the container returns a bool.

erase()

template<typename ContainerT, typename T>

int64_t erase	(	ContainerT &	container,
		T &&	value )

#include <ImFusion/Core/Container.h>

Convenience function to remove and erase all elements matching value from container.

Returns the number of elements that were removed.

eraseIf()

template<typename ContainerT, typename UnaryPredicate>

int64_t eraseIf	(	ContainerT &	container,
		UnaryPredicate &&	predicate )

#include <ImFusion/Core/Container.h>

Convenience function to remove and erase all elements from container that match the predicate.

Returns the number of elements that were removed.

eraseDuplicates()

template<typename ContainerT>

int64_t eraseDuplicates

(

ContainerT &

container

)

#include <ImFusion/Core/Container.h>

Removes all duplicates from the given container by calling std::sort(), std::unique() and std::erase().

Returns the number of elements that were removed.

Note

This algorithm may change the element order in order to achieve O(N log N) time complexity. Use the slower eraseDuplicatesStable() variant if you require that the element remains unchanged or the element type is not sortable.

eraseDuplicatesStable()

template<typename ContainerT>

int64_t eraseDuplicatesStable

(

ContainerT &

container

)

#include <ImFusion/Core/Container.h>

Removes all duplicates from the given container keeping the original order intact.

Returns the number of elements that were removed.

Note

This algorithm has time complexity O(n^2). Prefer using the faster eraseDuplicates() variant if you don't care about the element order.

extractIf()

template<typename ContainerT, typename UnaryPredicate>

ContainerT extractIf	(	ContainerT &	container,
		UnaryPredicate &&	predicate )

#include <ImFusion/Core/Container.h>

Move-extracts all elements from container that match the given predicate.

std::vector<std::string> input{ ".", "..", "...", "...." };
std::vector<std::string> output = Container::extractIf(input, [](std::string& s) {
    return (s.size() % 2) == 0;
};
// input will now be { ".", "..." } and output will be { "..", "...." }

Template Parameters

ContainerT	Must be a re-orderable container (e.g. a std::vector works but a SequenceContainer such as std::set does not)
UnaryPredicate	Function that can be applied to elements of container and returns a bool

transformed() [1/3]

template<typename ContainerT, typename UnaryOp>

auto transformed	(	ContainerT &&	container,
		UnaryOp &&	op ) -> std::vector<std::decay_t<decltype(op(*std::begin(container)))>>

#include <ImFusion/Core/Container.h>

A container-based wrapper for std::transform.

Returns a std::vector with the results of applying op to each element in container.

transformed() [2/3]

template<typename T, class UnaryOperation>

auto transformed	(	std::initializer_list< T >	elements,
		UnaryOperation &&	op ) -> std::vector<std::decay_t<decltype(op(*elements.begin()))>>

#include <ImFusion/Core/Container.h>

An overload for the container-based wrapper for std::transform, taking an initializer list as the container.

auto to_stars = [](int n) {
    std::string res;
    for (int i=0; i<n; ++i)
        res += "*";
    return res;
};
 
// will return std::vector<std::string>{"*", "**", "***", "****"};
const auto stars = transformed({1, 2, 3, 4}, to_stars);

transformed() [3/3]

template<typename T, typename U, class BinaryOperation>

auto transformed	(	const std::vector< T > &	containerA,
		const std::vector< U > &	containerB,
		BinaryOperation &&	op ) -> std::vector<std::decay_t<decltype(op(containerA.front(), containerB.front()))>>

#include <ImFusion/Core/Container.h>

A container-based wrapper for std::transform taking two constainers.

Parameters

containerA	A container of elements with type T.
containerB	A container of elements with type U.
op	A binary operation which transforms elements of type T and U to elements of type V

Returns

Vector of elements with type V, the values obtained by applying op to corresponding pairs of elements of the given containers.

std::vector<int> xs{1, 2, 3, 4};
std::vector<float> ys{5, 6, 7, 8};
auto to_point = [](int x, float y){ return Point<double>{x,y}; };
 
// will return std::vector<Point<double>{ {1.0, 5.0}, {2.0, 6.0}, {3.0, 7.0}, {4.0, 8.0}};
const auto points = transformed(xs, ys, to_point);

asRawPointers()

template<typename T, template< typename... > class SmartPtr>

std::vector< T * > asRawPointers

(

const std::vector< SmartPtr< T > > &

container

)

#include <ImFusion/Core/Container.h>

Converts a vector of smart pointers (such as std::unique_ptr or std::shared_ptr) to a vector of corresponding raw pointers.

This is a convenience function implementing transformed(container, [](const auto& ptr) { return ptr.get(); }).

Parameters

container

A std::vector of a smart pointer type. The smart pointer must implement the .get() member function to retrieve the underlying raw pointer.

casted()

template<typename T, typename ContainerT>

std::vector< T > casted

(

const ContainerT &

container

)

#include <ImFusion/Core/Container.h>

Converts the input container to a std::vector<T> by casting each element to T.

This is a convenience function implementing transformed(container, [](const auto& value) { return static_cast<T>(value); }).

Parameters

container

An iterable container where each element can be static_casted to T.

forEachZip()

template<typename T, typename U, class BinaryOperation>

void forEachZip	(	const std::vector< T > &	containerA,
		const std::vector< U > &	containerB,
		BinaryOperation &&	op )

#include <ImFusion/Core/Container.h>

A convenience function which applies a binary operator to two containers.

Conceptually the same as calling zip on the two containers, and then calling for_each on the result of that.

Parameters

containerA	A container of elements with type T.
containerB	A container of elements with type U. It must have at least as many elements as containerA.
op	A binary operation which does something with elements of type T and U, op(T,U) -> void.

Example:

std::vector<int> xs{1, 2, 3, 4};
std::vector<float> ys{5, 6, 7, 8, 9};
 
for_each_zip(xs, ys, [](int x, float y) {
    std::cout << x << ", " << y << std::endl;
});

will result in the console output:

1, 5.0
2, 6.0
3, 7.0
4, 8.0

Note that the extra element in ys was ignored.

filtered()

template<typename ContainerT, typename UnaryPred>

ContainerT filtered	(	const ContainerT &	container,
		UnaryPred &&	pred )

#include <ImFusion/Core/Container.h>

Filters certain elements out of a container.

Parameters

container	A container of elements.
pred	A callable predicate taking elements of the container and returning true for those elements that should be kept in the filtered container.

Returns

A container of elements from the given container for which the given predicate was satisfied.

Example:

const auto numbers = std::vector<int>{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const auto isEven = [](int n) { return n % 2 == 0; };
const auto evens = filtered(numbers, isEven); // evens contains {0, 2, 4, 6, 8, 10}

filteredTransform()

template<typename ContainerT, typename UnaryPred, typename UnaryOperation>

auto filteredTransform	(	const ContainerT &	container,
		UnaryPred &&	predicate,
		UnaryOperation &&	op ) -> std::vector<std::decay_t<decltype(op(*container.begin()))>>

#include <ImFusion/Core/Container.h>

Combines filtered() and transformed() into a single pass operation.

Iterates over all elements in container. All elements where predicate yields true are passed to op and the results are accumulated in a std::vector which is eventually returned.

Example:

auto isEven = [](int n) { return n % 2 == 0; };
auto makeNegative = [](int n) { return -n; };
auto evenNegatives = filteredTransform({0, 1, 2, 3, 4}, isEven, makeNegative); // returns {0, -2, -4}

accumulate() [1/3]

template<typename ContainerT>

auto accumulate

(

const ContainerT &

c

)

-> typename ContainerT::value_type

#include <ImFusion/Core/Container.h>

A container-based wrapper for std::accumulate.

Parameters

c	A container of elements with type T.

Returns

Element of type T with the value obtained by applying operator+() to all elements of the container

Example:

const auto nums = std::vector<int>{1, 2, 3, 4};
const int sum = accumulate(nums); // sum = 10

accumulate() [2/3]

template<typename ContainerT, typename T>

T accumulate	(	const ContainerT &	c,
		T	init )

#include <ImFusion/Core/Container.h>

A container-based wrapper for std::accumulate.

Parameters

c	A container of elements with type T.
init	The initial value of the accumulation.

Returns

An element of type T with the value obtained by applying operator+() to all elements of the container, starting with the given initial value.

Example:

const auto nums = std::vector<int>{1, 2, 3, 4};
const int sum = accumulate(nums, 10); // sum = 20

accumulate() [3/3]

template<typename ContainerT, typename T, typename BinaryOp>

T accumulate	(	const ContainerT &	c,
		T	init,
		BinaryOp &&	op )

#include <ImFusion/Core/Container.h>

A container-based wrapper for std::accumulate.

Parameters

c	A container of elements with type T.
init	The initial value of the accumulation. It must have the same type U as returned by the given binary operator.
op	The binary operation to be applied to the elements of the container. It has the signature op(U, T) -> U.

Returns

An element of type U with the value obtained by applying op() to all elements of the container, starting with the given initial value.

Example:

const auto nums = std::vector<int>{1, 2, 3, 4};
const auto init = std::string{""};
const auto op = [](std:string acc, int n) {
    for (int i = 0; i < n; ++i)
        acc += "*";
    acc += " ";
    return acc;
};
const auto stars = accumulate(nums, init, op); // stars = "* ** *** **** "

enumerate() [1/3]

template<class Iterator>

auto enumerate	(	Iterator	begin,
		Iterator	end )

#include <ImFusion/Core/Container.h>

Helper function to have access to both the index and value of each element during iteration.

The function returns an iterable object where each element is a small index-value pair, providing pair.index and pair.value to access the index and current value of the iteration respectively.

Example usage

SomeContainer container = ...;
for (const auto& elem : Container::enumerate(container.begin(), container.end()))
{
    LOG_INFO("Element #" << elem.index << " = " << elem.value);
}

enumerate() [2/3]

template<class Container>

auto enumerate

(

Container &

content

)

#include <ImFusion/Core/Container.h>

Helper function to have access to both the index and value of each element during iteration.

The function returns an iterable object where each element is a small index-value pair, providing pair.index and pair.value to access the index and current value of the iteration respectively.

Example usage

SomeContainer container = ...;
for (const auto& elem : Container::enumerate(container))
{
    LOG_INFO("Element #" << elem.index << " = " << elem.value);
}

enumerate() [3/3]

template<class Container>

auto enumerate

(

Container &&

content

)

#include <ImFusion/Core/Container.h>

Helper function to have access to both the index and value of each element during iteration.

The function returns an iterable object where each element is a small index-value pair, providing pair.index and pair.value to access the index and current value of the iteration respectively.

Example usage

SomeContainer producerFunction();
 
for (const auto& elem : Container::enumerate(producerFunction()))
{
    LOG_INFO("Element #" << elem.index << " = " << elem.value);
}

allEqual() [1/2]

template<typename ContainerT, class BinaryPredicate>

bool allEqual	(	const ContainerT &	container,
		BinaryPredicate &&	predicate )

#include <ImFusion/Core/Container.h>

A container-based algorithms that checks whether all elements in a container are equal to each other.

Parameters

container	A container of elements.
predicate	Binary predicate accepting two elements from container and returning if they are equal.

Returns

True if all of the elements in the container are pairwise equal according to predicate.

Example:

std::vector<int> ones{1, 1, 1, 1};
std::vector<int> signedOnes{1, -1, 1, -1};
// both checks will return true:
bool resultA = allEqual(ones, [](int lhs, int rhs) { return lhs == rhs; });
bool resultB = allEqual(signedOnes, [](int lhs, int rhs) { return std::abs(lhs) == std::abs(rhs); });

allEqual() [2/2]

template<typename ContainerT>

bool allEqual

(

const ContainerT &

container

)

#include <ImFusion/Core/Container.h>

A container-based algorithm that checks whether all elements in a container are equal to each other.

Parameters

container

A container of elements.

Returns

True if all of the elements in the container are pairwise equal.

Note

The equality comparison operator operator==() must be defined for the type of elements that are in the container.

Example:

const std::vector<int> ones{1,1,1,1};
const std::vector<float> oneToFour{1,2,3,4};
bool resultA = allEqual(ones);      // returns true
bool resultB = allEqual(oneToFour); // return false

naturalSort()

template<typename ContainerT>

void naturalSort

(

ContainerT &

container

)

#include <ImFusion/Core/Container.h>

Utility function implementing a "natural sort" algorithm for strings.

The natural sort order is the same as the alphanumerical sort order except that multi-digit numbers are treated atomically. E.g.:

• ab2 < xd2 < xd10
• x1y < x02y < x10y
• 01 < 10 < 0012

  Parameters

  container

  Container with random access iterator and std::string elements

renameKey()

template<typename ContainerT>

void renameKey ( ContainerT & container, const typename ContainerT::key_type & oldKey, const typename ContainerT::key_type & newKey )

inline

#include <ImFusion/Core/Container.h>

Convenience function to change the key for a map entry.

Parameters

container	A std::map or a std::unordered_map.
oldKey	the old value of the key
newKey	the new value of the key

Warning

This function will not work with a multimap.