File: Poco.LinearHashTable.html

package info (click to toggle)
poco-doc 1.3.6-1
  • links: PTS
  • area: main
  • in suites: buster, jessie, jessie-kfreebsd, squeeze, stretch, wheezy
  • size: 10,076 kB
  • ctags: 9,611
  • sloc: makefile: 31
file content (212 lines) | stat: -rw-r--r-- 16,046 bytes parent folder | download | duplicates (2)
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<title>Class Poco::LinearHashTable</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<meta name="author" content="Applied Informatics Software Engineering GmbH and Contributors"/>
<meta name="publisher" content="Applied Informatics Software Engineering GmbH and Contributors"/>
<meta name="copyright" content="Copyright (c) 2009, Applied Informatics Software Engineering GmbH and Contributors"/>
<meta name="language" content="en"/>
<meta name="date" content="2009-11-24"/>
<meta name="generator" content="PocoDoc"/>
<link rel="stylesheet" href="css/styles.css" type="text/css"/>
</head>
<body bgcolor="#ffffff" leftmargin="0" topmargin="0">
<div class="header">
<h1 class="namespace"><a href="Poco.html" class="namespace">Poco</a></h1>
<h1 class="template">template &lt; class Value, class HashFunc = Hash &lt; Value &gt; &gt;</h1>
<h1 class="symbol">class LinearHashTable</h1>
</div>
<div class="body">
<p>
<b>Library:</b> Foundation<br />
<b>Package:</b> Hashing<br />
<b>Header:</b> Poco/LinearHashTable.h</p>
<h2>Description</h2>
<div class="description">
<p>This class implements a linear hash table. </p>
<p>In a linear hash table, the available address space grows or shrinks dynamically. A linar hash table thus supports any number of insertions or deletions without lookup or insertion performance deterioration. </p>
<p>Linear hashing was discovered by Witold Litwin in 1980 and described in the paper LINEAR HASHING: A NEW TOOL FOR FILE AND TABLE ADDRESSING. </p>
<p>For more information on linear hashing, see &lt;<a href="http://en.wikipedia.org/wiki/Linear_hash" target="_blank">http://en.wikipedia.org/wiki/Linear_hash</a>&gt;. </p>
<p>The <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> is not thread safe. </p>
<p>Value must support comparison for equality. </p>
<p>Find, insert and delete operations are basically O(1) with regard to the total number of elements in the table, and O(N) with regard to the number of elements in the bucket where the element is stored. On average, every bucket stores one element; the exact number depends on the quality of the hash function. In most cases, the maximum number of elements in a bucket should not exceed 3. </p>
</div>
<h2>Member Summary</h2>
<p><b>Member Functions: </b><a href="Poco.LinearHashTable.html#7835" title="Poco::LinearHashTable::begin()">begin</a>, <a href="Poco.LinearHashTable.html#7854" title="Poco::LinearHashTable::bucketAddress()">bucketAddress</a>, <a href="Poco.LinearHashTable.html#7858" title="Poco::LinearHashTable::calcSize()">calcSize</a>, <a href="Poco.LinearHashTable.html#7851" title="Poco::LinearHashTable::clear()">clear</a>, <a href="Poco.LinearHashTable.html#7843" title="Poco::LinearHashTable::count()">count</a>, <a href="Poco.LinearHashTable.html#7853" title="Poco::LinearHashTable::empty()">empty</a>, <a href="Poco.LinearHashTable.html#7836" title="Poco::LinearHashTable::end()">end</a>, <a href="Poco.LinearHashTable.html#7847" title="Poco::LinearHashTable::erase()">erase</a>, <a href="Poco.LinearHashTable.html#7839" title="Poco::LinearHashTable::find()">find</a>, <a href="Poco.LinearHashTable.html#7845" title="Poco::LinearHashTable::insert()">insert</a>, <a href="Poco.LinearHashTable.html#7857" title="Poco::LinearHashTable::merge()">merge</a>, <a href="Poco.LinearHashTable.html#7831" title="Poco::LinearHashTable::operator =()">operator&nbsp;=</a>, <a href="Poco.LinearHashTable.html#7852" title="Poco::LinearHashTable::size()">size</a>, <a href="Poco.LinearHashTable.html#7856" title="Poco::LinearHashTable::split()">split</a>, <a href="Poco.LinearHashTable.html#7833" title="Poco::LinearHashTable::swap()">swap</a></p>
<h2>Nested Classes</h2>
<h3><a href="Poco.LinearHashTable.ConstIterator.html" class="class">class ConstIterator</a></h3>
<p>&nbsp;<a href="Poco.LinearHashTable.ConstIterator.html"><img src="images/arrow.gif" alt="more..." style="vertical-align:baseline;" border="0" /> </a></p>
<h3><a href="Poco.LinearHashTable.Iterator.html" class="class">class Iterator</a></h3>
<p>&nbsp;<a href="Poco.LinearHashTable.Iterator.html"><img src="images/arrow.gif" alt="more..." style="vertical-align:baseline;" border="0" /> </a></p>
<h2>Types</h2>
<h3><a name="7779">Bucket</a></h3>
<p class="decl">typedef std::vector &lt; Value &gt; <a href="Poco.LinearHashTable.html#7779" title="Poco::LinearHashTable::Bucket">Bucket</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7781">BucketIterator</a></h3>
<p class="decl">typedef typename Bucket::iterator <a href="Poco.LinearHashTable.html#7781" title="Poco::LinearHashTable::BucketIterator">BucketIterator</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7780">BucketVec</a></h3>
<p class="decl">typedef std::vector &lt; <a href="Poco.LinearHashTable.html#7779" title="Poco::LinearHashTable::Bucket">Bucket</a> &gt; <a href="Poco.LinearHashTable.html#7780" title="Poco::LinearHashTable::BucketVec">BucketVec</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7782">BucketVecIterator</a></h3>
<p class="decl">typedef typename BucketVec::iterator <a href="Poco.LinearHashTable.html#7782" title="Poco::LinearHashTable::BucketVecIterator">BucketVecIterator</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7777">ConstPointer</a></h3>
<p class="decl">typedef const Value * <a href="Poco.LinearHashTable.html#7777" title="Poco::LinearHashTable::ConstPointer">ConstPointer</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7775">ConstReference</a></h3>
<p class="decl">typedef const Value &amp; <a href="Poco.LinearHashTable.html#7775" title="Poco::LinearHashTable::ConstReference">ConstReference</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7778">Hash</a></h3>
<p class="decl">typedef HashFunc <a href="Poco.LinearHashTable.html#7778" title="Poco::LinearHashTable::Hash">Hash</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7776">Pointer</a></h3>
<p class="decl">typedef Value * <a href="Poco.LinearHashTable.html#7776" title="Poco::LinearHashTable::Pointer">Pointer</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7774">Reference</a></h3>
<p class="decl">typedef Value &amp; <a href="Poco.LinearHashTable.html#7774" title="Poco::LinearHashTable::Reference">Reference</a>;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7773">ValueType</a></h3>
<p class="decl">typedef Value <a href="Poco.LinearHashTable.html#7773" title="Poco::LinearHashTable::ValueType">ValueType</a>;</p>
<div class="description">
<p></p>
</div>
<h2>Constructors</h2>
<h3><a name="7826">LinearHashTable</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a>(<br />&nbsp;&nbsp;&nbsp;&nbsp;std::size_t initialReserve = 64<br />);</p>
<div class="description">
<p>Creates the <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a>, using the given initialReserve. </p>
</div>
<h3><a name="7828">LinearHashTable</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a>(<br />&nbsp;&nbsp;&nbsp;&nbsp;const <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> &amp; table<br />);</p>
<div class="description">
<p>Creates the <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> by copying another one. </p>
</div>
<h2>Destructor</h2>
<h3><a name="7830">~LinearHashTable</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">~<a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a>();</p>
<div class="description">
<p>Destroys the <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a>. </p>
</div>
<h2>Member Functions</h2>
<h3><a name="7835">begin</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.ConstIterator.html" title="class Poco::LinearHashTable::ConstIterator">ConstIterator</a> begin() const;</p>
<div class="description">
<p>Returns an iterator pointing to the first entry, if one exists. </p>
</div>
<h3><a name="7837">begin</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.Iterator.html" title="class Poco::LinearHashTable::Iterator">Iterator</a> begin();</p>
<div class="description">
<p>Returns an iterator pointing to the first entry, if one exists. </p>
</div>
<h3><a name="7851">clear</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">void clear();</p>
<div class="description">
<p>Erases all elements. </p>
</div>
<h3><a name="7843">count</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">std::size_t count(<br />&nbsp;&nbsp;&nbsp;&nbsp;const Value &amp; value<br />) const;</p>
<div class="description">
<p>Returns the number of elements with the given value, with is either 1 or 0. </p>
</div>
<h3><a name="7853">empty</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">bool empty() const;</p>
<div class="description">
<p>Returns true if and only if the table is empty. </p>
</div>
<h3><a name="7836">end</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.ConstIterator.html" title="class Poco::LinearHashTable::ConstIterator">ConstIterator</a> end() const;</p>
<div class="description">
<p>Returns an iterator pointing to the end of the table. </p>
</div>
<h3><a name="7838">end</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.Iterator.html" title="class Poco::LinearHashTable::Iterator">Iterator</a> end();</p>
<div class="description">
<p>Returns an iterator pointing to the end of the table. </p>
</div>
<h3><a name="7847">erase</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">void erase(<br />&nbsp;&nbsp;&nbsp;&nbsp;<a href="Poco.LinearHashTable.Iterator.html" title="class Poco::LinearHashTable::Iterator">Iterator</a> it<br />);</p>
<div class="description">
<p>Erases the element pointed to by it. </p>
</div>
<h3><a name="7849">erase</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">void erase(<br />&nbsp;&nbsp;&nbsp;&nbsp;const Value &amp; value<br />);</p>
<div class="description">
<p>Erases the element with the given value, if it exists. </p>
</div>
<h3><a name="7839">find</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.ConstIterator.html" title="class Poco::LinearHashTable::ConstIterator">ConstIterator</a> find(<br />&nbsp;&nbsp;&nbsp;&nbsp;const Value &amp; value<br />) const;</p>
<div class="description">
<p>Finds an entry in the table. </p>
</div>
<h3><a name="7841">find</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.Iterator.html" title="class Poco::LinearHashTable::Iterator">Iterator</a> find(<br />&nbsp;&nbsp;&nbsp;&nbsp;const Value &amp; value<br />);</p>
<div class="description">
<p>Finds an entry in the table. </p>
</div>
<h3><a name="7845">insert</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">std::pair &lt; <a href="Poco.LinearHashTable.Iterator.html" title="class Poco::LinearHashTable::Iterator">Iterator</a>, bool &gt; insert(<br />&nbsp;&nbsp;&nbsp;&nbsp;const Value &amp; value<br />);</p>
<div class="description">
<p>Inserts an element into the table. </p>
<p>If the element already exists in the table, a pair(iterator, false) with iterator pointing to the  existing element is returned. Otherwise, the element is inserted an a  pair(iterator, true) with iterator pointing to the new element is returned. </p>
</div>
<h3><a name="7831">operator =</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl"><a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> &amp; operator = (<br />&nbsp;&nbsp;&nbsp;&nbsp;const <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> &amp; table<br />);</p>
<div class="description">
<p>Assigns another <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a>. </p>
</div>
<h3><a name="7852">size</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">std::size_t size() const;</p>
<div class="description">
<p>Returns the number of elements in the table. </p>
</div>
<h3><a name="7833">swap</a> <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">void swap(<br />&nbsp;&nbsp;&nbsp;&nbsp;<a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> &amp; table<br />);</p>
<div class="description">
<p>Swaps the <a href="Poco.LinearHashTable.html" title="class Poco::LinearHashTable">LinearHashTable</a> with another one. </p>
</div>
<h3><a name="7854">bucketAddress</a> <img src="images/protected.gif" alt="protected" title="protected" style="vertical-align:baseline;" border="0" />  <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">std::size_t bucketAddress(<br />&nbsp;&nbsp;&nbsp;&nbsp;const Value &amp; value<br />) const;</p>
<div class="description">
<p></p>
</div>
<h3><a name="7858">calcSize</a> <img src="images/protected.gif" alt="protected" title="protected" style="vertical-align:baseline;" border="0" />  <img src="images/static.gif" alt="static" title="static" style="vertical-align:baseline;" border="0" />  <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">static std::size_t calcSize(<br />&nbsp;&nbsp;&nbsp;&nbsp;std::size_t initialSize<br />);</p>
<div class="description">
<p></p>
</div>
<h3><a name="7857">merge</a> <img src="images/protected.gif" alt="protected" title="protected" style="vertical-align:baseline;" border="0" />  <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">void merge();</p>
<div class="description">
<p></p>
</div>
<h3><a name="7856">split</a> <img src="images/protected.gif" alt="protected" title="protected" style="vertical-align:baseline;" border="0" />  <img src="images/inline.gif" alt="inline" title="inline" style="vertical-align:baseline;" border="0" /> </h3>
<p class="decl">void split();</p>
<div class="description">
<p></p>
</div>
<p class="footer">POCO C++ Libraries 1.3.6-all<br />
Copyright &copy; 2009, <a href="http://pocoproject.org/" target="_blank">Applied Informatics Software Engineering GmbH and Contributors</a></p>

</div>
</body>
</html>