| Index: gcc/libstdc++-v3/doc/html/ext/pb_ds/trie_based_containers.html
|
| diff --git a/gcc/libstdc++-v3/doc/html/ext/pb_ds/trie_based_containers.html b/gcc/libstdc++-v3/doc/html/ext/pb_ds/trie_based_containers.html
|
| deleted file mode 100644
|
| index 72bdd069779bc020ccf859ce7602e6e5c24bb94b..0000000000000000000000000000000000000000
|
| --- a/gcc/libstdc++-v3/doc/html/ext/pb_ds/trie_based_containers.html
|
| +++ /dev/null
|
| @@ -1,241 +0,0 @@
|
| -<!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" xml:lang="en" lang="en">
|
| -<head>
|
| - <meta name="generator" content=
|
| - "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
|
| -
|
| - <title>Trie-Based Containers</title>
|
| - <meta http-equiv="Content-Type" content=
|
| - "text/html; charset=us-ascii" />
|
| - </head>
|
| -
|
| -<body>
|
| - <div id="page">
|
| - <h1>Trie Design</h1>
|
| -
|
| - <h2><a name="overview" id="overview">Overview</a></h2>
|
| -
|
| - <p>The trie-based container has the following declaration:</p>
|
| - <pre>
|
| -<b>template</b><
|
| - <b>typename</b> Key,
|
| - <b>typename</b> Mapped,
|
| - <b>typename</b> Cmp_Fn = std::less<Key>,
|
| - <b>typename</b> Tag = <a href="pat_trie_tag.html">pat_trie_tag</a>,
|
| - <b>template</b><
|
| - <b>typename</b> Const_Node_Iterator,
|
| - <b>typename</b> Node_Iterator,
|
| - <b>typename</b> E_Access_Traits_,
|
| - <b>typename</b> Allocator_>
|
| - <b>class</b> Node_Update = <a href=
|
| -"null_trie_node_update.html">null_trie_node_update</a>,
|
| - <b>typename</b> Allocator = std::allocator<<b>char</b>> >
|
| -<b>class</b> <a href=
|
| -"trie.html">trie</a>;
|
| -</pre>
|
| -
|
| - <p>The parameters have the following meaning:</p>
|
| -
|
| - <ol>
|
| - <li><tt>Key</tt> is the key type.</li>
|
| -
|
| - <li><tt>Mapped</tt> is the mapped-policy, and is explained in
|
| - <a href="tutorial.html#assoc_ms">Tutorial::Associative
|
| - Containers::Associative Containers Others than Maps</a>.</li>
|
| -
|
| - <li><tt>E_Access_Traits</tt> is described in <a href=
|
| - "#e_access_traits">Element-Access Traits</a>.</li>
|
| -
|
| - <li><tt>Tag</tt> specifies which underlying data structure
|
| - to use, and is described shortly.</li>
|
| -
|
| - <li><tt>Node_Update</tt> is a policy for updating node
|
| - invariants. This is described in <a href="#invariants">Node
|
| - Invariants</a>.</li>
|
| -
|
| - <li><tt>Allocator</tt> is an allocator
|
| - type.</li>
|
| - </ol>
|
| -
|
| - <p>The <tt>Tag</tt> parameter specifies which underlying
|
| - data structure to use. Instantiating it by <a href=
|
| - "pat_trie_tag.html">pat_trie_tag</a>, specifies an
|
| - underlying PATRICIA trie (explained shortly); any other tag is
|
| - currently illegal.</p>
|
| - <hr />
|
| -
|
| - <p>Following is a description of a (PATRICIA) trie
|
| - (<tt>pb_ds</tt> follows specifically [<a href=
|
| - "references.html#okasaki98mereable">okasaki98mereable</a>] and
|
| - [<a href=
|
| - "references.html#filliatre2000ptset">filliatre2000ptset</a>]).</p>
|
| -
|
| - <p>A (PATRICIA) trie is similar to a tree, but with the
|
| - following differences:</p>
|
| -
|
| - <ol>
|
| - <li>It explicitly views keys as a sequence of elements.
|
| - <i>E.g.</i>, a trie can view a string as a sequence of
|
| - characters; a trie can view a number as a sequence of
|
| - bits.</li>
|
| -
|
| - <li>It is not (necessarily) binary. Each node has fan-out <i>n
|
| - + 1</i>, where <i>n</i> is the number of distinct
|
| - elements.</li>
|
| -
|
| - <li>It stores values only at leaf nodes.</li>
|
| -
|
| - <li>Internal nodes have the properties that A) each has at
|
| - least two children, and B) each shares the same prefix with
|
| - any of its descendant.</li>
|
| - </ol>
|
| -
|
| - <p><a href="#e_access_traits">Element-Access Traits</a> shows
|
| - an example of such a trie.</p>
|
| -
|
| - <p>A (PATRICIA) trie has some useful properties:</p>
|
| -
|
| - <ol>
|
| - <li>It can be configured to use large node fan-out, giving it
|
| - very efficient find performance (albeit at insertion
|
| - complexity and size).</li>
|
| -
|
| - <li>It works well for common-prefix keys.</li>
|
| -
|
| - <li>It can support efficiently queries such as which keys
|
| - match a certain prefix. This is sometimes useful in
|
| - file systems and routers.</li>
|
| - </ol>
|
| -
|
| - <p>(We would like to thank Matt Austern for the suggestion to
|
| - include tries.)</p>
|
| -
|
| - <h2><a name="e_access_traits" id=
|
| - "e_access_traits">Element-Access Traits</a></h2>
|
| -
|
| - <p>A trie inherently views its keys as sequences of elements.
|
| - For example, a trie can view a string as a sequence of
|
| - characters. A trie needs to map each of <i>n</i> elements to a
|
| - number in <i>{0, n - 1}</i>. For example, a trie can map a
|
| - character <tt>c</tt> to
|
| - <tt>static_cast<size_t>(c)</tt>.</p>
|
| -
|
| - <p>Seemingly, then, a trie can assume that its keys support
|
| - (const) iterators, and that the <tt>value_type</tt> of this
|
| - iterator can be cast to a <tt>size_t</tt>. There are several
|
| - reasons, though, to decouple the mechanism by which the trie
|
| - accesses its keys' elements from the trie:</p>
|
| -
|
| - <ol>
|
| - <li>In some cases, the numerical value of an element is
|
| - inappropriate. Consider a trie storing DNA strings. It is
|
| - logical to use a trie with a fan-out of <i>5 = 1 + |{'A', 'C',
|
| - 'G', 'T'}|</i>. This requires mapping 'T' to 3, though.</li>
|
| -
|
| - <li>In some cases the keys' iterators are different than what
|
| - is needed. For example, a trie can be used to search for
|
| - common <u>suffixes</u>, by using strings'
|
| - <tt>reverse_iterator</tt>. As another example, a trie mapping
|
| - UNICODE strings would have a huge fan-out if each node would
|
| - branch on a UNICODE character; instead, one can define an
|
| - iterator iterating over 8-bit (or less) groups.</li>
|
| - </ol>
|
| -
|
| - <p><a href=
|
| - "trie.html">trie</a> is,
|
| - consequently, parametrized by <tt>E_Access_Traits</tt> -
|
| - traits which instruct how to access sequences' elements.
|
| - <a href=
|
| - "string_trie_e_access_traits.html"><tt>string_trie_e_access_traits</tt></a>
|
| - is a traits class for strings. Each such traits define some
|
| - types, <i>e.g.</i>,</p>
|
| - <pre>
|
| -<b>typename</b> E_Access_Traits::const_iterator
|
| -</pre>
|
| -
|
| - <p>is a const iterator iterating over a key's elements. The
|
| - traits class must also define methods for obtaining an iterator
|
| - to the first and last element of a key.</p>
|
| -
|
| - <p>Figure <a href="#pat_trie">A PATRICIA trie</a> shows a
|
| - (PATRICIA) trie resulting from inserting the words: "I wish
|
| - that I could ever see a poem lovely as a trie" (which,
|
| - unfortunately, does not rhyme).</p>
|
| -
|
| - <p>The leaf nodes contain values; each internal node contains
|
| - two <tt><b>typename</b> E_Access_Traits::const_iterator</tt>
|
| - objects, indicating the maximal common prefix of all keys in
|
| - the sub-tree. For example, the shaded internal node roots a
|
| - sub-tree with leafs "a" and "as". The maximal common prefix is
|
| - "a". The internal node contains, consequently, to const
|
| - iterators, one pointing to <tt>'a'</tt>, and the other to
|
| - <tt>'s'</tt>.</p>
|
| -
|
| - <h6 class="c1"><a name="pat_trie" id="pat_trie"><img src=
|
| - "pat_trie.png" alt="no image" /></a></h6>
|
| -
|
| - <h6 class="c1">A PATRICIA trie.</h6>
|
| -
|
| - <h2><a name="invariants" id="invariants">Node
|
| - Invariants</a></h2>
|
| -
|
| - <p>Trie-based containers support node invariants, as do
|
| - tree-based containers (see <a href=
|
| - "tree_based_containers.html#invariants">Tree-Based
|
| - Containers::Node Invariants</a>). There are two minor
|
| - differences, though, which, unfortunately, thwart sharing them
|
| - sharing the same node-updating policies:</p>
|
| -
|
| - <ol>
|
| - <li>A trie's <tt>Node_Update</tt> template-template
|
| - parameter is parametrized by <tt>E_Access_Traits</tt>, while
|
| - a tree's <tt>Node_Update</tt> template-template parameter is
|
| - parametrized by <tt>Cmp_Fn</tt>.</li>
|
| -
|
| - <li>Tree-based containers store values in all nodes, while
|
| - trie-based containers (at least in this implementation) store
|
| - values in leafs.</li>
|
| - </ol>
|
| -
|
| - <p>Figure <a href="#trie_node_update_cd">A trie and its update
|
| - policy</a> shows the scheme, as well as some predefined
|
| - policies (which are explained below).</p>
|
| -
|
| - <h6 class="c1"><a name="trie_node_update_cd" id=
|
| - "trie_node_update_cd"><img src=
|
| - "trie_node_update_policy_cd.png" alt="no image" /></a></h6>
|
| -
|
| - <h6 class="c1">A trie and its update policy.</h6>
|
| -
|
| - <p><tt>pb_ds</tt> offers the following pre-defined trie node
|
| - updating policies:</p>
|
| -
|
| - <ol>
|
| - <li><a href=
|
| - "trie_order_statistics_node_update.html"><tt>trie_order_statistics_node_update</tt></a>
|
| - supports order statistics.</li>
|
| -
|
| - <li><a href=
|
| - "trie_prefix_search_node_update.html"><tt>trie_prefix_search_node_update</tt></a>
|
| - supports searching for ranges that match a given prefix. See
|
| - <a href=
|
| - "http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/ext/pb_ds/example/trie_prefix_search.cc"><tt>trie_prefix_search.cc</tt></a>.</li>
|
| -
|
| - <li><a href=
|
| - "null_trie_node_update.html"><tt>null_trie_node_update</tt></a>
|
| - is the null node updater.</li>
|
| - </ol>
|
| -
|
| - <h2><a name="add_methods" id="add_methods">Additional
|
| - Methods</a></h2>
|
| -
|
| - <p>Trie-based containers support split and join methods; the
|
| - rationale is equal to that of tree-based containers supporting
|
| - these methods (see <a href=
|
| - "tree_based_containers.html#add_methods">Tree-Based
|
| - Containers::Additional Methods</a>).</p>
|
| - </div>
|
| -</body>
|
| -</html>
|
|
|
Chromium Code Reviews
Issue 3050029:
[gcc] GCC 4.5.0=>4.5.1 (Closed)
Base URL: ssh://git@gitrw.chromium.org:9222/nacl-toolchain.git