Boost.Hana  1.5.0
Your standard library for metaprogramming
Searchable

Description

The Searchable concept represents structures that can be searched.

Intuitively, a Searchable is any structure, finite or infinite, containing elements that can be searched using a predicate. Sometimes, Searchables will associate keys to values; one can search for a key with a predicate, and the value associated to it is returned. This gives rise to map-like data structures. Other times, the elements of the structure that are searched (i.e. those to which the predicate is applied) are the same that are returned, which gives rise to set-like data structures. In general, we will refer to the keys of a Searchable structure as those elements that are used for searching, and to the values of a Searchable as those elements that are returned when a search is successful. As was explained, there is no requirement that both notions differ, and it is often useful to have keys and values coincide (think about std::set).

Some methods like any_of, all_of and none_of allow simple queries to be performed on the keys of the structure, while other methods like find and find_if make it possible to find the value associated to a key. The most specific method should always be used if one cares about performance, because it is usually the case that heavy optimizations can be performed in more specific methods. For example, an associative data structure implemented as a hash table will be much faster to access using find than find_if, because in the second case it will have to do a linear search through all the entries. Similarly, using contains will likely be much faster than any_of with an equivalent predicate.

Insight
In a lazy evaluation context, any Foldable can also become a model of Searchable because we can search lazily through the structure with fold_right. However, in the context of C++, some Searchables can not be folded; think for example of an infinite set.

Minimal complete definition

find_if and any_of

When find_if and any_of are provided, the other functions are implemented according to the laws explained below.

Note
We could implement any_of(xs, pred) by checking whether find_if(xs, pred) is an empty optional or not, and then reduce the minimal complete definition to find_if. However, this is not done because that implementation requires the predicate of any_of to return a compile-time Logical, which is more restrictive than what we have right now.

Laws

In order for the semantics of the methods to be consistent, some properties must be satisfied by any model of the Searchable concept. Rigorously, for any Searchables xs and ys and any predicate p, the following laws should be satisfied:

any_of(xs, p) <=> !all_of(xs, negated p)
<=> !none_of(xs, p)
contains(xs, x) <=> any_of(xs, equal.to(x))
find(xs, x) == find_if(xs, equal.to(x))
find_if(xs, always(false_)) == nothing
is_subset(xs, ys) <=> all_of(xs, [](auto x) { return contains(ys, x); })
is_disjoint(xs, ys) <=> none_of(xs, [](auto x) { return contains(ys, x); })

Additionally, if all the keys of the Searchable are Logicals, the following laws should be satisfied:

any(xs) <=> any_of(xs, id)
all(xs) <=> all_of(xs, id)
none(xs) <=> none_of(xs, id)

Concrete models

hana::map, hana::optional, hana::range, hana::set, hana::string, hana::tuple

Free model for builtin arrays

Builtin arrays whose size is known can be searched as-if they were homogeneous tuples. However, since arrays can only hold objects of a single type and the predicate to find_if must return a compile-time Logical, the find_if method is fairly useless. For similar reasons, the find method is also fairly useless. This model is provided mainly because of the any_of method & friends, which are both useful and compile-time efficient.

Structure preserving functions

Given two Searchables S1 and S2, a function \( f : S_1(X) \to S_2(X) \) is said to preserve the Searchable structure if for all xs of data type S1(X) and predicates \( \mathtt{pred} : X \to Bool \) (for a Logical Bool),

any_of(xs, pred) if and only if any_of(f(xs), pred)
find_if(xs, pred) == find_if(f(xs), pred)

This is really just a generalization of the following, more intuitive requirements. For all xs of data type S1(X) and x of data type X,

x ^in^ xs if and only if x ^in^ f(xs)
find(xs, x) == find(f(xs), x)

These requirements can be understood as saying that f does not change the content of xs, although it may reorder elements. As usual, such a structure-preserving transformation is said to be an embedding if it is also injective, i.e. if it is a lossless transformation.

Variables

constexpr auto boost::hana::all
 Returns whether all the keys of the structure are true-valued.The keys of the structure must be Logicals. If the structure is not finite, a false-valued key must appear at a finite "index" in order for this method to finish. More...
 
constexpr auto boost::hana::all_of
 Returns whether all the keys of the structure satisfy the predicate.If the structure is not finite, predicate has to return a false- valued Logical after looking at a finite number of keys for this method to finish. More...
 
