The Iterable
concept represents data structures supporting external iteration.
Intuitively, an Iterable
can be seen as a kind of container whose elements can be pulled out one at a time. An Iterable
also provides a way to know when the container is empty, i.e. when there are no more elements to pull out.
Whereas Foldable
represents data structures supporting internal iteration with the ability to accumulate a result, the Iterable
concept allows inverting the control of the iteration. This is more flexible than Foldable
, since it allows iterating over only some part of the structure. This, in turn, allows Iterable
to work on infinite structures, while trying to fold such a structure would never finish.
at
, drop_front
and is_empty
Iterable
Intuitively, for an Iterable
structure xs
, the linearization of xs
is the sequence of all the elements in xs
as if they had been put in a (possibly infinite) list:
The n
th element of the linearization of an Iterable
can be accessed with the at
function. In other words, at(xs, n) == xn
.
Note that this notion is precisely the extension of the linearization notion of Foldable
s to the infinite case. This notion is useful for expressing various properties of Iterable
s, and is used for that elsewhere in the documentation.
Iterable
s A compile-time Iterable
is an Iterable
for which is_empty
returns a compile-time Logical
. These structures allow iteration to be done at compile-time, in the sense that the "loop" doing the iteration can be unrolled because the total length of the structure is kown at compile-time.
In particular, note that being a compile-time Iterable
has nothing to do with being finite or infinite. For example, it would be possible to create a sequence representing the Pythagorean triples as integral_constant
s. Such a sequence would be infinite, but iteration on the sequence would still be done at compile-time. However, if one tried to iterate over all the elements of the sequence, the compiler would loop indefinitely, in contrast to your program looping indefinitely if the sequence was a runtime one.
In the current version of the library, only compile-time Iterable
s are supported. While it would be possible in theory to support runtime Iterable
s, doing it efficiently is the subject of some research. In particular, follow this issue for the current status of runtime Iterable
s.
First, we require the equality of two Iterable
s to be related to the equality of the elements in their linearizations. More specifically, if xs
and ys
are two Iterable
s of data type It
, then
This conveys that two Iterable
s must have the same linearization in order to be considered equal.
Secondly, since every Iterable
is also a Searchable
, we require the models of Iterable
and Searchable
to be consistent. This is made precise by the following laws. For any Iterable
xs
with a linearization of [x1, x2, x3, ...]
,
for some finite index i
. Furthermore,
or nothing
if no such xi
exists.
Searchable
(free model)Iterable
gives rise to a model of Searchable
, where the keys and the values are both the elements in the structure. Searching for a key is just doing a linear search through the elements of the structure. Foldable
for finite Iterable
sIterable
gives rise to a model of Foldable
. For these models to be consistent, we require the models of both Foldable
and Iterable
to have the same linearization.Iterable
s are also Searchable
s and their models have to be consistent. By the laws presented here, it also means that the Foldable
model for finite Iterable
s has to be consistent with the Searchable
model.For convenience, finite Iterable
s must only provide a definition of length
to model the Foldable
concept; defining the more powerful unpack
or fold_left
is not necessary (but still possible). The default implementation of unpack
derived from Iterable
+ length
uses the fact that at(xs, i)
denotes the i
th element of xs
's linearization, and that the linearization of a finite Iterable
must be the same as its linearization as a Foldable
.
hana::tuple
, hana::string
, hana::range
Variables | |
constexpr auto | boost::hana::at |
Returns the n th element of an iterable.Given an Iterable and an IntegralConstant index, at returns the element located at the index in the linearization of the iterable. Specifically, given an iterable xs with a linearization of [x1, ..., xN] , at(xs, k) is equivalent to xk . More... | |
template<std::size_t n> | |
constexpr auto | boost::hana::at_c |
Equivalent to at ; provided for convenience. More... | |
constexpr auto | boost::hana::back |
Returns the last element of a non-empty and finite iterable.Given a non-empty and finite iterable xs with a linearization of [x1, ..., xN] , back(xs) is equal to xN . Equivalently, back(xs) must be equivalent to at_c<N-1>(xs) , and that regardless of the value category of xs (back must respect the reference semantics of at ). More... | |
constexpr auto | boost::hana::drop_front |
Drop the first n elements of an iterable, and return the rest.Given an Iterable xs with a linearization of [x1, x2, ...] and a non-negative IntegralConstant n , drop_front(xs, n) is an iterable with the same tag as xs whose linearization is [xn+1, xn+2, ...] . In particular, note that this function does not mutate the original iterable in any way. If n is not given, it defaults to an IntegralConstant with a value equal to 1 . More... | |
constexpr auto | boost::hana::drop_front_exactly |
Drop the first n elements of an iterable, and return the rest.Given an Iterable xs with a linearization of [x1, x2, ...] and a non-negative IntegralConstant n , drop_front_exactly(xs, n) is an iterable with the same tag as xs whose linearization is [xn+1, xn+2, ...] . In particular, note that this function does not mutate the original iterable in any way. If n is not given, it defaults to an IntegralConstant with a value equal to 1 . More... | |
constexpr auto | boost::hana::drop_while |
Drop elements from an iterable up to, but excluding, the first element for which the predicate is not satisfied.Specifically, drop_while returns an iterable containing all the elements of the original iterable except for those in the range delimited by [head , e ), where head is the first element and e is the first element for which the predicate is not satisfied. If the iterable is not finite, the predicate has to return a false- valued Logical at a finite index for this method to return. More... | |
constexpr auto | boost::hana::front |
Returns the first element of a non-empty iterable.Given a non-empty Iterable xs with a linearization of [x1, ..., xN] , front(xs) is equal to x1 . If xs is empty, it is an error to use this function. Equivalently, front(xs) must be equivalent to at_c<0>(xs) , and that regardless of the value category of xs (front must respect the reference semantics of at ). More... | |
constexpr auto | boost::hana::is_empty |
Returns whether the iterable is empty.Given an Iterable xs , is_empty returns whether xs contains no more elements. In other words, it returns whether trying to extract the tail of xs would be an error. In the current version of the library, is_empty must return an IntegralConstant holding a value convertible to bool . This is because only compile-time Iterable s are supported right now. More... | |
constexpr auto | boost::hana::lexicographical_compare |
Short-circuiting lexicographical comparison of two Iterable s with an optional custom predicate, by default hana::less .Given two Iterable s xs and ys and a binary predicate pred , lexicographical_compare returns whether xs is to be considered less than ys in a lexicographical ordering. Specifically, let's denote the linearizations of xs and ys by [x1, x2, ...] and [y1, y2, ...] , respectively. If the first couple satisfying the predicate is of the form xi, yi , lexicographical_compare returns true. Otherwise, if the first couple to satisfy the predicate is of the form yi, xi , lexicographical_compare returns false. If no such couple can be found, lexicographical_compare returns whether xs has fewer elements than ys . More... | |
constexpr auto boost::hana::at |
#include <boost/hana/fwd/at.hpp>
Returns the n
th element of an iterable.Given an Iterable
and an IntegralConstant
index, at
returns the element located at the index in the linearization of the iterable. Specifically, given an iterable xs
with a linearization of [x1, ..., xN]
, at(xs, k)
is equivalent to xk
.
If the Iterable
actually stores the elements it contains, at
is required to return a lvalue reference, a lvalue reference to const or a rvalue reference to the matching element, where the type of reference must match that of the iterable passed to at
. If the Iterable
does not store the elements it contains (i.e. it generates them on demand), this requirement is dropped.
xs | The iterable in which an element is retrieved. The iterable must contain at least n + 1 elements. |
n | A non-negative IntegralConstant representing the 0-based index of the element to return. It is an error to call at with an index that out of bounds of the iterable. |
constexpr auto boost::hana::at_c |
#include <boost/hana/fwd/at.hpp>
Equivalent to at
; provided for convenience.
hana::at_c<n>
is an overloaded function, not a function object. Hence, it can't be passed to higher-order algorithms. This is done for compile-time performance reasons.constexpr auto boost::hana::back |
#include <boost/hana/fwd/back.hpp>
Returns the last element of a non-empty and finite iterable.Given a non-empty and finite iterable xs
with a linearization of [x1, ..., xN]
, back(xs)
is equal to xN
. Equivalently, back(xs)
must be equivalent to at_c<N-1>(xs)
, and that regardless of the value category of xs
(back
must respect the reference semantics of at
).
constexpr auto boost::hana::drop_front |
#include <boost/hana/fwd/drop_front.hpp>
Drop the first n
elements of an iterable, and return the rest.Given an Iterable
xs
with a linearization of [x1, x2, ...]
and a non-negative IntegralConstant
n
, drop_front(xs, n)
is an iterable with the same tag as xs
whose linearization is [xn+1, xn+2, ...]
. In particular, note that this function does not mutate the original iterable in any way. If n
is not given, it defaults to an IntegralConstant
with a value equal to 1
.
In case length(xs) <= n
, drop_front
will simply drop the whole iterable without failing, thus returning an empty iterable. This is different from drop_front_exactly
, which expects n <= length(xs)
but can be better optimized because of this additional guarantee.
xs | The iterable from which elements are dropped. |
n | A non-negative IntegralConstant representing the number of elements to be dropped from the iterable. If n is not given, it defaults to an IntegralConstant with a value equal to 1 . |
constexpr auto boost::hana::drop_front_exactly |
#include <boost/hana/fwd/drop_front_exactly.hpp>
Drop the first n
elements of an iterable, and return the rest.Given an Iterable
xs
with a linearization of [x1, x2, ...]
and a non-negative IntegralConstant
n
, drop_front_exactly(xs, n)
is an iterable with the same tag as xs
whose linearization is [xn+1, xn+2, ...]
. In particular, note that this function does not mutate the original iterable in any way. If n
is not given, it defaults to an IntegralConstant
with a value equal to 1
.
It is an error to use drop_front_exactly
with n > length(xs)
. This additional guarantee allows drop_front_exactly
to be better optimized than the drop_front
function, which allows n > length(xs)
.
xs | The iterable from which elements are dropped. |
n | A non-negative IntegralConstant representing the number of elements to be dropped from the iterable. In addition to being non-negative, n must be less than or equal to the number of elements in xs . If n is not given, it defaults to an IntegralConstant with a value equal to 1 . |
constexpr auto boost::hana::drop_while |
#include <boost/hana/fwd/drop_while.hpp>
Drop elements from an iterable up to, but excluding, the first element for which the predicate
is not satisfied.Specifically, drop_while
returns an iterable containing all the elements of the original iterable except for those in the range delimited by [head
, e
), where head
is the first element and e
is the first element for which the predicate
is not satisfied. If the iterable is not finite, the predicate
has to return a false- valued Logical
at a finite index for this method to return.
iterable | The iterable from which elements are dropped. |
predicate | A function called as predicate(x) , where x is an element of the structure, and returning a Logical representing whether x should be dropped from the structure. In the current version of the library, predicate should return a compile-time Logical . |
constexpr auto boost::hana::front |
#include <boost/hana/fwd/front.hpp>
Returns the first element of a non-empty iterable.Given a non-empty Iterable xs
with a linearization of [x1, ..., xN]
, front(xs)
is equal to x1
. If xs
is empty, it is an error to use this function. Equivalently, front(xs)
must be equivalent to at_c<0>(xs)
, and that regardless of the value category of xs
(front
must respect the reference semantics of at
).
constexpr auto boost::hana::is_empty |
#include <boost/hana/fwd/is_empty.hpp>
Returns whether the iterable is empty.Given an Iterable
xs
, is_empty
returns whether xs
contains no more elements. In other words, it returns whether trying to extract the tail of xs
would be an error. In the current version of the library, is_empty
must return an IntegralConstant
holding a value convertible to bool
. This is because only compile-time Iterable
s are supported right now.
constexpr auto boost::hana::lexicographical_compare |
#include <boost/hana/fwd/lexicographical_compare.hpp>
Short-circuiting lexicographical comparison of two Iterable
s with an optional custom predicate, by default hana::less
.Given two Iterable
s xs
and ys
and a binary predicate pred
, lexicographical_compare
returns whether xs
is to be considered less than ys
in a lexicographical ordering. Specifically, let's denote the linearizations of xs
and ys
by [x1, x2, ...]
and [y1, y2, ...]
, respectively. If the first couple satisfying the predicate is of the form xi, yi
, lexicographical_compare
returns true. Otherwise, if the first couple to satisfy the predicate is of the form yi, xi
, lexicographical_compare
returns false. If no such couple can be found, lexicographical_compare
returns whether xs
has fewer elements than ys
.
Given two Iterable
s It1(T)
and It2(T)
and a predicate \( pred : T \times T \to Bool \) (where Bool
is some Logical
), lexicographical_compare
has the following signatures. For the variant with a provided predicate,
\[ \mathtt{lexicographical\_compare} : It1(T) \times It2(T) \times (T \times T \to Bool) \to Bool \]
for the variant without a custom predicate, T
is required to be Orderable
. The signature is then
\[ \mathtt{lexicographical\_compare} : It1(T) \times It2(T) \to Bool \]
xs,ys | Two Iterable s to compare lexicographically. |
pred | A binary function called as pred(x, y) and pred(y, x) , where x and y are elements of xs and ys , respectively. pred must return a Logical representing whether its first argument is to be considered as less than its second argument. Also note that pred must define a total ordering as defined by the Orderable concept. When pred is not provided, it defaults to less . |
Referenced by boost::hana::literals::operator""_s().