1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Boost.Intrusive Iterator features</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 19. Boost.Intrusive">
<link rel="prev" href="thread_safety.html" title="Thread safety guarantees">
<link rel="next" href="equal_range_stability.html" title="Stability and insertion with hint in ordered associative containers with equivalent keys">
</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="thread_safety.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.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="equal_range_stability.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="intrusive.boost_intrusive_iterators"></a><a class="link" href="boost_intrusive_iterators.html" title="Boost.Intrusive Iterator features">Boost.Intrusive Iterator
features</a>
</h2></div></div></div>
<div class="toc"><dl class="toc">
<dt><span class="section"><a href="boost_intrusive_iterators.html#intrusive.boost_intrusive_iterators.null_forward_iterators">Null
forward iterators</a></span></dt>
<dt><span class="section"><a href="boost_intrusive_iterators.html#intrusive.boost_intrusive_iterators.scary_iterators">Scary
Iterators</a></span></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.boost_intrusive_iterators.null_forward_iterators"></a><a class="link" href="boost_intrusive_iterators.html#intrusive.boost_intrusive_iterators.null_forward_iterators" title="Null forward iterators">Null
forward iterators</a>
</h3></div></div></div>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> implements <a href="http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf" target="_top">C++14
Null Forward Iterators</a>, a feature that was introduced with C++14.
This means that equality and inequality comparison are defined over all iterators
for the same underlying sequence and the value initialized-iterators.
</p>
<p>
Value initialized iterators behave as if they refer past the end of the same
empty sequence:
</p>
<pre class="programlisting"><span class="identifier">list</span><span class="special"><</span><span class="identifier">MyType</span><span class="special">></span> <span class="identifier">l</span> <span class="special">=</span> <span class="special">{</span> <span class="special">...</span> <span class="special">};</span>
<span class="keyword">auto</span> <span class="identifier">ni</span> <span class="special">=</span> <span class="identifier">list</span><span class="special"><</span><span class="identifier">MyType</span><span class="special">>::</span><span class="identifier">iterator</span><span class="special">();</span>
<span class="keyword">auto</span> <span class="identifier">nd</span> <span class="special">=</span> <span class="identifier">list</span><span class="special"><</span><span class="identifier">MyType2</span><span class="special">>::</span><span class="identifier">iterator</span><span class="special">();</span>
<span class="identifier">ni</span> <span class="special">==</span> <span class="identifier">ni</span><span class="special">;</span> <span class="comment">// True.</span>
<span class="identifier">nd</span> <span class="special">!=</span> <span class="identifier">nd</span><span class="special">;</span> <span class="comment">// False.</span>
<span class="identifier">ni</span> <span class="special">==</span> <span class="identifier">nd</span><span class="special">;</span> <span class="comment">// Won't compile.</span>
</pre>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="intrusive.boost_intrusive_iterators.scary_iterators"></a><a class="link" href="boost_intrusive_iterators.html#intrusive.boost_intrusive_iterators.scary_iterators" title="Scary Iterators">Scary
Iterators</a>
</h3></div></div></div>
<p>
The paper N2913, titled <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf%2c" target="_top">SCARY
Iterator Assignment and Initialization</a>, proposed a requirement that
a standard container's iterator types have no dependency on any type argument
apart from the container's <code class="computeroutput"><span class="identifier">value_type</span></code>,
<code class="computeroutput"><span class="identifier">difference_type</span></code>, <code class="computeroutput"><span class="identifier">pointer</span> <span class="identifier">type</span></code>,
and <code class="computeroutput"><span class="identifier">const_pointer</span></code> type. In
particular, according to the proposal, the types of a standard container's
iterators should not depend on the container's <code class="computeroutput"><span class="identifier">key_compare</span></code>,
<code class="computeroutput"><span class="identifier">hasher</span></code>, <code class="computeroutput"><span class="identifier">key_equal</span></code>,
or <code class="computeroutput"><span class="identifier">allocator</span></code> types.
</p>
<p>
That paper demonstrated that SCARY operations were crucial to the performant
implementation of common design patterns using STL components. It showed
that implementations that support SCARY operations reduce object code bloat
by eliminating redundant specializations of iterator and algorithm templates.
</p>
<p>
<span class="bold"><strong>Boost.Intrusive</strong></span> containers are a bit different
from standard containers. In particular, they have no allocator parameter
and they can be configured with additional options not present in STL-like
containers. Thus <span class="bold"><strong>Boost.Intrusive</strong></span> offers
its own <code class="computeroutput"><span class="identifier">SCARY</span> <span class="identifier">iterator</span></code>
implementation, where iterator types don't change when the container is configured
with an option that does not alter the value <-> node transformation.
More concretely, the following options and conditions guarantee that iterator
types are unchanged:
</p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
<span class="bold"><strong>All containers</strong></span>: <code class="computeroutput"><span class="identifier">size_type</span><span class="special"><></span></code>, <code class="computeroutput"><span class="identifier">constant_time_size</span><span class="special"><></span></code>,
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">slist</span></code></strong></span>:
<code class="computeroutput"><span class="identifier">cache_last</span><span class="special"><></span></code>,
<code class="computeroutput"><span class="identifier">linear</span><span class="special"><></span></code>,
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">unordered_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code></strong></span>:
<code class="computeroutput"><span class="identifier">hash</span><span class="special"><></span></code>,
<code class="computeroutput"><span class="identifier">equal</span><span class="special"><></span></code>,
<code class="computeroutput"><span class="identifier">power_2_buckets</span><span class="special"><></span></code>,
<code class="computeroutput"><span class="identifier">cache_begin</span><span class="special"><></span></code>.
</li>
<li class="listitem">
<span class="bold"><strong>All tree-like containers</strong></span> (<code class="computeroutput"><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>,
<code class="computeroutput"><span class="identifier">avl_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>, <code class="computeroutput"><span class="identifier">sg_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>,
<code class="computeroutput"><span class="identifier">bs_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>, <code class="computeroutput"><span class="identifier">splay_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>,
<code class="computeroutput"><span class="identifier">treap_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>): <code class="computeroutput"><span class="identifier">compare</span><span class="special"><></span></code>.
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">treap_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code></strong></span>:
<code class="computeroutput"><span class="identifier">priority</span><span class="special"><></span></code>
</li>
<li class="listitem">
<span class="bold"><strong><code class="computeroutput"><span class="identifier">bs_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>,
<code class="computeroutput"><span class="identifier">sg_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>, <code class="computeroutput"><span class="identifier">treap_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code>,
<code class="computeroutput"><span class="identifier">splay_</span><span class="special">[</span><span class="identifier">multi</span><span class="special">]</span><span class="identifier">set</span></code></strong></span>: They share the same
iterator type when configured with the same options.
</li>
</ul></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 © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<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="thread_safety.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.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="equal_range_stability.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
