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">
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=utf-8" />
6 <meta name=
"generator" content=
"Docutils 0.7: http://docutils.sourceforge.net/" />
7 <title>The MPL Reference Manual: Associative Sequence
</title>
8 <link rel=
"stylesheet" href=
"../style.css" type=
"text/css" />
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-sequence.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-sequence.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#id1401">Associative Sequence
</a></h1>
16 <div class=
"section" id=
"id29">
17 <h3><a class=
"subsection-title" href=
"#description" name=
"description">Description
</a></h3>
18 <p>An
<a class=
"reference internal" href=
"./associative-sequence.html">Associative Sequence
</a> is a
<a class=
"reference internal" 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
25 <div class=
"section" id=
"id30">
26 <h3><a class=
"subsection-title" href=
"#definitions" name=
"definitions">Definitions
</a></h3>
27 <ul class=
"simple" id=
"value-part">
28 <span id=
"key-part"></span><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
34 <div class=
"section" id=
"id31">
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 internal" 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 internal" href=
"./forward-sequence.html">Forward Sequence
</a>,
39 the following must be met:
</p>
40 <table border=
"1" class=
"docutils table">
46 <thead valign=
"bottom">
47 <tr><th class=
"head">Expression
</th>
48 <th class=
"head">Type
</th>
49 <th class=
"head">Complexity
</th>
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 internal" href=
"./integral-constant.html">Integral Constant
</a></td>
55 <td>Amortized constant time
</td>
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 internal" href=
"./integral-constant.html">Integral Constant
</a></td>
59 <td>Amortized constant time
</td>
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 internal" 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>
65 <tr><td><tt class=
"literal"><span class=
"pre"><a href=
"./at.html" class=
"identifier">at
</a><s,k
>::type
</span></tt></td>
67 <td>Amortized constant time
</td>
69 <tr><td><tt class=
"literal"><span class=
"pre"><a href=
"./at.html" class=
"identifier">at
</a><s,k,def
>::type
</span></tt></td>
71 <td>Amortized constant time
</td>
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>
75 <td>Amortized constant time
</td>
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>
79 <td>Amortized constant time
</td>
84 <div class=
"section" id=
"id32">
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 internal" href=
"./forward-sequence.html">Forward Sequence
</a>.
</p>
88 <table border=
"1" class=
"docutils table">
93 <thead valign=
"bottom">
94 <tr><th class=
"head">Expression
</th>
95 <th class=
"head">Semantics
</th>
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 internal" 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=
"reference internal" href=
"./has-key.html">has_key
</a>.
</td>
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=
"reference internal" href=
"./count.html">count
</a>.
</td>
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 internal" 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=
"reference internal" href=
"./order.html">order
</a>.
</td>
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
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=
"reference internal" href=
"./at.html">at
</a>.
</td>
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=
"reference internal" href=
"./key-type.html">key_type
</a>.
</td>
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=
"reference internal" href=
"./value-type.html">value_type
</a>.
</td>
133 For any associative sequence ``s`` the following invariants always hold:
137 <div class=
"section" id=
"id33">
138 <h3><a class=
"subsection-title" href=
"#models" name=
"models">Models
</a></h3>
140 <li><a class=
"reference internal" href=
"./set.html">set
</a></li>
141 <li><a class=
"reference internal" href=
"./map.html">map
</a></li>
143 <!-- * |multiset| -->
145 <div class=
"section" id=
"id34">
146 <h3><a class=
"subsection-title" href=
"#see-also" name=
"see-also">See also
</a></h3>
147 <p><a class=
"reference internal" href=
"./sequences.html">Sequences
</a>,
<a class=
"reference internal" href=
"./extensible-associative-sequence.html">Extensible Associative Sequence
</a>,
<a class=
"reference internal" href=
"./has-key.html">has_key
</a>,
<a class=
"reference internal" href=
"./count.html">count
</a>,
<a class=
"reference internal" href=
"./order.html">order
</a>,
<a class=
"reference internal" href=
"./at.html">at
</a>,
<a class=
"reference internal" href=
"./key-type.html">key_type
</a>,
<a class=
"reference internal" href=
"./value-type.html">value_type
</a></p>
148 <!-- Sequences/Concepts//Extensible Associative Sequence |80 -->
152 <div class=
"footer-separator"></div>
153 <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-sequence.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-sequence.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>
154 <td><div class=
"copyright-footer"><div class=
"copyright">Copyright ©
2001-
2009 Aleksey Gurtovoy and David Abrahams
</div>
155 Distributed under the Boost Software License, Version
1.0. (See accompanying
156 file LICENSE_1_0.txt or copy at
<a class=
"reference external" href=
"http://www.boost.org/LICENSE_1_0.txt" target=
"_top">http://www.boost.org/LICENSE_1_0.txt
</a>)
</div></td></tr></table></body>