1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
6 <meta name="generator" content=
7 "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
9 <title>trie_prefix_search_node_update Interface</title>
10 <meta http-equiv="Content-Type" content=
11 "text/html; charset=us-ascii" />
16 <h1><tt>trie_prefix_search_node_update</tt> Interface</h1>
18 <p>A node updater that allows tries to be searched for the
19 range of values that match a certain prefix.</p>
21 <p>Defined in: <a href=
22 "../../../../include/ext/pb_ds/trie_policy.hpp"><tt>trie_policy.hpp</tt></a></p>
24 <h2><a name="link1" id="link1">Template Parameters</a></h2>
26 <table class="c1" width="100%" border="1" summary=
27 "Template Parameters">
29 <td width="20%" align="left"><b>Parameter</b></td>
31 <td width="50%" align="left"><b>Description</b></td>
33 <td width="30%" align="left"><b>Default Value</b></td>
39 <a name="Const_Node_Iterator1933878761" id=
40 "Const_Node_Iterator1933878761"><b>class</b> Const_Node_Iterator</a>
45 <p>Const node iterator type.</p>
54 <a name="Node_Iterator4206909839" id=
55 "Node_Iterator4206909839"><b>class</b> Node_Iterator</a>
60 <p>Node iterator type.</p>
69 <a name="E_Access_Traits686553840" id=
70 "E_Access_Traits686553840"><b>class</b> E_Access_Traits</a>
75 <p>Comparison functor.</p>
84 <a name="Allocator35940069" id=
85 "Allocator35940069"><b>class</b> Allocator</a>
90 <p>Allocator type.</p>
97 <h2><a name="link2" id="link2">Public Types and
100 <h3><a name="link3" id="link3">Key-Type Definitions</a></h3>
102 <table class="c1" width="100%" border="1" summary="Types">
104 <td width="30%" align="left"><b>Type</b></td>
106 <td width="55%" align="left"><b>Definition</b></td>
108 <td width="15%" align="left"><b>Description</b></td>
114 <a name="key_type10393186" id="key_type10393186">key_type</a>
120 The instantiating container's key type.
132 <a name="const_key_reference3185471705" id=
133 "const_key_reference3185471705">const_key_reference</a>
139 The instantiating container's const key reference type.
144 <p>Const key reference.</p>
149 <h3><a name="link4" id="link4">Policy Definitions</a></h3>
151 <table class="c1" width="100%" border="1" summary="Types">
153 <td width="30%" align="left"><b>Type</b></td>
155 <td width="55%" align="left"><b>Definition</b></td>
157 <td width="15%" align="left"><b>Description</b></td>
163 <a name="e_access_traits1948190928" id=
164 "e_access_traits1948190928">e_access_traits</a>
170 <a href="#E_Access_Traits686553840"><tt>E_Access_Traits</tt></a>
175 <p>Element access traits.</p>
182 <a name="const_e_iterator2450008044" id=
183 "const_e_iterator2450008044">const_e_iterator</a>
189 <b>typename</b> <a href=
190 "#e_access_traits1948190928"><tt>e_access_traits</tt></a>::const_iterator
195 <p>Const element iterator.</p>
202 <a name="allocator48440069" id="allocator48440069">allocator</a>
208 <a href="#Allocator35940069"><tt>Allocator</tt></a>
213 <p><a href="#Allocator35940069"><tt>Allocator</tt></a>
219 <h3><a name="link5" id="link5">General Definitions</a></h3>
221 <table class="c1" width="100%" border="1" summary="Types">
223 <td width="30%" align="left"><b>Type</b></td>
225 <td width="55%" align="left"><b>Definition</b></td>
227 <td width="15%" align="left"><b>Description</b></td>
233 <a name="size_type55424436" id="size_type55424436">size_type</a>
239 <b>typename</b> <a href=
240 "#allocator48440069"><tt>allocator</tt></a>::size_type
250 <h3><a name="link6" id="link6">Metadata-Type
253 <table class="c1" width="100%" border="1" summary="Types">
255 <td width="30%" align="left"><b>Type</b></td>
257 <td width="55%" align="left"><b>Definition</b></td>
259 <td width="15%" align="left"><b>Description</b></td>
265 <a name="metadata_type2849297114" id=
266 "metadata_type2849297114">metadata_type</a>
272 __gnu_pbds::detail::null_node_metadata
277 <p>Metadata type.</p>
282 <h3><a name="link7" id="link7">Iterator Definitions</a></h3>
284 <table class="c1" width="100%" border="1" summary="Types">
286 <td width="30%" align="left"><b>Type</b></td>
288 <td width="55%" align="left"><b>Definition</b></td>
290 <td width="15%" align="left"><b>Description</b></td>
296 <a name="const_node_iterator4205924553" id=
297 "const_node_iterator4205924553">const_node_iterator</a>
304 "#Const_Node_Iterator1933878761"><tt>Const_Node_Iterator</tt></a>
309 <p>Const node iterator type.</p>
316 <a name="node_iterator3431975247" id=
317 "node_iterator3431975247">node_iterator</a>
323 <a href="#Node_Iterator4206909839"><tt>Node_Iterator</tt></a>
328 <p>Node iterator type.</p>
335 <a name="const_iterator98626788" id=
336 "const_iterator98626788">const_iterator</a>
342 <b>typename</b> <a href=
343 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>::value_type
348 <p>Const iterator type.</p>
355 <a name="iterator10418194" id="iterator10418194">iterator</a>
361 <b>typename</b> <a href=
362 "#node_iterator3431975247"><tt>node_iterator</tt></a>::value_type
367 <p>Iterator type.</p>
372 <h2><a name="link8" id="link8">Public Methods</a></h2>
374 <h3><a name="link9" id="link9">Find Methods</a></h3>
376 <table class="c1" width="100%" border="1" summary="Methods">
378 <td width="45%" align="left"><b>Method</b></td>
380 <td width="55%" align="left"><b>Description</b></td>
387 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>,
389 "#const_iterator98626788"><tt>const_iterator</tt></a>>
392 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key) <b>const</b>
397 <p>Finds the <tt><b>const</b></tt> <a href=
398 "#iterator10418194"><tt>iterator</tt></a> range
399 corresponding to all values whose prefixes match
400 <span class="c1"><tt>r_key</tt></span>.</p>
408 <a href="#iterator10418194"><tt>iterator</tt></a>,
409 <a href="#iterator10418194"><tt>iterator</tt></a>>
412 "#const_key_reference3185471705"><tt>const_key_reference</tt></a> r_key)
417 <p>Finds the <a href=
418 "#iterator10418194"><tt>iterator</tt></a> range
419 corresponding to all values whose prefixes match
420 <span class="c1"><tt>r_key</tt></span>.</p>
428 <a href="#const_iterator98626788"><tt>const_iterator</tt></a>,
430 "#const_iterator98626788"><tt>const_iterator</tt></a>>
433 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> b,
435 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> e) <b>const</b>
440 <p>Finds the <tt><b>const</b></tt> <a href=
441 "#iterator10418194"><tt>iterator</tt></a> range
442 corresponding to all values whose prefixes match [b,
443 <span class="c1"><tt>e</tt></span>).</p>
451 <a href="#iterator10418194"><tt>iterator</tt></a>,
452 <a href="#iterator10418194"><tt>iterator</tt></a>>
455 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> b,
457 "#const_e_iterator2450008044"><tt>const_e_iterator</tt></a> e)
462 <p>Finds the <a href=
463 "#iterator10418194"><tt>iterator</tt></a> range
464 corresponding to all values whose prefixes match [b,
465 <span class="c1"><tt>e</tt></span>).</p>
470 <h2><a name="link10" id="link10">Protected Methods</a></h2>
472 <h3><a name="link11" id="link11">Operators</a></h3>
474 <table class="c1" width="100%" border="1" summary="Methods">
476 <td width="45%" align="left"><b>Method</b></td>
478 <td width="55%" align="left"><b>Description</b></td>
484 <b>inline</b> <b>void</b>
487 "#node_iterator3431975247"><tt>node_iterator</tt></a> node_it,
489 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a> end_nd_it) <b>const</b>
494 <p>Called to update a node's metadata.</p>
499 <h2><a name="link12" id="link12">Private Methods</a></h2>
501 <h3><a name="link13" id="link13">Overrides</a></h3>
503 <table class="c1" width="100%" border="1" summary="Methods">
505 <td width="45%" align="left"><b>Method</b></td>
507 <td width="55%" align="left"><b>Description</b></td>
513 <b>virtual</b> <a href=
514 "#const_iterator98626788"><tt>const_iterator</tt></a>
521 <p>Returns the <tt><b>const</b></tt> <a href=
522 "#iterator10418194"><tt>iterator</tt></a> associated with
523 the just-after last element.</p>
530 <b>virtual</b> <a href="#iterator10418194"><tt>iterator</tt></a>
537 <p>Returns the <a href=
538 "#iterator10418194"><tt>iterator</tt></a> associated with
539 the just-after last element.</p>
546 <b>virtual</b> <a href=
547 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
554 <p>Returns the <a href=
555 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
556 associated with the trie's root node.</p>
563 <b>virtual</b> <a href=
564 "#node_iterator3431975247"><tt>node_iterator</tt></a>
571 <p>Returns the <a href=
572 "#node_iterator3431975247"><tt>node_iterator</tt></a>
573 associated with the trie's root node.</p>
580 <b>virtual</b> <a href=
581 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
588 <p>Returns the <a href=
589 "#const_node_iterator4205924553"><tt>const_node_iterator</tt></a>
590 associated with a just-after leaf node.</p>
597 <b>virtual</b> <a href=
598 "#node_iterator3431975247"><tt>node_iterator</tt></a>
605 <p>Returns the <a href=
606 "#node_iterator3431975247"><tt>node_iterator</tt></a>
607 associated with a just-after leaf node.</p>
614 <b>virtual</b> <b>const</b> <a href=
615 "#e_access_traits1948190928"><tt>e_access_traits</tt></a> &
622 <p>Access to the cmp_fn object.</p>