1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 3 4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 5<head> 6 <meta name="generator" content= 7 "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> 8 9 <title>Concepts</title> 10 <meta http-equiv="Content-Type" content= 11 "text/html; charset=us-ascii" /> 12 </head> 13 14<body> 15 <div id="page"> 16 <h1>Concepts</h1> 17 18 <h2><a name="concepts_find_and_range_iterators" id= 19 "concepts_find_and_range_iterators">Point and Range Methods and 20 Iterators</a></h2> 21 22 <p>A point-type iterator is an iterator that refers to a 23 specific element, <i>e.g.</i> as returned through an 24 associative-container's <tt>find</tt> method; a range-type 25 iterator is an iterator that is used to go over a sequence of 26 elements, <i>e.g.</i>, as returned by a container's 27 <tt>find</tt> method. A point-type method is a method that 28 returns a point-type iterator; a range-type method is a method 29 that returns a range-type iterator.</p> 30 31 <p>For most containers, these types are synonymous; for 32 self-organizing containers, such as hash-based containers or 33 priority queues, these are inherently different (in any 34 implementation, including that of the STL), but in 35 <tt>pb_ds</tt> this is made explicit - they are distinct 36 types.</p> 37 38 39 <h2><a name="invalidation_guarantees" id= 40 "invalidation_guarantees">Invalidation Guarantees</a></h2> 41 42 <p>If one manipulates a container object, then iterators 43 previously obtained from it can be invalidated. In some cases a 44 previously-obtained iterator cannot be de-referenced; in other 45 cases, the iterator's next or previous element might have 46 changed unpredictably. This corresponds exactly to the question 47 whether a point-type or range-type iterator (see previous 48 concept) is valid or not. In <tt>pb_ds</tt> one can query a 49 container (in compile time) what are its invalidation 50 guarantees.</p> 51 52 <h2><a name="prm_sec" id="prm_sec">Primary and Secondary Keys 53 and Associative Containers</a></h2> 54 55 <p>In <tt>pb_ds</tt> there are no associative containers which 56 allow multiple values with equivalent keys (such as the STL's 57 <tt>std::multimap</tt>, for example). Instead, one maps the 58 unique part of a key - the primary key, into an 59 associative-container of the (originally) non-unique parts of 60 the key - the secondary key. A primary associative-container is 61 an associative container of primary keys; a secondary 62 associative-container is an associative container of secondary 63 keys.</p> 64 65 66 <h2><a name="concepts_null_policies" id= 67 "concepts_null_policies">Null Policy Classes</a></h2> 68 69 <p>Associative containers are typically parametrized by 70 various policies. For example, a hash-based associative 71 container is parametrized by a hash-functor, transforming each 72 key into an non-negative numerical type. Each such value is 73 then further mapped into a position within the table. The 74 mapping of a key into a position within the table is therefore 75 a two-step process.</p> 76 77 <p>In some cases, instantiations are <i>redundant</i>. For 78 example, when the keys are integers, it is possible to use a 79 <i>redundant</i> hash policy, which transforms each key into 80 its value.</p> 81 82 <p>In some other cases, these policies are <i>irrelevant</i>. 83 For example, a hash-based associative container might transform 84 keys into positions within a table by a different method than 85 the two-step method described above. In such a case, the hash 86 functor is simply irrelevant.</p> 87 88 <p><tt>pb_ds</tt> uses special pre-defined "null policies" 89 classes for these cases. Some null policies in <tt>pb_ds</tt> 90 are:</p> 91 92 <ol> 93 <li><a href= 94 "null_mapped_type.html"><tt>null_mapped_type</tt></a></li> 95 96 <li><a href= 97 "null_tree_node_update.html"><tt>null_tree_node_update</tt></a></li> 98 99 <li><a href= 100 "null_trie_node_update.html"><tt>null_trie_node_update</tt></a></li> 101 102 <li><a href= 103 "null_hash_fn.html"><tt>null_hash_fn</tt></a></li> 104 105 <li><a href= 106 "null_probe_fn.html"><tt>null_probe_fn</tt></a></li> 107 </ol> 108 109 <p>A "set" in <tt>pb_ds</tt>, for example, is an associative 110 container with its <tt>Data_Parameter</tt> instantiated by 111 <a href="null_mapped_type.html"><tt>null_mapped_type</tt></a>. 112 <a href= 113 "tree_based_containers.html#invariants">Design::Tree-Based 114 Containers::Node Invariants</a> explains another case where a 115 null policy is needed.</p> 116 </div> 117</body> 118</html> 119