![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to map.3 CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / man / adm / man3|
Return to map.3 CVS log | Up to [Research Unix] / researchv10dc / man / adm / man3 |
1.1 root 1: .TH MAP 3+
2: .CT 2 datatype
3: .SH NAME
4: Map \- associative array classes
5: .SH SYNOPSIS
6: .nf
7: .B "#include <Map.h>"
8: .PP
9: .ds 1s \*S
10: .ds S \fIS\fP
11: .ds T \fIT\fP
12: .ft L
13: Mapdeclare(\*S,\*T)
14: Mapimplement(\*S,\*T)
15: .PP
16: .ft L
17: struct Map(\*S,\*T) {
18: Map(\*S,\*T)();
19: Map(\*S,\*T)(const \*T&);
20: Map(\*S,\*T)(const Map(\*S,\*T)&);
21: ~Map(\*S,\*T);
22: Map(\*S,\*T)& operator= (const Map(\*S,\*T)&);
23: \*T& operator[] (int);
24: int size();
25: Mapiter(\*S,\*T) element(const \*S&);
26: Mapiter(\*S,\*T) first();
27: Mapiter(\*S,\*T) last();
28: };
29: .PP
30: .ft L
31: struct Mapiter(\*S,\*T) {
32: Mapiter(\*S,\*T) (const Map(\*S,\*T)&);
33: ~Mapiter(\*S,\*T);
34: operator int();
35: \*S key();
36: \*T value();
37: Mapiter(\*S,\*T)& operator++ (Mapiter(\*S,\*T)&);
38: Mapiter(\*S,\*T)& operator-- (Mapiter(\*S,\*T)&);
39: };
40: .ft R
41: .fi
42: .SH DESCRIPTION
43: A
44: .I map
45: is a collection of
46: .I elements,
47: each of which contains a
48: .I key
49: part of type
50: .I S
51: and a
52: .I value
53: part of type
54: .I T,
55: where
56: .I S
57: and
58: .I T
59: are type names.
60: Both
61: .I S
62: and
63: .I T
64: must have value semantics:
65: assignment or initialization have the effect of copying.
66: (It is unlikely for
67: .I S
68: and
69: .I T
70: to be pointers.)
71: .PP
72: Map elements are ordered by key: type
73: .I S
74: must have a transitive boolean
75: .BR operator< .
76: .PP
77: The macro call
78: .L Mapdeclare(\*S,\*T)
79: declares the classes
80: .B Map(\*S,\*T)
81: and
82: .BR Mapiter(\*S,\*T) .
83: It must appear once in every source file that uses either.
84: The macro call
85: .B Mapimplement(\*S,\*T)
86: defines the functions that implement the map classes.
87: It must appear exactly once in the entire program.
88: .SS Map constructors
89: .nr xx \w'\fLMap(\*S,\*T)(m)\ \fP'
90: .TP \n(xxu
91: .B Map(\*S,\*T)()
92: An empty map.
93: The value part of future elements
94: is the value of an otherwise uninitialized
95: static object of type
96: .I T .
97: .TP
98: .BI Map(\*S,\*T)( x )
99: An empty map whose future elements have
100: default value
101: .I x .
102: .TP
103: .BI Map(\*S,\*T)( m )
104: A copy of map
105: .I m
106: obtained by copying the elements and default value of
107: .I m.
108: .SS Map operators
109: .TP \n(xxu
110: .IB n " = " m
111: All the elements of map
112: .I n
113: are deleted and and
114: copies of the elements of
115: .I m
116: are added.
117: The default value of
118: .I n
119: does not change.
120: Running time is
121: .IR O (log(| m |)
122: +
123: .RI log(| n |)),
124: where
125: .RI | m |
126: means
127: .IB m .size() .
128: .TP
129: .IB m [ k ]
130: A reference
131: to the value part of the element of map
132: .I m
133: with key
134: .BR k .
135: If the element does not exist, it is created.
136: Running time is
137: .IR O (log(| m |)) .
138: .SS Other Map functions
139: .TP \n(xxu
140: .IB m .size()
141: The number of elements in
142: .LR m .
143: Running time is
144: .IR O (1).
145: .TP
146: .IB m .element( k )
147: A map iterator
148: referring to the element of
149: .I m
150: with key
151: .I k
152: if such an element exists.
153: Otherwise the result is vacuous.
154: Running time is
155: .IR O (log(| m |)) .
156: .TP
157: .IB m .first()
158: .br
159: .ns
160: .TP
161: .IB m .last()
162: A map iterator
163: referring to the element of
164: .I m
165: with the smallest (or largest) key.
166: If
167: .L m
168: has no elements, the result is vacuous.
169: Running time is
170: .IR O (log(| m |)) .
171: .SS "Map iterators"
172: For every class
173: .B Map(\*S,\*T)
174: there is a class
175: .BR Mapiter(\*S,\*T) .
176: A map iterator identifies a map object and possibly
177: an element in that map.
178: An iterator that does not identify an element is
179: .IR vacuous .
180: .SS Mapiter constructors
181: .TP \n(xxu
182: .BI Mapiter(\*S,\*T)( m )
183: A vacuous iterator referring to map
184: .I m.
185: Running time is
186: .IR O (1).
187: .SS Mapiter operators
188: .TP \n(xxu
189: .IB i " = " j
190: Make iterator
191: .I i
192: refer (for now) to the same map as does
193: .I j.
194: .TP
195: .BI (int) i
196: Zero if iterator
197: .I i
198: is vacuous, otherwise nonzero.
199: .TP
200: .BI ++ i
201: .br
202: .ns
203: .TP
204: .BI -- i
205: If iterator
206: .I i
207: is vacuous, make it refer to the map element with
208: the smallest (or largest) key
209: Otherwise, make it refer to the map element with the
210: next key greater (or less) than the key of the
211: current element.
212: If no such element exists,
213: .I i
214: becomes vacuous.
215: The running time of a single increment
216: operation for map
217: .I m
218: is
219: .IR O (log(| m |)).
220: However an iterator
221: takes only time
222: .IR O (| m |)
223: to sequence through the whole map.
224: .SS Other mapiter functions
225: .TP \n(xxu
226: .IB i .key()
227: .br
228: .ns
229: .TP
230: .IB i .value()
231: The key (or value) part of the element referred to by
232: .I i .
233: If
234: .I i
235: is vacuous, return
236: the value of an otherwise uninitialized static
237: object of appropriate type.
238: Running time is
239: .IR O (1).
240: .SH EXAMPLES
241: .EX
242: struct city { char name[100]; };
243: typedef int population;
244: int operator< (const city&, const city&);
245: .EE
246: .PP
247: .B Mapdeclare(name,population)
248: .PP
249: .B Map(name,population) gazetteer;
250: .PP
251: .B "// Print big cities; set populations of others to zero.
252: .PP
253: .EX
254: for(Mapiter(name,population) i = gazetteer.first(); i; i++)
255: if(i.value() > 1000000)
256: printf("%s\en", i.key().name);
257: else
258: gazetteer[i.key()] = 0;
259: .EE
260: .SH BUGS
261: A `type name'
262: .B Map(\*S,\*T)
263: or
264: .BR Mapiter(\*S,\*T)
265: that contains spaces will be mangled by
266: .IR cpp (8).
267: .br
268: There is no way to delete a single element.
269: .br
270: Ambiguities can occur if the type name
271: .I S
272: contains an underscore.
273: .br
274: No precautions are taken against running out of memory.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.