535 lines
15 KiB
HTML
535 lines
15 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Language" content="en-us">
|
|
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
|
|
|
|
<title>Collection</title>
|
|
</head>
|
|
|
|
<body bgcolor="#FFFFFF" link="#0000EE" text="#000000" vlink="#551A8B" alink=
|
|
"#FF0000">
|
|
<h1><img src="../../boost.png" alt="boost logo" width="277" align="middle"
|
|
height="86"><br>
|
|
Collection</h1>
|
|
|
|
<h3>Description</h3>
|
|
|
|
<p>A Collection is a <i>concept</i> similar to the STL <a href=
|
|
"http://www.sgi.com/tech/stl/Container.html">Container</a> concept. A
|
|
Collection provides iterators for accessing a range of elements and
|
|
provides information about the number of elements in the Collection.
|
|
However, a Collection has fewer requirements than a Container. The
|
|
motivation for the Collection concept is that there are many useful
|
|
Container-like types that do not meet the full requirements of Container,
|
|
and many algorithms that can be written with this reduced set of
|
|
requirements. To summarize the reduction in requirements:</p>
|
|
|
|
<ul>
|
|
<li>It is not required to "own" its elements: the lifetime of an element
|
|
in a Collection does not have to match the lifetime of the Collection
|
|
object, though the lifetime of the element should cover the lifetime of
|
|
the Collection object.</li>
|
|
|
|
<li>The semantics of copying a Collection object is not defined (it could
|
|
be a deep or shallow copy or not even support copying).</li>
|
|
|
|
<li>The associated reference type of a Collection does not have to be a
|
|
real C++ reference.</li>
|
|
</ul>Because of the reduced requirements, some care must be taken when
|
|
writing code that is meant to be generic for all Collection types. In
|
|
particular, a Collection object should be passed by-reference since
|
|
assumptions can not be made about the behaviour of the copy constructor.
|
|
|
|
<h3>Associated types</h3>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<td valign="top">Value type</td>
|
|
|
|
<td valign="top"><tt>X::value_type</tt></td>
|
|
|
|
<td valign="top">The type of the object stored in a Collection. If the
|
|
Collection is <i>mutable</i> then the value type must be <a href=
|
|
"http://www.sgi.com/tech/stl/Assignable.html">Assignable</a>. Otherwise
|
|
the value type must be <a href=
|
|
"./CopyConstructible.html">CopyConstructible</a>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Iterator type</td>
|
|
|
|
<td valign="top"><tt>X::iterator</tt></td>
|
|
|
|
<td valign="top">The type of iterator used to iterate through a
|
|
Collection's elements. The iterator's value type is expected to be the
|
|
Collection's value type. A conversion from the iterator type to the
|
|
const iterator type must exist. The iterator type must be an <a href=
|
|
"http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Const iterator type</td>
|
|
|
|
<td valign="top"><tt>X::const_iterator</tt></td>
|
|
|
|
<td valign="top">A type of iterator that may be used to examine, but
|
|
not to modify, a Collection's elements.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Reference type</td>
|
|
|
|
<td valign="top"><tt>X::reference</tt></td>
|
|
|
|
<td valign="top">A type that behaves like a reference to the
|
|
Collection's value type. <a href="#n1">[1]</a></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Const reference type</td>
|
|
|
|
<td valign="top"><tt>X::const_reference</tt></td>
|
|
|
|
<td valign="top">A type that behaves like a const reference to the
|
|
Collection's value type.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Pointer type</td>
|
|
|
|
<td valign="top"><tt>X::pointer</tt></td>
|
|
|
|
<td valign="top">A type that behaves as a pointer to the Collection's
|
|
value type.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Distance type</td>
|
|
|
|
<td valign="top"><tt>X::difference_type</tt></td>
|
|
|
|
<td valign="top">A signed integral type used to represent the distance
|
|
between two of the Collection's iterators. This type must be the same
|
|
as the iterator's distance type.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Size type</td>
|
|
|
|
<td valign="top"><tt>X::size_type</tt></td>
|
|
|
|
<td valign="top">An unsigned integral type that can represent any
|
|
nonnegative value of the Collection's distance type.</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Notation</h3>
|
|
|
|
<table summary="">
|
|
<tr>
|
|
<td valign="top"><tt>X</tt></td>
|
|
|
|
<td valign="top">A type that is a model of Collection.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top"><tt>a</tt>, <tt>b</tt></td>
|
|
|
|
<td valign="top">Object of type <tt>X</tt>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top"><tt>T</tt></td>
|
|
|
|
<td valign="top">The value type of <tt>X</tt>.</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Valid expressions</h3>
|
|
|
|
<p>The following expressions must be valid.</p>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<th>Name</th>
|
|
|
|
<th>Expression</th>
|
|
|
|
<th>Return type</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Beginning of range</td>
|
|
|
|
<td valign="top"><tt>a.begin()</tt></td>
|
|
|
|
<td valign="top"><tt>iterator</tt> if <tt>a</tt> is mutable,
|
|
<tt>const_iterator</tt> otherwise</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">End of range</td>
|
|
|
|
<td valign="top"><tt>a.end()</tt></td>
|
|
|
|
<td valign="top"><tt>iterator</tt> if <tt>a</tt> is mutable,
|
|
<tt>const_iterator</tt> otherwise</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Size</td>
|
|
|
|
<td valign="top"><tt>a.size()</tt></td>
|
|
|
|
<td valign="top"><tt>size_type</tt></td>
|
|
</tr><!--
|
|
<TR>
|
|
<TD VAlign=top>
|
|
Maximum size
|
|
</TD>
|
|
<TD VAlign=top>
|
|
<tt>a.max_size()</tt>
|
|
</TD>
|
|
<TD VAlign=top>
|
|
<tt>size_type</tt>
|
|
</TD>
|
|
</TR>
|
|
-->
|
|
|
|
<tr>
|
|
<td valign="top">Empty Collection</td>
|
|
|
|
<td valign="top"><tt>a.empty()</tt></td>
|
|
|
|
<td valign="top">Convertible to <tt>bool</tt></td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Swap</td>
|
|
|
|
<td valign="top"><tt>a.swap(b)</tt></td>
|
|
|
|
<td valign="top"><tt>void</tt></td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Expression semantics</h3>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<th>Name</th>
|
|
|
|
<th>Expression</th>
|
|
|
|
<th>Semantics</th>
|
|
|
|
<th>Postcondition</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Beginning of range</td>
|
|
|
|
<td valign="top"><tt>a.begin()</tt></td>
|
|
|
|
<td valign="top">Returns an iterator pointing to the first element in
|
|
the Collection.</td>
|
|
|
|
<td valign="top"><tt>a.begin()</tt> is either dereferenceable or
|
|
past-the-end. It is past-the-end if and only if <tt>a.size() ==
|
|
0</tt>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">End of range</td>
|
|
|
|
<td valign="top"><tt>a.end()</tt></td>
|
|
|
|
<td valign="top">Returns an iterator pointing one past the last element
|
|
in the Collection.</td>
|
|
|
|
<td valign="top"><tt>a.end()</tt> is past-the-end.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Size</td>
|
|
|
|
<td valign="top"><tt>a.size()</tt></td>
|
|
|
|
<td valign="top">Returns the size of the Collection, that is, its
|
|
number of elements.</td>
|
|
|
|
<td valign="top"><tt>a.size() >= 0</tt></td>
|
|
</tr><!--
|
|
<TR>
|
|
<TD VAlign=top>
|
|
Maximum size
|
|
</TD>
|
|
<TD VAlign=top>
|
|
<tt>a.max_size()</tt>
|
|
</TD>
|
|
<TD VAlign=top>
|
|
|
|
</TD>
|
|
<TD VAlign=top>
|
|
Returns the largest size that this Collection can ever have. <A href="#8">[8]</A>
|
|
</TD>
|
|
<TD VAlign=top>
|
|
<tt>a.max_size() >= 0 && a.max_size() >= a.size()</tt>
|
|
</TD>
|
|
</TR>
|
|
-->
|
|
|
|
<tr>
|
|
<td valign="top">Empty Collection</td>
|
|
|
|
<td valign="top"><tt>a.empty()</tt></td>
|
|
|
|
<td valign="top">Equivalent to <tt>a.size() == 0</tt>. (But possibly
|
|
faster.)</td>
|
|
|
|
<td valign="top"> </td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Swap</td>
|
|
|
|
<td valign="top"><tt>a.swap(b)</tt></td>
|
|
|
|
<td valign="top">Equivalent to <tt>swap(a,b)</tt></td>
|
|
|
|
<td valign="top"> </td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Complexity guarantees</h3>
|
|
|
|
<p><tt>begin()</tt> and <tt>end()</tt> are amortized constant time.</p>
|
|
|
|
<p><tt>size()</tt> is at most linear in the Collection's size.
|
|
<tt>empty()</tt> is amortized constant time.</p>
|
|
|
|
<p><tt>swap()</tt> is at most linear in the size of the two
|
|
collections.</p>
|
|
|
|
<h3>Invariants</h3>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<td valign="top">Valid range</td>
|
|
|
|
<td valign="top">For any Collection <tt>a</tt>, <tt>[a.begin(),
|
|
a.end())</tt> is a valid range.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Range size</td>
|
|
|
|
<td valign="top"><tt>a.size()</tt> is equal to the distance from
|
|
<tt>a.begin()</tt> to <tt>a.end()</tt>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Completeness</td>
|
|
|
|
<td valign="top">An algorithm that iterates through the range
|
|
<tt>[a.begin(), a.end())</tt> will pass through every element of
|
|
<tt>a</tt>.</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Models</h3>
|
|
|
|
<ul>
|
|
<li><tt>array</tt></li>
|
|
|
|
<li><tt>array_ptr</tt></li>
|
|
|
|
<li><tt>vector<bool></tt></li>
|
|
</ul>
|
|
|
|
<h3>Collection Refinements</h3>
|
|
|
|
<p>There are quite a few concepts that refine the Collection concept,
|
|
similar to the concepts that refine the Container concept. Here is a brief
|
|
overview of the refining concepts.</p>
|
|
|
|
<h4>ForwardCollection</h4>
|
|
|
|
<p>The elements are arranged in some order that does not change
|
|
spontaneously from one iteration to the next. As a result, a
|
|
ForwardCollection is <a href=
|
|
"http://www.sgi.com/tech/stl/EqualityComparable.html">EqualityComparable</a>
|
|
and <a href=
|
|
"http://www.sgi.com/tech/stl/LessThanComparable.html">LessThanComparable</a>.
|
|
In addition, the iterator type of a ForwardCollection is a
|
|
MultiPassInputIterator which is just an InputIterator with the added
|
|
requirements that the iterator can be used to make multiple passes through
|
|
a range, and that if <tt>it1 == it2</tt> and <tt>it1</tt> is
|
|
dereferenceable then <tt>++it1 == ++it2</tt>. The ForwardCollection also
|
|
has a <tt>front()</tt> method.</p>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<th>Name</th>
|
|
|
|
<th>Expression</th>
|
|
|
|
<th>Return type</th>
|
|
|
|
<th>Semantics</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Front</td>
|
|
|
|
<td valign="top"><tt>a.front()</tt></td>
|
|
|
|
<td valign="top"><tt>reference</tt> if <tt>a</tt> is mutable,<br>
|
|
<tt>const_reference</tt> otherwise.</td>
|
|
|
|
<td valign="top">Equivalent to <tt>*(a.begin())</tt>.</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h4>ReversibleCollection</h4>
|
|
|
|
<p>The container provides access to iterators that traverse in both
|
|
directions (forward and reverse). The iterator type must meet all of the
|
|
requirements of <a href=
|
|
"http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>
|
|
except that the reference type does not have to be a real C++ reference.
|
|
The ReversibleCollection adds the following requirements to those of
|
|
ForwardCollection.</p>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<th>Name</th>
|
|
|
|
<th>Expression</th>
|
|
|
|
<th>Return type</th>
|
|
|
|
<th>Semantics</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Beginning of range</td>
|
|
|
|
<td valign="top"><tt>a.rbegin()</tt></td>
|
|
|
|
<td valign="top"><tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
|
|
<tt>const_reverse_iterator</tt> otherwise.</td>
|
|
|
|
<td valign="top">Equivalent to
|
|
<tt>X::reverse_iterator(a.end())</tt>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">End of range</td>
|
|
|
|
<td valign="top"><tt>a.rend()</tt></td>
|
|
|
|
<td valign="top"><tt>reverse_iterator</tt> if <tt>a</tt> is mutable,
|
|
<tt>const_reverse_iterator</tt> otherwise.</td>
|
|
|
|
<td valign="top">Equivalent to
|
|
<tt>X::reverse_iterator(a.begin())</tt>.</td>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Back</td>
|
|
|
|
<td valign="top"><tt>a.back()</tt></td>
|
|
|
|
<td valign="top"><tt>reference</tt> if <tt>a</tt> is mutable,<br>
|
|
<tt>const_reference</tt> otherwise.</td>
|
|
|
|
<td valign="top">Equivalent to <tt>*(--a.end())</tt>.</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h4>SequentialCollection</h4>
|
|
|
|
<p>The elements are arranged in a strict linear order. No extra methods are
|
|
required.</p>
|
|
|
|
<h4>RandomAccessCollection</h4>
|
|
|
|
<p>The iterators of a RandomAccessCollection satisfy all of the
|
|
requirements of <a href=
|
|
"http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>
|
|
except that the reference type does not have to be a real C++ reference. In
|
|
addition, a RandomAccessCollection provides an element access operator.</p>
|
|
|
|
<table border summary="">
|
|
<tr>
|
|
<th>Name</th>
|
|
|
|
<th>Expression</th>
|
|
|
|
<th>Return type</th>
|
|
|
|
<th>Semantics</th>
|
|
</tr>
|
|
|
|
<tr>
|
|
<td valign="top">Element Access</td>
|
|
|
|
<td valign="top"><tt>a[n]</tt></td>
|
|
|
|
<td valign="top"><tt>reference</tt> if <tt>a</tt> is mutable,
|
|
<tt>const_reference</tt> otherwise.</td>
|
|
|
|
<td valign="top">Returns the nth element of the Collection. <tt>n</tt>
|
|
must be convertible to <tt>size_type</tt>. Precondition: <tt>0 <= n
|
|
< a.size()</tt>.</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Notes</h3>
|
|
|
|
<p><a name="n1" id="n1">[1]</a> The reference type does not have to be a
|
|
real C++ reference. The requirements of the reference type depend on the
|
|
context within which the Collection is being used. Specifically it depends
|
|
on the requirements the context places on the value type of the Collection.
|
|
The reference type of the Collection must meet the same requirements as the
|
|
value type. In addition, the reference objects must be equivalent to the
|
|
value type objects in the collection (which is trivially true if they are
|
|
the same object). Also, in a mutable Collection, an assignment to the
|
|
reference object must result in an assignment to the object in the
|
|
Collection (again, which is trivially true if they are the same object, but
|
|
non-trivial if the reference type is a proxy class).</p>
|
|
|
|
<h3>See also</h3>
|
|
|
|
<p><a href=
|
|
"http://www.sgi.com/tech/stl/Container.html">Container</a><br></p>
|
|
<hr>
|
|
|
|
<p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
|
|
"../../doc/images/valid-html401.png" alt="Valid HTML 4.01 Transitional"
|
|
height="31" width="88"></a></p>
|
|
|
|
<p>Revised
|
|
<!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05
|
|
December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p>
|
|
|
|
<table summary="">
|
|
<tr valign="top">
|
|
<td nowrap><i>Copyright © 2000</i></td>
|
|
|
|
<td><i><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>)</i></td>
|
|
</tr>
|
|
</table>
|
|
|
|
<p><i>Distributed under the Boost Software License, Version 1.0. (See
|
|
accompanying file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
|
|
copy at <a href=
|
|
"http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
|
|
</body>
|
|
</html>
|