EIC code displayed by LXR master/​include/​boost/​hana/​fwd/​concept/​searchable.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-18 09:37:58

 /*!
 @file
 Forward declares `boost::hana::Searchable`.
 
 Copyright Louis Dionne 2013-2022
 Distributed under the Boost Software License, Version 1.0.
 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
  */
 
 #ifndef BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP
 #define BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP
 
 #include <boost/hana/config.hpp>
 
 
 namespace boost { namespace hana {
     //! @ingroup group-concepts
     //! @defgroup group-Searchable Searchable
     //! 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,
     //! `Searchable`s 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__\n
     //! > 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 `Searchable`s
     //! > 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 `Searchable`s  `xs` and `ys` and any predicate `p`,
     //! the following laws should be satisfied:
     //! @code
     //!     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); })
     //! @endcode
     //!
     //! Additionally, if all the keys of the `Searchable` are `Logical`s,
     //! the following laws should be satisfied:
     //! @code
     //!     any(xs)  <=> any_of(xs, id)
     //!     all(xs)  <=> all_of(xs, id)
     //!     none(xs) <=> none_of(xs, id)
     //! @endcode
     //!
     //!
     //! 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$ f : S_1(X) \to S_2(X) @f$ is said to preserve the `Searchable`
     //! structure if for all `xs` of data type `S1(X)` and predicates
     //! @f$ \mathtt{pred} : X \to Bool @f$ (for a `Logical` `Bool`),
     //! @code
     //!     any_of(xs, pred)  if and only if  any_of(f(xs), pred)
     //!     find_if(xs, pred) == find_if(f(xs), pred)
     //! @endcode
     //!
     //! 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`,
     //! @code
     //!     x ^in^ xs  if and only if  x ^in^ f(xs)
     //!     find(xs, x) == find(f(xs), x)
     //! @endcode
     //!
     //! 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.
     template <typename S>
     struct Searchable;
 }} // end namespace boost::hana
 
 #endif // !BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team