1 | <?xml version="1.0" encoding="utf-8" ?> |
---|
2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
---|
3 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> |
---|
4 | <head> |
---|
5 | <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> |
---|
6 | <meta name="generator" content="Docutils 0.3.6: http://docutils.sourceforge.net/" /> |
---|
7 | <title>The MPL Reference Manual: Associative Sequence</title> |
---|
8 | <link rel="stylesheet" href="../style.css" type="text/css" /> |
---|
9 | </head> |
---|
10 | <body class="docframe refmanual"> |
---|
11 | <table class="header"><tr class="header"><td class="header-group navigation-bar"><span class="navigation-group"><a href="./back-extensible-sequence.html" class="navigation-link">Prev</a> <a href="./extensible-associative.html" class="navigation-link">Next</a></span><span class="navigation-group-separator"> | </span><span class="navigation-group"><a href="./back-extensible-sequence.html" class="navigation-link">Back</a> <a href="./extensible-associative.html" class="navigation-link">Along</a></span><span class="navigation-group-separator"> | </span><span class="navigation-group"><a href="./concepts.html" class="navigation-link">Up</a> <a href="../refmanual.html" class="navigation-link">Home</a></span><span class="navigation-group-separator"> | </span><span class="navigation-group"><a href="./refmanual_toc.html" class="navigation-link">Full TOC</a></span></td> |
---|
12 | <td class="header-group page-location"><a href="../refmanual.html" class="navigation-link">Front Page</a> / <a href="./sequences.html" class="navigation-link">Sequences</a> / <a href="./concepts.html" class="navigation-link">Concepts</a> / <a href="./associative-sequence.html" class="navigation-link">Associative Sequence</a></td> |
---|
13 | </tr></table><div class="header-separator"></div> |
---|
14 | <div class="section" id="associative-sequence"> |
---|
15 | <h1><a class="toc-backref" href="./concepts.html#id330" name="associative-sequence">Associative Sequence</a></h1> |
---|
16 | <div class="section" id="associative-description"> |
---|
17 | <h3><a class="subsection-title" href="#description" name="description">Description</a></h3> |
---|
18 | <p>An <a class="reference" href="./associative-sequence.html">Associative Sequence</a> is a <a class="reference" href="./forward-sequence.html">Forward Sequence</a> that allows efficient retrieval of |
---|
19 | elements based on keys. Unlike associative containers in the C++ Standard Library, |
---|
20 | MPL associative sequences have no associated ordering relation. Instead, |
---|
21 | <em>type identity</em> is used to impose an equivalence relation on keys, and the |
---|
22 | order in which sequence elements are traversed during iteration is left |
---|
23 | unspecified.</p> |
---|
24 | </div> |
---|
25 | <div class="section" id="associative-definitions"> |
---|
26 | <h3><a class="subsection-title" href="#definitions" name="definitions">Definitions</a></h3> |
---|
27 | <a class="target" id="key-part" name="key-part"></a><a class="target" id="value-part" name="value-part"></a><ul class="simple"> |
---|
28 | <li>A <em>key</em> is a part of the element type used to identify and retrieve |
---|
29 | the element within the sequence.</li> |
---|
30 | <li>A <em>value</em> is a part of the element type retrievied from the sequence |
---|
31 | by its key.</li> |
---|
32 | </ul> |
---|
33 | </div> |
---|
34 | <div class="section" id="associative-expression-requirements"> |
---|
35 | <h3><a class="subsection-title" href="#expression-requirements" name="expression-requirements">Expression requirements</a></h3> |
---|
36 | <p>In the following table and subsequent specifications, <tt class="literal"><span class="pre">s</span></tt> is an <a class="reference" href="./associative-sequence.html">Associative Sequence</a>, |
---|
37 | <tt class="literal"><span class="pre">x</span></tt> is a sequence element, and <tt class="literal"><span class="pre">k</span></tt> and <tt class="literal"><span class="pre">def</span></tt> are arbitrary types.</p> |
---|
38 | <p>In addition to the requirements defined in <a class="reference" href="./forward-sequence.html">Forward Sequence</a>, |
---|
39 | the following must be met:</p> |
---|
40 | <table border="1" class="table"> |
---|
41 | <colgroup> |
---|
42 | <col width="33%" /> |
---|
43 | <col width="38%" /> |
---|
44 | <col width="29%" /> |
---|
45 | </colgroup> |
---|
46 | <thead valign="bottom"> |
---|
47 | <tr><th>Expression</th> |
---|
48 | <th>Type</th> |
---|
49 | <th>Complexity</th> |
---|
50 | </tr> |
---|
51 | </thead> |
---|
52 | <tbody valign="top"> |
---|
53 | <tr><td><tt class="literal"><span class="pre"><a href="./has-key.html" class="identifier">has_key</a><s,k>::type</span></tt></td> |
---|
54 | <td>Boolean <a class="reference" href="./integral-constant.html">Integral Constant</a></td> |
---|
55 | <td>Amortized constant time</td> |
---|
56 | </tr> |
---|
57 | <tr><td><tt class="literal"><span class="pre"><a href="./count.html" class="identifier">count</a><s,k>::type</span></tt></td> |
---|
58 | <td><a class="reference" href="./integral-constant.html">Integral Constant</a></td> |
---|
59 | <td>Amortized constant time</td> |
---|
60 | </tr> |
---|
61 | <tr><td><tt class="literal"><span class="pre"><a href="./order.html" class="identifier">order</a><s,k>::type</span></tt></td> |
---|
62 | <td><a class="reference" href="./integral-constant.html">Integral Constant</a> or <tt class="literal"><span class="pre"><a href="./void.html" class="identifier">void_</a></span></tt></td> |
---|
63 | <td>Amortized constant time</td> |
---|
64 | </tr> |
---|
65 | <tr><td><tt class="literal"><span class="pre"><a href="./at.html" class="identifier">at</a><s,k>::type</span></tt></td> |
---|
66 | <td>Any type</td> |
---|
67 | <td>Amortized constant time</td> |
---|
68 | </tr> |
---|
69 | <tr><td><tt class="literal"><span class="pre"><a href="./at.html" class="identifier">at</a><s,k,def>::type</span></tt></td> |
---|
70 | <td>Any type</td> |
---|
71 | <td>Amortized constant time</td> |
---|
72 | </tr> |
---|
73 | <tr><td><tt class="literal"><span class="pre"><a href="./key-type.html" class="identifier">key_type</a><s,x>::type</span></tt></td> |
---|
74 | <td>Any type</td> |
---|
75 | <td>Amortized constant time</td> |
---|
76 | </tr> |
---|
77 | <tr><td><tt class="literal"><span class="pre"><a href="./value-type.html" class="identifier">value_type</a><s,x>::type</span></tt></td> |
---|
78 | <td>Any type</td> |
---|
79 | <td>Amortized constant time</td> |
---|
80 | </tr> |
---|
81 | </tbody> |
---|
82 | </table> |
---|
83 | </div> |
---|
84 | <div class="section" id="associative-expression-semantics"> |
---|
85 | <h3><a class="subsection-title" href="#expression-semantics" name="expression-semantics">Expression semantics</a></h3> |
---|
86 | <p>The semantics of an expression are defined only |
---|
87 | where they differ from, or are not defined in <a class="reference" href="./forward-sequence.html">Forward Sequence</a>.</p> |
---|
88 | <table border="1" class="table"> |
---|
89 | <colgroup> |
---|
90 | <col width="33%" /> |
---|
91 | <col width="67%" /> |
---|
92 | </colgroup> |
---|
93 | <thead valign="bottom"> |
---|
94 | <tr><th>Expression</th> |
---|
95 | <th>Semantics</th> |
---|
96 | </tr> |
---|
97 | </thead> |
---|
98 | <tbody valign="top"> |
---|
99 | <tr><td><tt class="literal"><span class="pre"><a href="./has-key.html" class="identifier">has_key</a><s,k>::type</span></tt></td> |
---|
100 | <td>A boolean <a class="reference" href="./integral-constant.html">Integral Constant</a> <tt class="literal"><span class="pre">c</span></tt> such that |
---|
101 | <tt class="literal"><span class="pre">c::value</span> <span class="pre">==</span> <span class="pre">true</span></tt> if and only if there is one or more |
---|
102 | elements with the key <tt class="literal"><span class="pre">k</span></tt> in <tt class="literal"><span class="pre">s</span></tt>; see <a class="refentry reference" href="./has-key.html"><tt class="refentry literal"><span class="pre">has_key</span></tt></a>.</td> |
---|
103 | </tr> |
---|
104 | <tr><td><tt class="literal"><span class="pre"><a href="./count.html" class="identifier">count</a><s,k>::type</span></tt></td> |
---|
105 | <td>The number of elements with the key <tt class="literal"><span class="pre">k</span></tt> in <tt class="literal"><span class="pre">s</span></tt>; |
---|
106 | see <a class="refentry reference" href="./count.html"><tt class="refentry literal"><span class="pre">count</span></tt></a>.</td> |
---|
107 | </tr> |
---|
108 | <tr><td><tt class="literal"><span class="pre"><a href="./order.html" class="identifier">order</a><s,k>::type</span></tt></td> |
---|
109 | <td>A unique unsigned <a class="reference" href="./integral-constant.html">Integral Constant</a> associated |
---|
110 | with the key <tt class="literal"><span class="pre">k</span></tt> in the sequence <tt class="literal"><span class="pre">s</span></tt>; see <a class="refentry reference" href="./order.html"><tt class="refentry literal"><span class="pre">order</span></tt></a>.</td> |
---|
111 | </tr> |
---|
112 | <tr><td><pre class="first last literal-block"> |
---|
113 | <a href="./at.html" class="identifier">at</a><s,k>::type |
---|
114 | <a href="./at.html" class="identifier">at</a><s,k,def>::type |
---|
115 | </pre> |
---|
116 | </td> |
---|
117 | <td>The first element associated with the key <tt class="literal"><span class="pre">k</span></tt> |
---|
118 | in the sequence <tt class="literal"><span class="pre">s</span></tt>; see <a class="refentry reference" href="./at.html"><tt class="refentry literal"><span class="pre">at</span></tt></a>.</td> |
---|
119 | </tr> |
---|
120 | <tr><td><tt class="literal"><span class="pre"><a href="./key-type.html" class="identifier">key_type</a><s,x>::type</span></tt></td> |
---|
121 | <td>The key part of the element <tt class="literal"><span class="pre">x</span></tt> that would be |
---|
122 | used to identify <tt class="literal"><span class="pre">x</span></tt> in <tt class="literal"><span class="pre">s</span></tt>; see <a class="refentry reference" href="./key-type.html"><tt class="refentry literal"><span class="pre">key_type</span></tt></a>.</td> |
---|
123 | </tr> |
---|
124 | <tr><td><tt class="literal"><span class="pre"><a href="./value-type.html" class="identifier">value_type</a><s,x>::type</span></tt></td> |
---|
125 | <td>The value part of the element <tt class="literal"><span class="pre">x</span></tt> that would be |
---|
126 | used for <tt class="literal"><span class="pre">x</span></tt> in <tt class="literal"><span class="pre">s</span></tt>; see <a class="refentry reference" href="./value-type.html"><tt class="refentry literal"><span class="pre">value_type</span></tt></a>.</td> |
---|
127 | </tr> |
---|
128 | </tbody> |
---|
129 | </table> |
---|
130 | <!-- Invariants |
---|
131 | - - - - - - - - - - |
---|
132 | |
---|
133 | For any associative sequence ``s`` the following invariants always hold: |
---|
134 | |
---|
135 | * ??? --> |
---|
136 | </div> |
---|
137 | <div class="section" id="associative-models"> |
---|
138 | <h3><a class="subsection-title" href="#models" name="models">Models</a></h3> |
---|
139 | <ul class="simple"> |
---|
140 | <li><a class="refentry reference" href="./set.html"><tt class="refentry literal"><span class="pre">set</span></tt></a></li> |
---|
141 | <li><a class="refentry reference" href="./map.html"><tt class="refentry literal"><span class="pre">map</span></tt></a></li> |
---|
142 | </ul> |
---|
143 | <!-- * |multiset| --> |
---|
144 | </div> |
---|
145 | <div class="section" id="associative-see-also"> |
---|
146 | <h3><a class="subsection-title" href="#see-also" name="see-also">See also</a></h3> |
---|
147 | <p><a class="reference" href="./sequences.html">Sequences</a>, <a class="reference" href="./extensible-associative.html">Extensible Associative Sequence</a>, <a class="refentry reference" href="./has-key.html"><tt class="refentry literal"><span class="pre">has_key</span></tt></a>, <a class="refentry reference" href="./count.html"><tt class="refentry literal"><span class="pre">count</span></tt></a>, <a class="refentry reference" href="./order.html"><tt class="refentry literal"><span class="pre">order</span></tt></a>, <a class="refentry reference" href="./at.html"><tt class="refentry literal"><span class="pre">at</span></tt></a>, <a class="refentry reference" href="./key-type.html"><tt class="refentry literal"><span class="pre">key_type</span></tt></a>, <a class="refentry reference" href="./value-type.html"><tt class="refentry literal"><span class="pre">value_type</span></tt></a></p> |
---|
148 | <!-- modtime: November 13, 2004 00:51:14 +0000 --> |
---|
149 | <!-- Sequences/Concepts//Extensible Associative Sequence |80 --> |
---|
150 | </div> |
---|
151 | </div> |
---|
152 | |
---|
153 | <div class="footer-separator"></div> |
---|
154 | <table class="footer"><tr class="footer"><td class="header-group navigation-bar"><span class="navigation-group"><a href="./back-extensible-sequence.html" class="navigation-link">Prev</a> <a href="./extensible-associative.html" class="navigation-link">Next</a></span><span class="navigation-group-separator"> | </span><span class="navigation-group"><a href="./back-extensible-sequence.html" class="navigation-link">Back</a> <a href="./extensible-associative.html" class="navigation-link">Along</a></span><span class="navigation-group-separator"> | </span><span class="navigation-group"><a href="./concepts.html" class="navigation-link">Up</a> <a href="../refmanual.html" class="navigation-link">Home</a></span><span class="navigation-group-separator"> | </span><span class="navigation-group"><a href="./refmanual_toc.html" class="navigation-link">Full TOC</a></span></td> |
---|
155 | </tr></table></body> |
---|
156 | </html> |
---|