constexpr auto boost::hana::any
 Returns whether any key of the structure is true-valued.The keys of the structure must be Logicals. If the structure is not finite, a true-valued key must appear at a finite "index" in order for this method to finish. More...
 
constexpr auto boost::hana::any_of
 Returns whether any key of the structure satisfies the predicate.If the structure is not finite, predicate has to be satisfied after looking at a finite number of keys for this method to finish. More...
 
constexpr auto boost::hana::at_key
 Returns the value associated to the given key in a structure, or fail.Given a key and a Searchable structure, at_key returns the first value whose key is equal to the given key, and fails at compile-time if no such key exists. This requires the key to be compile-time Comparable, exactly like for find. at_key satisfies the following: More...
 
constexpr auto boost::hana::contains
 Returns whether the key occurs in the structure.Given a Searchable structure xs and a key, contains returns whether any of the keys of the structure is equal to the given key. If the structure is not finite, an equal key has to appear at a finite position in the structure for this method to finish. For convenience, contains can also be applied in infix notation. More...
 
constexpr auto boost::hana::in = hana::infix(hana::flip(hana::contains))
 Return whether the key occurs in the structure.Specifically, this is equivalent to contains, except in takes its arguments in reverse order. Like contains, in can also be applied in infix notation for increased expressiveness. This function is not a method that can be overriden; it is just a convenience function provided with the concept. More...
 
constexpr auto boost::hana::find
 Finds the value associated to the given key in a structure.Given a key and a Searchable structure, find returns the just the first value whose key is equal to the given key, or nothing if there is no such key. Comparison is done with equal. find satisfies the following: More...
 
constexpr auto boost::hana::find_if
 Finds the value associated to the first key satisfying a predicate.Given a Searchable structure xs and a predicate pred, find_if(xs, pred) returns just the first element whose key satisfies the predicate, or nothing if there is no such element. More...
 
constexpr auto boost::hana::is_disjoint
 Returns whether two Searchables are disjoint.Given two Searchables xs and ys, is_disjoint returns a Logical representing whether the keys in xs are disjoint from the keys in ys, i.e. whether both structures have no keys in common. More...
 
constexpr auto boost::hana::is_subset
 Returns whether a structure contains a subset of the keys of another structure.Given two Searchables xs and ys, is_subset returns a Logical representing whether xs is a subset of ys. In other words, it returns whether all the keys of xs are also present in ys. This method does not return whether xs is a strict subset of ys; if xs and ys are equal, all the keys of xs are also present in ys, and is_subset returns true. More...
 
constexpr auto boost::hana::none
 Returns whether all of the keys of the structure are false-valued.The keys of the structure must be Logicals. If the structure is not finite, a true-valued key must appear at a finite "index" in order for this method to finish. More...
 
constexpr auto boost::hana::none_of
 Returns whether none of the keys of the structure satisfy the predicate.If the structure is not finite, predicate has to return a true- valued Logical after looking at a finite number of keys for this method to finish. More...
 

Variable Documentation

constexpr auto boost::hana::all

#include <boost/hana/fwd/all.hpp>

Initial value:
= [](auto&& xs) {
return tag-dispatched;
}

Returns whether all the keys of the structure are true-valued.The keys of the structure must be Logicals. If the structure is not finite, a false-valued key must appear at a finite "index" in order for this method to finish.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
static_assert(hana::all(hana::make_tuple(hana::true_c, true, hana::true_c)), "");
BOOST_HANA_CONSTANT_CHECK(!hana::all(hana::make_tuple(true, hana::false_c, hana::true_c)));
int main() { }
constexpr auto boost::hana::all_of

#include <boost/hana/fwd/all_of.hpp>

Initial value:
= [](auto&& xs, auto&& predicate) {
return tag-dispatched;
}

Returns whether all the keys of the structure satisfy the predicate.If the structure is not finite, predicate has to return a false- valued Logical after looking at a finite number of keys for this method to finish.

Parameters
xsThe structure to search.
predicateA function called as predicate(k), where k is a key of the structure, and returning a Logical.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <type_traits>
namespace hana = boost::hana;
using namespace hana::literals;
BOOST_HANA_CONSTEXPR_LAMBDA auto is_odd = [](auto x) {
return x % 2_c != 0_c;
};
int main() {
BOOST_HANA_CONSTEXPR_CHECK(hana::all_of(hana::make_tuple(1, 3), is_odd));
BOOST_HANA_CONSTANT_CHECK(!hana::all_of(hana::make_tuple(3_c, 4_c), is_odd));
!hana::all_of(hana::make_tuple(hana::type<void>{}, hana::type<char&>{}),
hana::traits::is_void)
);
hana::all_of(hana::make_tuple(hana::type_c<int>, hana::type_c<char>),
hana::traits::is_integral)
);
}
constexpr auto boost::hana::any

