|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r61241 - in sandbox/tokenmap/libs/tokenmap/doc: . html html/tokenmap
From: sl_at_[hidden]
Date: 2010-04-13 08:53:32
Author: sl_
Date: 2010-04-13 08:53:29 EDT (Tue, 13 Apr 2010)
New Revision: 61241
URL: http://svn.boost.org/trac/boost/changeset/61241
Log:
doc tweaks
Text files modified:
sandbox/tokenmap/libs/tokenmap/doc/html/index.html | 36 +++++++++++++++---------------------
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html | 6 +++---
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html | 2 +-
sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html | 10 +++++-----
sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk | 12 ++++++------
5 files changed, 30 insertions(+), 36 deletions(-)
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/index.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/index.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/index.html 2010-04-13 08:53:29 EDT (Tue, 13 Apr 2010)
@@ -27,7 +27,7 @@
</h3></div></div>
<div><p class="copyright">Copyright © 2009 Slawomir Lisznianski</p></div>
<div><div class="legalnotice">
-<a name="id472187"></a><p>
+<a name="id501064"></a><p>
Distributed under the Boost Software License, Version 1.0. (See accompanying
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
</p>
@@ -54,47 +54,41 @@
</h2></div></div></div>
<p>
A <code class="computeroutput"><span class="identifier">tokenmap</span></code> is a data structure
- that uniquely maps pseudo-random integer keys to values.
+ that uniquely maps internally generated integer keys to values.
</p>
<p>
- Unlike other dictionary-like containers such as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> or
- Boost.Unordered,
- a <code class="computeroutput"><span class="identifier">tokenmap</span></code> generates the keys
- (also called “<span class="quote">tokens</span>”) for values by an internal, pseudo-random
- algorithm rather than relying on the user to provide them; that is, when a
- new value is inserted into a <code class="computeroutput"><span class="identifier">tokenmap</span></code>,
- the <code class="computeroutput"><span class="identifier">tokenmap</span></code> generates a key
- for the value in some unspecified way and returns this key to the caller. Returned
- keys, which uniquely map to values, can later be used to retrieve the corresponding
- value in a very efficient lookup.
+ Unlike typical dictionary-like containers such as <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> or
+ <code class="computeroutput"><span class="identifier">boost_unordered</span></code>, a <code class="computeroutput"><span class="identifier">tokenmap</span></code> generates keys internally (called
+ <code class="computeroutput"><span class="identifier">tokens</span></code>) for stored values.
+ The keys are pseudo-random in appearance yet have the property of allowing
+ the container a very efficient look-up, in the order of indexing within a C-array.
</p>
<p>
<code class="literal">tokenmap</code>s have the following properties:
</p>
<div class="orderedlist"><ol type="1">
<li>
- No two tokens map to the same value (<code class="computeroutput"><span class="identifier">tokenmap</span></code>
- differs from <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">multimap</span></code> in this respect)
+ No two tokens map to the same value; in essence, <code class="computeroutput"><span class="identifier">tokenmap</span></code>
+ is a perfect hash container.
</li>
<li>
The returned tokens are <span class="emphasis"><em>stable</em></span> (a token will always
map to the corresponding value regardless of how the <code class="computeroutput"><span class="identifier">tokenmap</span></code>
- was modified since the token was generated)
+ was modified since the token was generated).
</li>
<li>
- Lookups are much faster - sometimes 30 times faster - than <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code>
- lookups
+ Lookups are extremely efficient - sometimes 30 times faster - compared to
+ <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">map</span></code> find.
</li>
</ol></div>
<p>
- The second property, also called the <span class="emphasis"><em>perfect hashing property</em></span>,
- requires special support from the container, as described on the <a class="link" href="tokenmap/background.html" title="Background">Background</a>
- page.
+ The mechanism of how the first and second properties are implemented is described
+ in the <a class="link" href="tokenmap/background.html" title="Background">Background</a> section.
</p>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: April 04, 2010 at 13:59:52 GMT</small></p></td>
+<td align="left"><p><small>Last revised: April 13, 2010 at 12:53:00 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/background.html 2010-04-13 08:53:29 EDT (Tue, 13 Apr 2010)
@@ -139,7 +139,7 @@
hashing property is preserved.
</p>
<a name="tokenmap.background.analysis_of_simple_strategy.modular_arithmetic_notation"></a><h5>
-<a name="id481365"></a>
+<a name="id510281"></a>
<a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.modular_arithmetic_notation">Modular
arithmetic notation</a>
</h5>
@@ -153,7 +153,7 @@
the set of all integers that are congruent modulo <span class="emphasis"><em>s</em></span>.
</p>
<a name="tokenmap.background.analysis_of_simple_strategy.proposition_1__perfect_hashing_is_preserved_with_multiples_of_the_old_store_length"></a><h5>
-<a name="id481449"></a>
+<a name="id510364"></a>
<a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.proposition_1__perfect_hashing_is_preserved_with_multiples_of_the_old_store_length">Proposition
1: Perfect hashing is preserved with multiples of the old store length</a>
</h5>
@@ -212,7 +212,7 @@
so [<span class="emphasis"><em>x</em></span>]<sub><span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub></sub> equals [<span class="emphasis"><em>y</em></span>]<sub><span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub></sub>. ∎
</p>
<a name="tokenmap.background.analysis_of_simple_strategy.__emphasis_s__emphasis_____quickbook_escape_prefix____subscript__emphasis_k__emphasis___subscript_____quickbook_escape_postfix_____that_preserves_perfect_hashing_after_arbitrary_rehashes"></a><h5>
-<a name="id481719"></a>
+<a name="id510634"></a>
<a class="link" href="background.html#tokenmap.background.analysis_of_simple_strategy.__emphasis_s__emphasis_____quickbook_escape_prefix____subscript__emphasis_k__emphasis___subscript_____quickbook_escape_postfix_____that_preserves_perfect_hashing_after_arbitrary_rehashes">{<span class="emphasis"><em>s</em></span><sub><span class="emphasis"><em>k</em></span></sub>}
that preserves perfect hashing after arbitrary rehashes</a>
</h5>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/examples_.html 2010-04-13 08:53:29 EDT (Tue, 13 Apr 2010)
@@ -32,7 +32,7 @@
them:
</p>
<div class="table">
-<a name="id483388"></a><p class="title"><b>Table 1.1. Tutorial examples</b></p>
+<a name="id512303"></a><p class="title"><b>Table 1.1. Tutorial examples</b></p>
<div class="table-contents"><table class="table" summary="Tutorial examples">
<colgroup>
<col>
Modified: sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/html/tokenmap/reference.html 2010-04-13 08:53:29 EDT (Tue, 13 Apr 2010)
@@ -27,7 +27,7 @@
<a name="tokenmap.reference"></a><a class="link" href="reference.html" title="Reference">Reference</a>
</h2></div></div></div>
<a name="tokenmap.reference.headers"></a><h4>
-<a name="id482382"></a>
+<a name="id511297"></a>
<a class="link" href="reference.html#tokenmap.reference.headers">Headers</a>
</h4>
<p>
@@ -36,7 +36,7 @@
to boost namespace.
</p>
<a name="tokenmap.reference.synopsis"></a><h4>
-<a name="id482409"></a>
+<a name="id511324"></a>
<a class="link" href="reference.html#tokenmap.reference.synopsis">Synopsis</a>
</h4>
<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> <span class="special">{</span>
@@ -83,15 +83,15 @@
</span><span class="special">}</span> <span class="comment">// namespace boost
</span></pre>
<a name="tokenmap.reference.class_template_tokenmap"></a><h4>
-<a name="id482996"></a>
+<a name="id511912"></a>
<a class="link" href="reference.html#tokenmap.reference.class_template_tokenmap">Class template tokenmap</a>
</h4>
<a name="tokenmap.reference.nested_types"></a><h4>
-<a name="id483011"></a>
+<a name="id511926"></a>
<a class="link" href="reference.html#tokenmap.reference.nested_types">Nested types</a>
</h4>
<a name="tokenmap.reference.constructors__copy_and_assignment"></a><h4>
-<a name="id483025"></a>
+<a name="id511941"></a>
<a class="link" href="reference.html#tokenmap.reference.constructors__copy_and_assignment">Constructors,
copy and assignment</a>
</h4>
Modified: sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk
==============================================================================
--- sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk (original)
+++ sandbox/tokenmap/libs/tokenmap/doc/tokenmap.qbk 2010-04-13 08:53:29 EDT (Tue, 13 Apr 2010)
@@ -99,17 +99,17 @@
[section Description]
-A `tokenmap` is a data structure that uniquely maps pseudo-random integer keys to values.
+A `tokenmap` is a data structure that uniquely maps internally generated integer keys to values.
-Unlike other dictionary-like containers such as `std::map` or _boost_unordered_, a `tokenmap` generates the keys (also called ["tokens]) for values by an internal, pseudo-random algorithm rather than relying on the user to provide them; that is, when a new value is inserted into a `tokenmap`, the `tokenmap` generates a key for the value in some unspecified way and returns this key to the caller. Returned keys, which uniquely map to values, can later be used to retrieve the corresponding value in a very efficient lookup.
+Unlike typical dictionary-like containers such as `std::map` or `boost_unordered`, a `tokenmap` generates keys internally (called `tokens`) for stored values. The keys are pseudo-random in appearance yet have the property of allowing the container a very efficient look-up, in the order of indexing within a C-array.
[^tokenmap]s have the following properties:
-# No two tokens map to the same value (`tokenmap` differs from `std::multimap` in this respect)
-# The returned tokens are /stable/ (a token will always map to the corresponding value regardless of how the `tokenmap` was modified since the token was generated)
-# Lookups are much faster - sometimes 30 times faster - than `std::map` lookups
+# No two tokens map to the same value; in essence, `tokenmap` is a perfect hash container.
+# The returned tokens are /stable/ (a token will always map to the corresponding value regardless of how the `tokenmap` was modified since the token was generated).
+# Lookups are extremely efficient - sometimes 30 times faster - compared to `std::map` find.
-The second property, also called the /perfect hashing property/, requires special support from the container, as described on the [link tokenmap.background Background] page.
+The mechanism of how the first and second properties are implemented is described in the [link tokenmap.background Background] section.
[endsect]
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk