Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/utility/Collection.html @ 12

Last change on this file since 12 was 12, checked in by landauf, 17 years ago

added boost
File size: 12.8 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) Jeremy Siek 2000
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  Silicon Graphics makes no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<Head>
14<Title>Collection</Title>
15</HEAD>
16
17<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
18        ALINK="#ff0000"> 
19<h1>
20   <img src="../../boost.png" alt="boost logo"
21    width="277" align="middle" height="86">
22   <br>Collection
23</h1>
24
25<h3>Description</h3>
26
27A Collection is a <i>concept</i> similar to the STL <a
28href="http://www.sgi.com/tech/stl/Container.html">Container</a>
29concept.  A Collection provides iterators for accessing a range of
30elements and provides information about the number of elements in the
31Collection.  However, a Collection has fewer requirements than a
32Container. The motivation for the Collection concept is that there are
33many useful Container-like types that do not meet the full
34requirements of Container, and many algorithms that can be written
35with this reduced set of requirements. To summarize the reduction
36in requirements:
37
38<UL>
39<LI>It is not required to &quot;own&quot; its elements: the lifetime
40of an element in a Collection does not have to match the lifetime of
41the Collection object, though the lifetime of the element should cover
42the lifetime of the Collection object.
43<LI>The semantics of copying a Collection object is not defined (it
44could be a deep or shallow copy or not even support copying).
45<LI>The associated reference type of a Collection does
46not have to be a real C++ reference.
47</UL>
48
49
50Because of the reduced requirements, some care must be taken when
51writing code that is meant to be generic for all Collection types.
52In particular, a Collection object should be passed by-reference
53since assumptions can not be made about the behaviour of the
54copy constructor.
55
56<p>
57
58<h3>Associated types</h3>
59
60<Table border>
61<TR>
62<TD VAlign=top>
63Value type
64</TD>
65<TD VAlign=top>
66<tt>X::value_type</tt>
67</TD>
68<TD VAlign=top>
69The type of the object stored in a Collection. 
70If the Collection is <i>mutable</i> then
71the value type must be <A
72href="http://www.sgi.com/tech/stl/Assignable.html">Assignable</A>.
73Otherwise the value type must be <a href="./CopyConstructible.html">CopyConstructible</a>.
74</TD>
75</TR>
76<TR>
77<TD VAlign=top>
78Iterator type
79</TD>
80<TD VAlign=top>
81<tt>X::iterator</tt>
82</TD>
83<TD VAlign=top>
84The type of iterator used to iterate through a Collection's
85   elements.  The iterator's value type is expected to be the
86   Collection's value type.  A conversion
87   from the iterator type to the const iterator type must exist.
88   The iterator type must be an <A href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</A>.
89</TD>
90</TR>
91<TR>
92<TD VAlign=top>
93Const iterator type
94</TD>
95<TD VAlign=top>
96<tt>X::const_iterator</tt>
97</TD>
98<TD VAlign=top>
99A type of iterator that may be used to examine, but not to modify,
100   a Collection's elements.
101</TD>
102</TR>
103<TR>
104<TD VAlign=top>
105Reference type
106</TD>
107<TD VAlign=top>
108<tt>X::reference</tt>
109</TD>
110<TD VAlign=top>
111A type that behaves like a reference to the Collection's value type.
112<a href="#1">[1]</a>
113</TD>
114</TR>
115<TR>
116<TD VAlign=top>
117Const reference type
118</TD>
119<TD VAlign=top>
120<tt>X::const_reference</tt>
121</TD>
122<TD VAlign=top>
123A type that behaves like a const reference to the Collection's value type.
124</TD>
125</TR>
126<TR>
127<TD VAlign=top>
128Pointer type
129</TD>
130<TD VAlign=top>
131<tt>X::pointer</tt>
132</TD>
133<TD VAlign=top>
134A type that behaves as a pointer to the Collection's value type.
135</TD>
136</TR>
137<TR>
138<TD VAlign=top>
139Distance type
140</TD>
141<TD VAlign=top>
142<tt>X::difference_type</tt>
143</TD>
144<TD VAlign=top>
145A signed integral type used to represent the distance between two
146   of the Collection's iterators.  This type must be the same as
147   the iterator's distance type.
148</TD>
149</TR>
150<TR>
151<TD VAlign=top>
152Size type
153</TD>
154<TD VAlign=top>
155<tt>X::size_type</tt>
156</TD>
157<TD VAlign=top>
158An unsigned integral type that can represent any nonnegative value
159   of the Collection's distance type.
160</TD>
161</tr>
162</table>
163<h3>Notation</h3>
164<Table>
165<TR>
166<TD VAlign=top>
167<tt>X</tt>
168</TD>
169<TD VAlign=top>
170A type that is a model of Collection.
171</TD>
172</TR>
173<TR>
174<TD VAlign=top>
175<tt>a</tt>, <tt>b</tt>
176</TD>
177<TD VAlign=top>
178Object of type <tt>X</tt>.
179</TD>
180</TR>
181<TR>
182<TD VAlign=top>
183<tt>T</tt>
184</TD>
185<TD VAlign=top>
186The value type of <tt>X</tt>.
187</TD>
188</tr>
189</table>
190
191<h3>Valid expressions</h3>
192
193The following expressions must be valid.
194<p>
195
196<Table border>
197<TR>
198<TH>
199Name
200</TH>
201<TH>
202Expression
203</TH>
204<TH>
205Return type
206</TH>
207</TR>
208<TR>
209<TD VAlign=top>
210Beginning of range
211</TD>
212<TD VAlign=top>
213<tt>a.begin()</tt>
214</TD>
215<TD VAlign=top>
216<tt>iterator</tt> if <tt>a</tt> is mutable, <tt>const_iterator</tt> otherwise
217</TD>
218</TR>
219<TR>
220<TD VAlign=top>
221End of range
222</TD>
223<TD VAlign=top>
224<tt>a.end()</tt>
225</TD>
226<TD VAlign=top>
227<tt>iterator</tt> if <tt>a</tt> is mutable, <tt>const_iterator</tt> otherwise
228</TD>
229</TR>
230<TR>
231<TD VAlign=top>
232Size
233</TD>
234<TD VAlign=top>
235<tt>a.size()</tt>
236</TD>
237<TD VAlign=top>
238<tt>size_type</tt>
239</TD>
240</TR>
241<!--
242<TR>
243<TD VAlign=top>
244Maximum size
245</TD>
246<TD VAlign=top>
247<tt>a.max_size()</tt>
248</TD>
249<TD VAlign=top>
250<tt>size_type</tt>
251</TD>
252</TR>
253<TR>
254-->
255<TD VAlign=top>
256Empty Collection
257</TD>
258<TD VAlign=top>
259<tt>a.empty()</tt>
260</TD>
261<TD VAlign=top>
262Convertible to <tt>bool</tt>
263</TD>
264</TR>
265<TR>
266<TD VAlign=top>
267Swap
268</TD>
269<TD VAlign=top>
270<tt>a.swap(b)</tt>
271</TD>
272<TD VAlign=top>
273<tt>void</tt>
274</TD>
275</tr>
276</table>
277<h3>Expression semantics</h3>
278
279<Table border>
280<TR>
281<TH>
282Name
283</TH>
284<TH>
285Expression
286</TH>
287<TH>
288Semantics
289</TH>
290<TH>
291Postcondition
292</TH>
293</TR>
294<TD VAlign=top>
295<TR>
296<TD VAlign=top>
297Beginning of range
298</TD>
299<TD VAlign=top>
300<tt>a.begin()</tt>
301</TD>
302<TD VAlign=top>
303Returns an iterator pointing to the first element in the Collection.
304</TD>
305<TD VAlign=top>
306<tt>a.begin()</tt> is either dereferenceable or past-the-end.  It is
307   past-the-end if and only if <tt>a.size() == 0</tt>.
308</TD>
309</TR>
310<TR>
311<TD VAlign=top>
312End of range
313</TD>
314<TD VAlign=top>
315<tt>a.end()</tt>
316</TD>
317<TD VAlign=top>
318Returns an iterator pointing one past the last element in the
319   Collection.
320</TD>
321<TD VAlign=top>
322<tt>a.end()</tt> is past-the-end.
323</TD>
324</TR>
325<TR>
326<TD VAlign=top>
327Size
328</TD>
329<TD VAlign=top>
330<tt>a.size()</tt>
331</TD>
332<TD VAlign=top>
333Returns the size of the Collection, that is, its number of elements.
334</TD>
335<TD VAlign=top>
336<tt>a.size() &gt;= 0
337</TD>
338</TR>
339<!--
340<TR>
341<TD VAlign=top>
342Maximum size
343</TD>
344<TD VAlign=top>
345<tt>a.max_size()</tt>
346</TD>
347<TD VAlign=top>
348&nbsp;
349</TD>
350<TD VAlign=top>
351Returns the largest size that this Collection can ever have. <A href="#8">[8]</A>
352</TD>
353<TD VAlign=top>
354<tt>a.max_size() &gt;= 0 &amp;&amp; a.max_size() &gt;= a.size()</tt>
355</TD>
356</TR>
357 -->
358<TR>
359<TD VAlign=top>
360Empty Collection
361</TD>
362<TD VAlign=top>
363<tt>a.empty()</tt>
364</TD>
365<TD VAlign=top>
366Equivalent to <tt>a.size() == 0</tt>.  (But possibly faster.)
367</TD>
368<TD VAlign=top>
369&nbsp;
370</TD>
371</TR>
372<TR>
373<TD VAlign=top>
374Swap
375</TD>
376<TD VAlign=top>
377<tt>a.swap(b)</tt>
378</TD>
379<TD VAlign=top>
380Equivalent to <tt>swap(a,b)</tt>
381</TD>
382<TD VAlign=top>
383&nbsp;
384</TD>
385</tr>
386</table>
387<h3>Complexity guarantees</h3>
388
389<tt>begin()</tt> and <tt>end()</tt> are amortized constant time.
390<P>
391<tt>size()</tt> is at most linear in the Collection's
392size. <tt>empty()</tt> is amortized constant time.
393<P>
394<tt>swap()</tt> is at most linear in the size of the two collections.
395<h3>Invariants</h3>
396<Table border>
397<TR>
398<TD VAlign=top>
399Valid range
400</TD>
401<TD VAlign=top>
402For any Collection <tt>a</tt>, <tt>[a.begin(), a.end())</tt> is a valid
403   range.
404</TD>
405</TR>
406<TR>
407<TD VAlign=top>
408Range size
409</TD>
410<TD VAlign=top>
411<tt>a.size()</tt> is equal to the distance from <tt>a.begin()</tt> to <tt>a.end()</tt>.
412</TD>
413</TR>
414<TR>
415<TD VAlign=top>
416Completeness
417</TD>
418<TD VAlign=top>
419An algorithm that iterates through the range <tt>[a.begin(), a.end())</tt>
420   will pass through every element of <tt>a</tt>.
421</TD>
422</tr>
423</table>
424
425
426<h3>Models</h3>
427<UL>
428<LI> <tt>array</tt>
429<LI> <tt>array_ptr</tt>
430<LI> <tt>vector&lt;bool&gt;</tt>
431</UL>
432
433
434<h3>Collection Refinements</h3>
435
436There are quite a few concepts that refine the Collection concept,
437similar to the concepts that refine the Container concept. Here
438is a brief overview of the refining concepts.
439
440<h4>ForwardCollection</h4>
441The elements are arranged in some order that
442does not change spontaneously from one iteration to the next. As
443a result, a ForwardCollection is
444<A
445href="http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</A>
446and
447<A
448href="http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</A>.
449In addition, the iterator type of a ForwardCollection is a
450MultiPassInputIterator which is just an InputIterator with the added
451requirements that the iterator can be used to make multiple passes
452through a range, and that if <tt>it1 == it2</tt> and <tt>it1</tt> is
453dereferenceable then <tt>++it1 == ++it2</tt>. The ForwardCollection
454also has a <tt>front()</tt> method.
455
456<p>
457<Table border>
458<TR>
459<TH>
460Name
461</TH>
462<TH>
463Expression
464</TH>
465<TH>
466Return type
467</TH>
468<TH>
469Semantics
470</TH>
471</TR>
472
473<TR>
474<TD VAlign=top>
475Front
476</TD>
477<TD VAlign=top>
478<tt>a.front()</tt>
479</TD>
480<TD VAlign=top>
481<tt>reference</tt> if <tt>a</tt> is mutable, <br> <tt>const_reference</tt>
482otherwise.
483</TD>
484<TD VAlign=top>
485Equivalent to <tt>*(a.begin())</tt>.
486</TD>
487</TR>
488
489</table>
490
491
492<h4>ReversibleCollection</h4>
493
494The container provides access to iterators that traverse in both
495directions (forward and reverse). The iterator type must meet all of
496the requirements of
497<a href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>
498except that the reference type does not have to be a real C++
499reference. The ReversibleCollection adds the following requirements
500to those of ForwardCollection.
501<p>
502
503<Table border>
504<TR>
505<TH>
506Name
507</TH>
508<TH>
509Expression
510</TH>
511<TH>
512Return type
513</TH>
514<TH>
515Semantics
516</TH>
517</TR>
518<TR>
519<TD VAlign=top>
520Beginning of range
521</TD>
522<TD VAlign=top>
523<tt>a.rbegin()</tt>
524</TD>
525<TD VAlign=top>
526<tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
527<tt>const_reverse_iterator</tt> otherwise.
528</TD>
529<TD VAlign=top>
530Equivalent to <tt>X::reverse_iterator(a.end())</tt>.
531</TD>
532</TR>
533<TR>
534<TD VAlign=top>
535End of range
536</TD>
537<TD VAlign=top>
538<tt>a.rend()</tt>
539</TD>
540<TD VAlign=top>
541<tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
542<tt>const_reverse_iterator</tt> otherwise.
543</TD>
544<TD VAlign=top>
545Equivalent to <tt>X::reverse_iterator(a.begin())</tt>.
546</TD>
547</tr>
548
549<TR>
550<TD VAlign=top>
551Back
552</TD>
553<TD VAlign=top>
554<tt>a.back()</tt>
555</TD>
556<TD VAlign=top>
557<tt>reference</tt> if <tt>a</tt> is mutable, <br> <tt>const_reference</tt>
558otherwise.
559</TD>
560<TD VAlign=top>
561Equivalent to <tt>*(--a.end())</tt>.
562</TD>
563</TR>
564
565</table>
566
567<h4>SequentialCollection</h4>
568
569The elements are arranged in a strict linear order. No extra methods
570are required.
571
572<h4>RandomAccessCollection</h4>
573
574The iterators of a RandomAccessCollection satisfy all of the
575requirements of <a
576href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>
577except that the reference type does not have to be a real C++
578reference. In addition, a RandomAccessCollection provides
579an element access operator.
580
581<p>
582
583<Table border>
584<TR>
585<TH>
586Name
587</TH>
588<TH>
589Expression
590</TH>
591<TH>
592Return type
593</TH>
594<TH>
595Semantics
596</TH>
597</TR>
598<TR>
599<TD VAlign=top>
600Element Access
601</TD>
602<TD VAlign=top>
603<tt>a[n]</tt>
604</TD>
605<TD VAlign=top>
606<tt>reference</tt> if <tt>a</tt> is mutable,
607<tt>const_reference</tt> otherwise.
608</TD>
609<TD VAlign=top>
610Returns the nth element of the Collection.
611<tt>n</tt> must be convertible to <tt>size_type</tt>.
612Precondition: <tt>0 &lt;= n &lt; a.size()</tt>.
613</TD>
614</TR>
615
616</table>
617
618<h3>Notes</h3>
619
620<P><A name="1">[1]</A> 
621
622The reference type does not have to be a real C++ reference. The
623requirements of the reference type depend on the context within which
624the Collection is being used. Specifically it depends on the
625requirements the context places on the value type of the Collection.
626The reference type of the Collection must meet the same requirements
627as the value type. In addition, the reference objects must be
628equivalent to the value type objects in the collection (which is
629trivially true if they are the same object).  Also, in a mutable
630Collection, an assignment to the reference object must result in an
631assignment to the object in the Collection (again, which is trivially
632true if they are the same object, but non-trivial if the reference
633type is a proxy class).
634
635<h3>See also</h3>
636<A href="http://www.sgi.com/tech/stl/Container.html">Container</A>
637
638
639<br>
640<HR>
641<TABLE>
642<TR valign=top>
643<TD nowrap>Copyright &copy 2000</TD><TD>
644<A HREF=http://www.boost.org/people/jeremy_siek.htm>Jeremy Siek</A>, Univ.of Notre Dame and C++ Library & Compiler Group/SGI (<A HREF="mailto:jsiek@engr.sgi.com">jsiek@engr.sgi.com</A>)
645</TD></TR></TABLE>
646
647</BODY>
648</HTML> 
Note: See TracBrowser for help on using the repository browser.