#include <boost/hana/fwd/any.hpp>

Initial value:
= [](auto&& xs) {
return tag-dispatched;
}

Returns whether any key of the structure is true-valued.The keys of the structure must be Logicals. If the structure is not finite, a true-valued key must appear at a finite "index" in order for this method to finish.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
BOOST_HANA_CONSTANT_CHECK(hana::any(hana::make_tuple(false, hana::false_c, hana::true_c)));
static_assert(hana::any(hana::make_tuple(false, hana::false_c, true)), "");
static_assert(!hana::any(hana::make_tuple(false, hana::false_c, hana::false_c)), "");
int main() { }
constexpr auto boost::hana::any_of

#include <boost/hana/fwd/any_of.hpp>

Initial value:
= [](auto&& xs, auto&& predicate) {
return tag-dispatched;
}

Returns whether any key of the structure satisfies the predicate.If the structure is not finite, predicate has to be satisfied after looking at a finite number of keys for this method to finish.

Parameters
xsThe structure to search.
predicateA function called as predicate(k), where k is a key of the structure, and returning a Logical.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <type_traits>
namespace hana = boost::hana;
using namespace hana::literals;
BOOST_HANA_CONSTEXPR_LAMBDA auto is_odd = [](auto x) {
return x % 2_c != 0_c;
};
int main() {
BOOST_HANA_CONSTEXPR_CHECK(hana::any_of(hana::make_tuple(1, 2), is_odd));
BOOST_HANA_CONSTANT_CHECK(!hana::any_of(hana::make_tuple(2_c, 4_c), is_odd));
hana::any_of(hana::make_tuple(hana::type<void>{}, hana::type<char&>{}),
hana::traits::is_void)
);
!hana::any_of(hana::make_tuple(hana::type<void>{}, hana::type<char&>{}),
hana::traits::is_integral)
);
}
constexpr auto boost::hana::at_key

#include <boost/hana/fwd/at_key.hpp>

Initial value:
= [](auto&& xs, auto const& key) -> decltype(auto) {
return tag-dispatched;
}

Returns the value associated to the given key in a structure, or fail.Given a key and a Searchable structure, at_key returns the first value whose key is equal to the given key, and fails at compile-time if no such key exists. This requires the key to be compile-time Comparable, exactly like for find. at_key satisfies the following:

at_key(xs, key) == find(xs, key).value()

If the Searchable actually stores the elements it contains, at_key is required to return a lvalue reference, a lvalue reference to const or a rvalue reference to the found value, where the type of reference must match that of the structure passed to at_key. If the Searchable does not store the elements it contains (i.e. it generates them on demand), this requirement is dropped.

Parameters
xsThe structure to be searched.
keyA key to be searched for in the structure. The key has to be Comparable with the other keys of the structure. In the current version of the library, the comparison of key with any other key of the structure must return a compile-time Logical.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <string>
namespace hana = boost::hana;
int main() {
auto m = hana::make_map(
hana::make_pair(hana::type<int>{}, std::string{"int"}),
hana::make_pair(hana::int_<3>{}, std::string{"3"})
);
BOOST_HANA_RUNTIME_CHECK(hana::at_key(m, hana::type<int>{}) == "int");
// usage as operator[]
BOOST_HANA_RUNTIME_CHECK(m[hana::type<int>{}] == "int");
BOOST_HANA_RUNTIME_CHECK(m[hana::int_<3>{}] == "3");
}
constexpr auto boost::hana::contains

#include <boost/hana/fwd/contains.hpp>

Initial value:
= [](auto&& xs, auto&& key) {
return tag-dispatched;
}

Returns whether the key occurs in the structure.Given a Searchable structure xs and a key, contains returns whether any of the keys of the structure is equal to the given key. If the structure is not finite, an equal key has to appear at a finite position in the structure for this method to finish. For convenience, contains can also be applied in infix notation.

