3 <meta http-equiv=
"Content-Type" content=
"text/html; charset=US-ASCII">
4 <title>Implementation
</title>
5 <link rel=
"stylesheet" href=
"../../../../../doc/src/boostbook.css" type=
"text/css">
6 <meta name=
"generator" content=
"DocBook XSL Stylesheets V1.74.0">
7 <link rel=
"home" href=
"../index.html" title=
"Chapter 1. Boost.Icl">
8 <link rel=
"up" href=
"../index.html" title=
"Chapter 1. Boost.Icl">
9 <link rel=
"prev" href=
"customization.html" title=
"Customization">
10 <link rel=
"next" href=
"implementation/complexity.html" title=
"Complexity">
12 <body bgcolor=
"white" text=
"black" link=
"#0000FF" vlink=
"#840084" alink=
"#0000FF">
13 <table cellpadding=
"2" width=
"100%"><tr>
14 <td valign=
"top"><img alt=
"Boost C++ Libraries" width=
"277" height=
"86" src=
"../../../../../boost.png"></td>
15 <td align=
"center"><a href=
"../../../../../index.html">Home
</a></td>
16 <td align=
"center"><a href=
"../../../../libraries.htm">Libraries
</a></td>
17 <td align=
"center"><a href=
"http://www.boost.org/users/people.html">People
</a></td>
18 <td align=
"center"><a href=
"http://www.boost.org/users/faq.html">FAQ
</a></td>
19 <td align=
"center"><a href=
"../../../../../more/index.htm">More
</a></td>
22 <div class=
"spirit-nav">
23 <a accesskey=
"p" href=
"customization.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=
"implementation/complexity.html"><img src=
"../../../../../doc/src/images/next.png" alt=
"Next"></a>
25 <div class=
"section boost_icl_implementation" lang=
"en">
26 <div class=
"titlepage"><div><div><h2 class=
"title" style=
"clear: both">
27 <a name=
"boost_icl.implementation"></a><a class=
"link" href=
"implementation.html" title=
"Implementation">Implementation
</a>
28 </h2></div></div></div>
30 <dt><span class=
"section"><a href=
"implementation.html#boost_icl.implementation.iterative_size">Iterative size
</a></span></dt>
31 <dt><span class=
"section"><a href=
"implementation/complexity.html">Complexity
</a></span></dt>
32 <dt><span class=
"section"><a href=
"implementation/inplace_and_infix_operators.html">Inplace
33 and infix operators
</a></span></dt>
36 The
<a class=
"link" href=
"interface.html" title=
"Interface">previous section
</a> gave an overview
37 over the interface of the
<span class=
"bold"><strong>icl
</strong></span> outlining
<a class=
"link" href=
"interface.html#boost_icl.interface.class_templates" title=
"Class templates">class templates
</a>,
<a class=
"link" href=
"interface/associated_types.html" title=
"Associated Types">associated types
</a> and
38 polymorphic
<a class=
"link" href=
"interface/function_synopsis.html" title=
"Function Synopsis">functions
39 and operators
</a>. In preparation to the
<a class=
"link" href=
"function_reference.html" title=
"Function Reference">next
40 section
</a>, that describes the
<span class=
"bold"><strong>icl's
</strong></span> polymorphic
41 functions in more detail together with
<span class=
"emphasis"><em><span class=
"bold"><strong>complexity
42 characteristics
</strong></span></em></span>, this section summarizes some general
43 information on implementation and performance.
45 <a name=
"boost_icl.implementation.stl_based_implementation"></a><h6>
46 <a name=
"id1130357"></a>
47 <a class=
"link" href=
"implementation.html#boost_icl.implementation.stl_based_implementation">STL based
51 The
<span class=
"bold"><strong>implementation
</strong></span> of the
<span class=
"bold"><strong>icl's
</strong></span>
52 containers is based on
<span class=
"bold"><strong>std::set
</strong></span> and
<span class=
"bold"><strong>std::map
</strong></span>. So the underlying data structure of interval
53 containers is a red black tree of intervals or interval value pairs. The element
54 containers
<a href=
"http://www.cplusplus.com/reference/stl/set/" target=
"_top"><code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">set
</span></code>
55 </a> and
<code class=
"computeroutput"><a class=
"link" href=
"../boost/icl/map.html" title=
"Class template map">icl::map
</a></code> are wrapper
56 classes of
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">set
</span></code> and
<code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">map
</span></code>. Interval
57 containers are then using
<a href=
"http://www.cplusplus.com/reference/stl/set/" target=
"_top"><code class=
"computeroutput"><span class=
"identifier">std
</span><span class=
"special">::
</span><span class=
"identifier">sets
</span></code></a>
58 of intervals or
<code class=
"computeroutput"><a class=
"link" href=
"../boost/icl/map.html" title=
"Class template map">icl::maps
</a></code> of interval
59 value pairs as implementing containers. So all the
<span class=
"emphasis"><em><span class=
"bold"><strong>complexity
60 characteristics
</strong></span></em></span> of icl containers are based on and limited
61 by the
<span class=
"emphasis"><em><span class=
"bold"><strong>red-black tree implementation
</strong></span></em></span>
62 of the underlying std::AssociativeContainers.
64 <div class=
"section boost_icl_implementation_iterative_size" lang=
"en">
65 <div class=
"titlepage"><div><div><h3 class=
"title">
66 <a name=
"boost_icl.implementation.iterative_size"></a><a class=
"link" href=
"implementation.html#boost_icl.implementation.iterative_size" title=
"Iterative size">Iterative size
</a>
67 </h3></div></div></div>
69 Throughout the documentation on complexity, big
<span class=
"emphasis"><em>O
</em></span> expressions
70 like
<span class=
"emphasis"><em>O(n)
</em></span> or
<span class=
"emphasis"><em>O(m log n)
</em></span> refer to
71 container sizes
<span class=
"emphasis"><em>n
</em></span> and
<span class=
"emphasis"><em>m
</em></span>. In this
72 documentation these sizes
<span class=
"emphasis"><em><span class=
"bold"><strong>do not
</strong></span></em></span>
73 denote to the familiar
<code class=
"computeroutput"><span class=
"identifier">size
</span></code>
74 function that returns the
<span class=
"emphasis"><em><span class=
"bold"><strong>number of elements
</strong></span></em></span>
75 of a container. Because for an interval container
77 <pre class=
"programlisting"><span class=
"identifier">interval_set
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">></span> <span class=
"identifier">mono
</span><span class=
"special">;
</span>
78 <span class=
"identifier">mono
</span> <span class=
"special">+=
</span> <span class=
"identifier">interval
</span><span class=
"special"><</span><span class=
"keyword">int
</span><span class=
"special">>::
</span><span class=
"identifier">closed
</span><span class=
"special">(
</span><span class=
"number">1</span><span class=
"special">,
</span><span class=
"number">5</span><span class=
"special">);
</span> <span class=
"comment">// {[
1 ...
5]}
79 </span><span class=
"identifier">mono
</span><span class=
"special">.
</span><span class=
"identifier">size
</span><span class=
"special">()
</span> <span class=
"special">==
</span> <span class=
"number">5</span><span class=
"special">;
</span> <span class=
"comment">// true,
5 elements
80 </span><span class=
"identifier">mono
</span><span class=
"special">.
</span><span class=
"identifier">interval_count
</span><span class=
"special">()
</span> <span class=
"special">==
</span> <span class=
"number">1</span><span class=
"special">;
</span> <span class=
"comment">// true, only one interval
85 it's size and the number of contained intervals is usually different. To
86 refer uniformly to a
<span class=
"emphasis"><em>size
</em></span> that matters for iteration,
87 which is the decisive kind of size concerning algorithmic behavior there
90 <pre class=
"programlisting"><span class=
"keyword">bool
</span> <span class=
"identifier">T
</span><span class=
"special">::
</span><span class=
"identifier">iterative_size
</span><span class=
"special">()
</span><span class=
"keyword">const
</span><span class=
"special">;
</span> <span class=
"comment">// Number of entities that can be iterated over.
93 for all element and interval containers of the icl. So for complexity statements
94 throughout the icl's documentation the sizes will be
<code class=
"computeroutput"><span class=
"identifier">iterative_sizes
</span></code>
95 and big
<span class=
"emphasis"><em>O
</em></span> expressions like
<span class=
"emphasis"><em>O(m log n)
</em></span>
98 <pre class=
"programlisting"><span class=
"identifier">n
</span> <span class=
"special">=
</span> <span class=
"identifier">y
</span><span class=
"special">.
</span><span class=
"identifier">iterative_size
</span><span class=
"special">();
</span>
99 <span class=
"identifier">m
</span> <span class=
"special">=
</span> <span class=
"identifier">x
</span><span class=
"special">.
</span><span class=
"identifier">iterative_size
</span><span class=
"special">();
</span>
102 for containers
<code class=
"computeroutput"><span class=
"identifier">y
</span></code> and
<code class=
"computeroutput"><span class=
"identifier">x
</span></code>. Note that
104 <pre class=
"programlisting"><span class=
"identifier">iterative_size
</span></pre>
106 refers to the primary entities, that we can iterate over. For interval containers
107 these are intervals or segments.
109 <pre class=
"programlisting"><span class=
"identifier">Itervative_size
</span></pre>
111 never refers to element iteration for interval containers.
115 <table xmlns:
rev=
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width=
"100%"><tr>
116 <td align=
"left"></td>
117 <td align=
"right"><div class=
"copyright-footer">Copyright
© 2007 -
2010 Joachim Faulhaber
<br>Copyright
© 1999 -
2006 Cortex Software GmbH
<p>
118 Distributed under the Boost Software License, Version
1.0. (See accompanying
119 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>)
124 <div class=
"spirit-nav">
125 <a accesskey=
"p" href=
"customization.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=
"implementation/complexity.html"><img src=
"../../../../../doc/src/images/next.png" alt=
"Next"></a>