<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Notes</title>
<link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.75.2">
<link rel="home" href="../index.html" title="Chapter 1. Fusion 2.0">
<link rel="up" href="../index.html" title="Chapter 1. Fusion 2.0">
<link rel="prev" href="functional/generation/metafunctions/mk_unfused.html" title="make_unfused">
<link rel="next" href="change_log.html" title="Change log">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td>
<td align="center"><a href="../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="functional/generation/metafunctions/mk_unfused.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="change_log.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="fusion.notes"></a><a class="link" href="notes.html" title="Notes">Notes</a>
</h2></div></div></div>
<a name="fusion.notes.recursive_inlined_functions"></a><h4>
<a name="id1128689"></a>
<a class="link" href="notes.html#fusion.notes.recursive_inlined_functions">Recursive Inlined
Functions</a>
</h4>
<p>
An interesting peculiarity of functions like <a class="link" href="sequence/intrinsic/functions/at.html" title="at"><code class="computeroutput"><span class="identifier">at</span></code></a> when applied to a <a class="link" href="sequence/concepts/forward_sequence.html" title="Forward Sequence">Forward
Sequence</a> like <a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a>
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.
</p>
<a name="fusion.notes.overloaded_functions"></a><h4>
<a name="id1128730"></a>
<a class="link" href="notes.html#fusion.notes.overloaded_functions">Overloaded Functions</a>
</h4>
<p>
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, <code class="computeroutput"><span class="identifier">f</span><span class="special">(</span><span class="identifier">k</span><span class="special">)</span></code>, for each key <span class="emphasis"><em>type</em></span> <code class="computeroutput"><span class="identifier">k</span></code>. The compiler chooses the appropriate function
given a key, <code class="computeroutput"><span class="identifier">k</span></code>.
</p>
<a name="fusion.notes.tag_dispatching"></a><h4>
<a name="id1128783"></a>
<a class="link" href="notes.html#fusion.notes.tag_dispatching">Tag Dispatching</a>
</h4>
<p>
Tag dispatching is a generic programming technique for selecting template specializations.
There are typically 3 components involved in the tag dispatching mechanism:
</p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">
A type for which an appropriate template specialization is required
</li>
<li class="listitem">
A metafunction that associates the type with a tag type
</li>
<li class="listitem">
A template that is specialized for the tag type
</li>
</ol></div>
<p>
For example, the fusion <code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">begin</span></code> metafunction
is implemented as follows:
</p>
<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">Sequence</span><span class="special">></span>
<span class="keyword">struct</span> <span class="identifier">begin</span>
<span class="special">{</span>
<span class="keyword">typedef</span> <span class="keyword">typename</span>
<span class="identifier">result_of</span><span class="special">::</span><span class="identifier">begin_impl</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">traits</span><span class="special">::</span><span class="identifier">tag_of</span><span class="special"><</span><span class="identifier">Sequence</span><span class="special">>::</span><span class="identifier">type</span><span class="special">>::</span>
<span class="keyword">template</span> <span class="identifier">apply</span><span class="special"><</span><span class="identifier">Sequence</span><span class="special">>::</span><span class="identifier">type</span>
<span class="identifier">type</span><span class="special">;</span>
<span class="special">};</span>
</pre>
<p>
In the case:
</p>
<div class="orderedlist"><ol class="orderedlist" type="1">
<li class="listitem">
<code class="computeroutput"><span class="identifier">Sequence</span></code> is the type for
which a suitable implementation of <code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">begin_impl</span></code>
is required
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">traits</span><span class="special">::</span><span class="identifier">tag_of</span></code> is the metafunction that associates
<code class="computeroutput"><span class="identifier">Sequence</span></code> with an appropriate
tag
</li>
<li class="listitem">
<code class="computeroutput"><span class="identifier">result_of</span><span class="special">::</span><span class="identifier">begin_impl</span></code> is the template which is specialized
to provide an implementation for each tag type
</li>
</ol></div>
<a name="fusion.notes.extensibility"></a><h4>
<a name="id1129071"></a>
<a class="link" href="notes.html#fusion.notes.extensibility">Extensibility</a>
</h4>
<p>
Unlike <a href="http://www.boost.org/libs/mpl/index.html" target="_top">MPL</a>, 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 <a href="http://en.wikipedia.org/wiki/Standard_Template_Library" target="_top">STL</a>
and <a href="http://www.boost.org/libs/mpl/index.html" target="_top">MPL</a> on account
of the lazy nature of fusion <a class="link" href="algorithm.html" title="Algorithm">Algorithms</a>.
<a href="http://en.wikipedia.org/wiki/Standard_Template_Library" target="_top">STL</a>
containers extend themselves in place though member functions such as <a class="link" href="algorithm/transformation/functions/push_back.html" title="push_back"><code class="computeroutput"><span class="identifier">push_back</span></code></a> and <a class="link" href="algorithm/transformation/functions/insert.html" title="insert"><code class="computeroutput"><span class="identifier">insert</span></code></a>. <a href="http://www.boost.org/libs/mpl/index.html" target="_top">MPL</a>
sequences, on the other hand, are extended through "intrinsic" functions
that actually return whole sequences. <a href="http://www.boost.org/libs/mpl/index.html" target="_top">MPL</a>
is purely functional and can not have side effects. For example, <a href="http://www.boost.org/libs/mpl/index.html" target="_top">MPL</a>'s
<code class="computeroutput"><span class="identifier">push_back</span></code> does not actually
mutate an <code class="computeroutput"><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">vector</span></code>. It can't do that. Instead, it returns
an extended <code class="computeroutput"><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">vector</span></code>.
</p>
<p>
Like <a href="http://www.boost.org/libs/mpl/index.html" target="_top">MPL</a>, 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
<a class="link" href="view.html" title="View">Views</a>. <a class="link" href="view.html" title="View">Views</a>
are sequences that do not actually contain data, but instead impart an alternative
presentation over the data from one or more underlying sequences. <a class="link" href="view.html" title="View">Views</a>
are proxies. They provide an efficient yet purely functional way to work on
potentially expensive sequence operations. For example, given a <a class="link" href="container/vector.html" title="vector"><code class="computeroutput"><span class="identifier">vector</span></code></a>, Fusion's <a class="link" href="algorithm/transformation/functions/push_back.html" title="push_back"><code class="computeroutput"><span class="identifier">push_back</span></code></a> returns a <a class="link" href="view/joint_view.html" title="joint_view"><code class="computeroutput"><span class="identifier">joint_view</span></code></a>, instead of an actual extended
<a class="link" href="container/vector.html" title="vector"><code class="computeroutput"><span class="identifier">vector</span></code></a>.
A <a class="link" href="view/joint_view.html" title="joint_view"><code class="computeroutput"><span class="identifier">joint_view</span></code></a>
holds a reference to the original sequence plus the appended data --making
it very cheap to pass around.
</p>
<a name="fusion.notes.element_conversion"></a><h4>
<a name="id1129253"></a>
<a class="link" href="notes.html#fusion.notes.element_conversion">Element Conversion</a>
</h4>
<p>
Functions that take in elemental values to form sequences (e.g. <a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a>) convert their arguments
to something suitable to be stored as a sequence element. In general, the element
types are stored as plain values. Example:
</p>
<pre class="programlisting"><a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="number">1</span><span class="special">,</span> <span class="char">'x'</span><span class="special">)</span>
</pre>
<p>
returns a <a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a><code class="computeroutput"><span class="special"><</span><span class="keyword">int</span><span class="special">,</span>
<span class="keyword">char</span><span class="special">></span></code>.
</p>
<p>
There are a few exceptions, however.
</p>
<p>
<span class="bold"><strong>Arrays:</strong></span>
</p>
<p>
Array arguments are deduced to reference to const types. For example <sup>[<a name="id1129358" href="#ftn.id1129358" class="footnote">10</a>]</sup>:
</p>
<pre class="programlisting"><a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="string">"Donald"</span><span class="special">,</span> <span class="string">"Daisy"</span><span class="special">)</span>
</pre>
<p>
creates a <a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a>
of type
</p>
<pre class="programlisting"><a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a><span class="special"><</span><span class="keyword">const</span> <span class="keyword">char</span> <span class="special">(&)[</span><span class="number">7</span><span class="special">],</span> <span class="keyword">const</span> <span class="keyword">char</span> <span class="special">(&)[</span><span class="number">6</span><span class="special">]></span>
</pre>
<p>
<span class="bold"><strong>Function pointers:</strong></span>
</p>
<p>
Function pointers are deduced to the plain non-reference type (i.e. to plain
function pointer). Example:
</p>
<pre class="programlisting"><span class="keyword">void</span> <span class="identifier">f</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">i</span><span class="special">);</span>
<span class="special">...</span>
<a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(&</span><span class="identifier">f</span><span class="special">);</span>
</pre>
<p>
creates a <a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a>
of type
</p>
<pre class="programlisting"><a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a><span class="special"><</span><span class="keyword">void</span> <span class="special">(*)(</span><span class="keyword">int</span><span class="special">)></span>
</pre>
<a name="fusion.notes.boost__ref"></a><h4>
<a name="id1131042"></a>
<a class="link" href="notes.html#fusion.notes.boost__ref">boost::ref</a>
</h4>
<p>
Fusion's generation functions (e.g. <a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a>) by default stores the element
types as plain non-reference types. Example:
</p>
<pre class="programlisting"><span class="keyword">void</span> <span class="identifier">foo</span><span class="special">(</span><span class="keyword">const</span> <span class="identifier">A</span><span class="special">&</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">B</span><span class="special">&</span> <span class="identifier">b</span><span class="special">)</span> <span class="special">{</span>
<span class="special">...</span>
<a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">b</span><span class="special">)</span>
</pre>
<p>
creates a <a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a>
of type
</p>
<pre class="programlisting"><a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a><span class="special"><</span><span class="identifier">A</span><span class="special">,</span> <span class="identifier">B</span><span class="special">></span>
</pre>
<p>
Sometimes the plain non-reference type is not desired. You can use <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">ref</span></code>
and <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">cref</span></code> 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:
</p>
<p>
For example:
</p>
<pre class="programlisting"><span class="identifier">A</span> <span class="identifier">a</span><span class="special">;</span> <span class="identifier">B</span> <span class="identifier">b</span><span class="special">;</span> <span class="keyword">const</span> <span class="identifier">A</span> <span class="identifier">ca</span> <span class="special">=</span> <span class="identifier">a</span><span class="special">;</span>
<a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="identifier">cref</span><span class="special">(</span><span class="identifier">a</span><span class="special">),</span> <span class="identifier">b</span><span class="special">);</span> <span class="comment">// creates list<const A&, B>
</span><a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="identifier">ref</span><span class="special">(</span><span class="identifier">a</span><span class="special">),</span> <span class="identifier">b</span><span class="special">);</span> <span class="comment">// creates list<A&, B>
</span><a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="identifier">ref</span><span class="special">(</span><span class="identifier">a</span><span class="special">),</span> <span class="identifier">cref</span><span class="special">(</span><span class="identifier">b</span><span class="special">));</span> <span class="comment">// creates list<A&, const B&>
</span><a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="identifier">cref</span><span class="special">(</span><span class="identifier">ca</span><span class="special">));</span> <span class="comment">// creates list<const A&>
</span><a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a><span class="special">(</span><span class="identifier">ref</span><span class="special">(</span><span class="identifier">ca</span><span class="special">));</span> <span class="comment">// creates list<const A&>
</span></pre>
<p>
See <a href="http://www.boost.org/doc/html/ref.html" target="_top">Boost.Ref</a> for
details.
</p>
<div class="footnotes">
<br><hr width="100" align="left">
<div class="footnote"><p><sup>[<a name="ftn.id1129358" href="#id1129358" class="para">10</a>] </sup>
Note that the type of a string literal is an array of const characters, not
<code class="computeroutput"><span class="keyword">const</span> <span class="keyword">char</span><span class="special">*</span></code>. To get <a class="link" href="container/generation/functions/make_list.html" title="make_list"><code class="computeroutput"><span class="identifier">make_list</span></code></a> to create a <a class="link" href="container/list.html" title="list"><code class="computeroutput"><span class="identifier">list</span></code></a> with an element of a non-const
array type one must use the <code class="computeroutput"><span class="identifier">ref</span></code>
wrapper (see <a class="link" href="notes.html#fusion.notes.boost__ref"><code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">ref</span></code></a>).
</p></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2001-2007 Joel de Guzman, Dan Marsden, Tobias
Schwinger<p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="functional/generation/metafunctions/mk_unfused.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="change_log.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