Parameters
xsThe structure to search.
keyA key to be searched for in the structure. The key has to be Comparable with the other keys of the structure.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
BOOST_HANA_CONSTANT_CHECK(hana::contains(hana::make_tuple(2, hana::int_c<2>, hana::int_c<3>, 'x'), hana::int_c<3>));
BOOST_HANA_CONSTANT_CHECK(hana::contains(hana::make_set(hana::int_c<3>, hana::type_c<void>), hana::type_c<void>));
// contains can be applied in infix notation
hana::make_tuple(2, hana::int_c<2>, hana::int_c<3>, 'x') ^hana::contains^ hana::int_c<2>
);
int main() { }
constexpr auto boost::hana::in = hana::infix(hana::flip(hana::contains))

#include <boost/hana/fwd/contains.hpp>

Return whether the key occurs in the structure.Specifically, this is equivalent to contains, except in takes its arguments in reverse order. Like contains, in can also be applied in infix notation for increased expressiveness. This function is not a method that can be overriden; it is just a convenience function provided with the concept.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
BOOST_HANA_CONSTANT_CHECK(hana::int_c<2> ^hana::in^ hana::make_tuple(2, hana::int_c<2>, hana::int_c<3>, 'x'));
int main() { }
constexpr auto boost::hana::find

#include <boost/hana/fwd/find.hpp>

Initial value:
= [](auto&& xs, auto const& key) {
return tag-dispatched;
}

Finds the value associated to the given key in a structure.Given a key and a Searchable structure, find returns the just the first value whose key is equal to the given key, or nothing if there is no such key. Comparison is done with equal. find satisfies the following:

find(xs, key) == find_if(xs, equal.to(key))
Parameters
xsThe structure to be searched.
keyA key to be searched for in the structure. The key has to be Comparable with the other keys of the structure. In the current version of the library, the comparison of key with any other key of the structure must return a compile-time Logical.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
hana::find(hana::make_tuple(hana::int_c<1>, hana::type_c<int>, '3'), hana::type_c<int>) == hana::just(hana::type_c<int>)
);
hana::find(hana::make_tuple(hana::int_c<1>, hana::type_c<int>, '3'), hana::type_c<void>) == hana::nothing
);
constexpr auto m = hana::make_map(
hana::make_pair(hana::int_c<2>, 2),
hana::make_pair(hana::type_c<float>, 3.3),
hana::make_pair(hana::type_c<char>, hana::type_c<int>)
);
static_assert(hana::find(m, hana::type_c<float>) == hana::just(3.3), "");
int main() { }

Referenced by boost::hana::literals::operator""_s().

constexpr auto boost::hana::find_if

#include <boost/hana/fwd/find_if.hpp>

Initial value:
= [](auto&& xs, auto&& predicate) {
return tag-dispatched;
}

Finds the value associated to the first key satisfying a predicate.Given a Searchable structure xs and a predicate pred, find_if(xs, pred) returns just the first element whose key satisfies the predicate, or nothing if there is no such element.

Parameters
xsThe structure to be searched.
predicateA function called as predicate(k), where k is a key of the structure, and returning whether k is the key of the element being searched for. In the current version of the library, the predicate has to return an IntegralConstant holding a value that can be converted to bool.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <type_traits>
namespace hana = boost::hana;
// First get the type of the object, and then call the trait on it.
constexpr auto is_integral = hana::compose(hana::trait<std::is_integral>, hana::typeid_);
constexpr auto is_class = hana::compose(hana::trait<std::is_class>, hana::typeid_);
static_assert(
hana::find_if(hana::make_tuple(1.0, 2, '3'), is_integral) == hana::just(2)
, "");
hana::find_if(hana::make_tuple(1.0, 2, '3'), is_class) == hana::nothing
);
constexpr auto types = hana::tuple_t<char, int, unsigned, long, unsigned long>;
hana::find_if(types, hana::equal.to(hana::type_c<unsigned>)) == hana::just(hana::type_c<unsigned>)
);
hana::find_if(types, hana::equal.to(hana::type_c<void>)) == hana::nothing
);
int main() { }
constexpr auto boost::hana::is_disjoint

#include <boost/hana/fwd/is_disjoint.hpp>

Initial value:
= [](auto const& xs, auto const& ys) {
return tag-dispatched;
}

Returns whether two Searchables are disjoint.Given two Searchables xs and ys, is_disjoint returns a Logical representing whether the keys in xs are disjoint from the keys in ys, i.e. whether both structures have no keys in common.

