Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Notes

Recursive Inlined Functions

An interesting peculiarity of functions like at when applied to a Forward Sequence like list is that what could have been linear runtime complexity effectively becomes constant O(1) due to compiler optimization of C++ inlined functions, however deeply recursive (up to a certain compiler limit of course). Compile time complexity remains linear.

Overloaded Functions

Associative sequences use function overloading to implement membership testing and type associated key lookup. This amounts to constant runtime and amortized constant compile time complexities. There is an overloaded function, f(k), for each key type k. The compiler chooses the appropriate function given a key, k.

Tag Dispatching

Tag dispatching is a generic programming technique for selecting template specializations. There are typically 3 components involved in the tag dispatching mechanism:

  1. A type for which an appropriate template specialization is required
  2. A metafunction that associates the type with a tag type
  3. A template that is specialized for the tag type

For example, the fusion result_of::begin metafunction is implemented as follows:

template <typename Sequence>
struct begin
{
    typedef typename
        result_of::begin_impl<typename traits::tag_of<Sequence>::type>::
        template apply<Sequence>::type
    type;
};

In the case:

  1. Sequence is the type for which a suitable implementation of result_of::begin_impl is required
  2. traits::tag_of is the metafunction that associates Sequence with an appropriate tag
  3. result_of::begin_impl is the template which is specialized to provide an implementation for each tag type

Extensibility

Unlike MPL, there is no extensibe sequence concept in fusion. This does not mean that Fusion sequences are not extensible. In fact, all Fusion sequences are inherently extensible. It is just that the manner of sequence extension in Fusion is diferent from both STL and MPL on account of the lazy nature of fusion Algorithms. STL containers extend themselves in place though member functions such as push_back and insert. MPL sequences, on the other hand, are extended through "intrinsic" functions that actually return whole sequences. MPL is purely functional and can not have side effects. For example, MPL's push_back does not actually mutate an mpl::vector. It can't do that. Instead, it returns an extended mpl::vector.

Like MPL, Fusion too is purely functional and can not have side effects. With runtime efficiency in mind, Fusion sequences are extended through generic functions that return Views. Views are sequences that do not actually contain data, but instead impart an alternative presentation over the data from one or more underlying sequences. Views are proxies. They provide an efficient yet purely functional way to work on potentially expensive sequence operations. For example, given a vector, Fusion's push_back returns a joint_view, instead of an actual extended vector. A joint_view holds a reference to the original sequence plus the appended data --making it very cheap to pass around.

Element Conversion

Functions that take in elemental values to form sequences (e.g. make_list) convert their arguments to something suitable to be stored as a sequence element. In general, the element types are stored as plain values. Example:

make_list(1, 'x')

returns a list<int, char>.

There are a few exceptions, however.

Arrays:

Array arguments are deduced to reference to const types. For example [13]:

make_list("Donald", "Daisy")

creates a list of type

list<const char (&)[7], const char (&)[6]>

Function pointers:

Function pointers are deduced to the plain non-reference type (i.e. to plain function pointer). Example:

void f(int i);
  ...
make_list(&f);

creates a list of type

list<void (*)(int)>

boost::ref

Fusion's generation functions (e.g. make_list) by default stores the element types as plain non-reference types. Example:

void foo(const A& a, B& b) {
    ...
    make_list(a, b)

creates a list of type

list<A, B>

Sometimes the plain non-reference type is not desired. You can use boost::ref and boost::cref to store references or const references (respectively) instead. The mechanism does not compromise const correctness since a const object wrapped with ref results in a tuple element with const reference type (see the fifth code line below). Examples:

For example:

A a; B b; const A ca = a;
make_list(cref(a), b);          // creates list<const A&, B>
make_list(ref(a), b);           // creates list<A&, B>
make_list(ref(a), cref(b));     // creates list<A&, const B&>
make_list(cref(ca));            // creates list<const A&>
make_list(ref(ca));             // creates list<const A&>

See Boost.Ref for details.

adt_attribute_proxy

To adapt arbitrary data types that do not allow direct access to their members, but allow indirect access via expressions (such as invocations of get- and set-methods), fusion's BOOST_FUSION_ADAPT_xxxADTxxx-family (e.g. BOOST_FUSION_ADAPT_ADT) may be used. To bypass the restriction of not having actual lvalues that represent the elements of the fusion sequence, but rather a sequence of paired expressions that access the elements, the actual return type of fusion's intrinsic sequence access functions (at, at_c, at_key, deref, and deref_data) is a proxy type, an instance of adt_attribute_proxy, that encapsulates these expressions.

adt_attribute_proxy is defined in the namespace boost::fusion::extension and has three template arguments:

namespace boost { namespace fusion { namespace extension
{
    template<
        typename Type
      , int Index
      , bool Const
    >
    struct adt_attribute_proxy;
}}}

When adapting a class type, adt_attribute_proxy is specialized for every element of the adapted sequence, with Type being the class type that is adapted, Index the 0-based indices of the elements, and Const both true and false. The return type of fusion's intrinsic sequence access functions for the Nth element of an adapted class type type_name is adt_attribute_proxy<type_name, N, Const>, with Const being true for constant instances of type_name and false for non-constant ones.

Notation

type_name

The type to be adapted, with M attributes

inst

Object of type type_name

const_inst

Object of type type_name const

(attribute_typeN, attribute_const_typeN, get_exprN, set_exprN)

Attribute descriptor of the Nth attribute of type_name as passed to the adaption macro, 0≤N<M

proxy_typeN

adt_attribute_proxy<type_name, N, false> with N being an integral constant, 0≤N<M

const_proxy_typeN

adt_attribute_proxy<type_name, N, true> with N being an integral constant, 0≤N<M

proxyN

Object of type proxy_typeN

const_proxyN

Object of type const_proxy_typeN

Expression Semantics

Expression

Semantics

proxy_typeN(inst)

Creates an instance of proxy_typeN with underlying object inst

const_proxy_typeN(const_inst)

Creates an instance of const_proxy_typeN with underlying object const_inst

proxy_typeN::type

Another name for attribute_typeN

const_proxy_typeN::type

Another name for const_attribute_typeN

proxyN=t

Invokes set_exprN, with t being an arbitrary object. set_exprN may access the variables named obj of type type_name&, which represent the corresponding instance of type_name, and val of an arbitrary const-qualified reference template type parameter Val, which represents t.

proxyN.get()

Invokes get_exprN and forwards its return value. get_exprN may access the variable named obj of type type_name& which represents the underlying instance of type_name. attribute_typeN may specify the type that get_exprN denotes to.

const_proxyN.get()

Invokes get_exprN and forwards its return value. get_exprN may access the variable named obj of type type_name const& which represents the underlying instance of type_name. attribute_const_typeN may specify the type that get_exprN denotes to.

Additionally, proxy_typeN and const_proxy_typeN are copy constructible, copy assignable and implicitly convertible to proxy_typeN::type or const_proxy_typeN::type.

[Tip] Tip

To avoid the pitfalls of the proxy type, an arbitrary class type may also be adapted directly using fusion's intrinsic extension mechanism.



[13] Note that the type of a string literal is an array of const characters, not const char*. To get make_list to create a list with an element of a non-const array type one must use the ref wrapper (see boost::ref).


PrevUpHomeNext