Parameters
xs,ysTwo Searchables to test for disjointness.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <string>
namespace hana = boost::hana;
using namespace std::literals;
int main() {
// Tuples
auto xs = hana::make_tuple(hana::int_c<1>, "alfa"s, hana::type_c<int>);
auto ys = hana::make_tuple(hana::type_c<void>, hana::int_c<3>, "bravo"s);
// Sets
auto s1 = hana::make_set(hana::int_c<1>, hana::type_c<void>, hana::int_c<2>);
auto s2 = hana::make_set(hana::type_c<char>, hana::type_c<int>, hana::int_c<1>);
// Maps
auto vowels = hana::make_map(
hana::make_pair(hana::char_c<'a'>, "alfa"s),
hana::make_pair(hana::char_c<'e'>, "echo"s),
hana::make_pair(hana::char_c<'i'>, "india"s)
// ...
);
auto consonants = hana::make_map(
hana::make_pair(hana::char_c<'b'>, "bravo"s),
hana::make_pair(hana::char_c<'c'>, "charlie"s),
hana::make_pair(hana::char_c<'f'>, "foxtrot"s)
// ...
);
}
constexpr auto boost::hana::is_subset

#include <boost/hana/fwd/is_subset.hpp>

Initial value:
= [](auto&& xs, auto&& ys) {
return tag-dispatched;
}

Returns whether a structure contains a subset of the keys of another structure.Given two Searchables xs and ys, is_subset returns a Logical representing whether xs is a subset of ys. In other words, it returns whether all the keys of xs are also present in ys. This method does not return whether xs is a strict subset of ys; if xs and ys are equal, all the keys of xs are also present in ys, and is_subset returns true.

Note
For convenience, is_subset can also be applied in infix notation.

Cross-type version of the method

This method is tag-dispatched using the tags of both arguments. It can be called with any two Searchables sharing a common Searchable embedding, as defined in the main documentation of the Searchable concept. When Searchables with two different tags but sharing a common embedding are sent to is_subset, they are first converted to this common Searchable and the is_subset method of the common embedding is then used. Of course, the method can be overriden for custom Searchables for efficieny.

Note
While cross-type dispatching for is_subset is supported, it is not currently used by the library because there are no models of Searchable with a common embedding.
Parameters
xsThe structure to check whether it is a subset of ys.
ysThe structure to check whether it is a superset of xs.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
static_assert(
hana::is_subset(hana::make_tuple(1, '2', 3.3), hana::make_tuple(3.3, 1, '2', nullptr))
, "");
// is_subset can be applied in infix notation
static_assert(
hana::make_tuple(1, '2', 3.3) ^hana::is_subset^ hana::make_tuple(3.3, 1, '2', nullptr)
, "");
int main() { }
constexpr auto boost::hana::none

#include <boost/hana/fwd/none.hpp>

Initial value:
= [](auto&& xs) -> decltype(auto) {
return tag-dispatched;
}

Returns whether all of the keys of the structure are false-valued.The keys of the structure must be Logicals. If the structure is not finite, a true-valued key must appear at a finite "index" in order for this method to finish.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
namespace hana = boost::hana;
static_assert(hana::none(hana::make_tuple(false, hana::false_c, hana::false_c)), "");
static_assert(!hana::none(hana::make_tuple(false, hana::false_c, true)), "");
BOOST_HANA_CONSTANT_CHECK(!hana::none(hana::make_tuple(false, hana::false_c, hana::true_c)));
int main() { }
constexpr auto boost::hana::none_of

#include <boost/hana/fwd/none_of.hpp>

Initial value:
= [](auto&& xs, auto&& predicate) {
return tag-dispatched;
}

Returns whether none of the keys of the structure satisfy the predicate.If the structure is not finite, predicate has to return a true- valued Logical after looking at a finite number of keys for this method to finish.

Parameters
xsThe structure to search.
predicateA function called as predicate(k), where k is a key of the structure, and returning a Logical.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
#include <type_traits>
namespace hana = boost::hana;
using namespace hana::literals;
BOOST_HANA_CONSTEXPR_LAMBDA auto is_odd = [](auto x) {
return x % 2_c != 0_c;
};
int main() {
BOOST_HANA_CONSTANT_CHECK(hana::none_of(hana::make_tuple(2_c, 4_c), is_odd));
BOOST_HANA_CONSTEXPR_CHECK(!hana::none_of(hana::make_tuple(1, 2), is_odd));
!hana::none_of(hana::make_tuple(hana::type_c<void>, hana::type_c<char&>), hana::trait<std::is_void>)
);
hana::none_of(hana::make_tuple(hana::type_c<void>, hana::type_c<char&>), hana::trait<std::is_integral>)
);
}