1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
|
<!DOCTYPE HTML PUBLIC "-//Netscape Comm. Corp.//DTD HTML//EN">
<HTML>
<HEAD>
<!-- SGI_COMMENT COSMOCREATE -->
<!-- SGI_COMMENT VERSION NUMBER="1.0" -->
<TITLE>How to use the STL documentation</TITLE>
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
ALINK="#ff0000">
<IMG SRC="CorpID.gif"
ALT="SGI" HEIGHT="43" WIDTH="151">
<!--end header-->
<CENTER><H1 ALIGN="CENTER">How to use the STL documentation</H1>
</CENTER><P>
This site documents all of the components (classes, functions, and
concepts) in the SGI Standard Template Library. Each page describes a
single component, and also includes links to related components. </P>
<P>
This documentation assumes a general familiarity with C++, especially
with C++ templates. Additionally, you should read <A
HREF="stl_introduction.html">Introduction to the Standard Template
Library</A> before proceeding to the pages that describe individual
components: the introductory page defines several terms that are used
throughout the documentation.</P>
<H2>
Classification of STL components</H2>
<P>
The STL components are divided into six broad categories on the basis
of functionality: <I>Containers</I>, <I>Iterators</I>, <I>Algorithms</I>, <I>Function
Objects</I>, <I>Utilities</I>, and <I>Allocators</I>; these categories
are defined in the <A HREF="stl_introduction.html">Introduction</A>,
and the <A HREF="table_of_contents.html">Table of Contents</A> is
organized according to them. </P>
<P>
The STL documentation contains two indices. One of them, the <A
HREF="stl_index.html">Main Index</A>, lists all components in
alphabetical order. The other, the <A HREF="stl_index_cat.html">Divided
Index</A>, contains a separate alphabetical listing for each category.
The Divided Index includes one category that is not present in the
Table of Contents: <I>Adaptors</I>. An adaptor is a class or a
function that transforms one interface into a different one. The reason
that adaptors don't appear in the Table of Contents is that no
component is merely an adaptor, but always an adaptor and something
else; <TT><A href="stack.html">stack</A></TT>, for example, is a container and an adaptor.
Accordingly, <TT><A href="stack.html">stack</A></TT> appears in two different places in the
Divided Index. There are several other components that appear in the
Divided Index in more than one place. </P>
<P>
The STL documentation classifies components in two ways.
<OL>
<LI><i>Categories</i> are a classification by functionality.
The categories are:
<UL>
<LI>Container
<LI>Iterator
<LI>Algorithm
<LI>Function Object
<LI>Utility
<LI>Adaptor
<LI>Allocator.
</UL>
<LI><i>Component types</i> are a structural classification: one
based on what kind of C++ entity (if any) a component is. The
component types are:
<UL>
<LI>Type (<i>i.e.</i> a <TT>struct</TT> or <TT>class</TT>)
<LI>Function
<LI>Concept (as defined in the
<A HREF="stl_introduction.html">Introduction</A>).
</UL>
</OL>
</P>
<P>
These two classification schemes are independent, and each of them
applies to every STL component; <TT><A href="Vector.html">vector</A></TT>, for example, is a <I>type</I>
whose category is <I>Containers</I>, and <B><A href="ForwardIterator.html">Forward Iterator</A></B>
is a <I>concept</I> whose category is <I>Iterators</I>. </P>
<P>
Both of these classification schemes appear at the top of every page
that documents an STL component. The upper left corner identifies the
the component's category as <I>Containers</I>,<I> Iterators</I>, <I>Algorithms</I>, <I>Function
Objects</I>, <I>Utilities</I>, <I>Adaptors</I>, or <I>Allocators</I>,
and the upper right corner identifies the component as a <I>type</I>, a <I>function</I>,
or a <I>concept</I>. </P>
<H2>
Using the STL documentation</H2>
<P>
The STL is a <I>generic</I> library: almost every class and function is
a template. Accordingly, one of the most important purposes of the STL
documentation is to provide a clear description of which types may be
used to instantiate those templates. As described in the <A
HREF="stl_introduction.html">Introduction</A>, a <I>concept </I>is a
generic set of requirements that a type must satisfy: a type is said to
be a <I>model of</I> a concept if it satisfies all of that concept's
requirements. </P>
<P>
Concepts are used very heavily in the STL documentation, both because
they directly express type requirements, and because they are a tool
for organizing types conceptually. (For example, the fact that <TT><A href="ostream_iterator.html">ostream_iterator</A></TT>
and <TT><A href="insert_iterator.html">insert_iterator</A></TT> are both models of <B><A href="OutputIterator.html">Output Iterator</A></B>
is an important statement about what those two classes
have in common.) Concepts are used for the documentation of both <I>types</I>
and <I>functions</I>.</P>
<H3>
The format of a <I>concept </I>page</H3>
<P>
A page that documents a <I>concept</I> has the following sections. </P>
<UL>
<LI>
<B>Summary:</B> A description of the concept's purpose.
<LI>
<B>Refinement of:</B> A list of other concepts that this concept <I>refines</I>,
with links to those concepts.
<LI>
<B>Associated types:</B> A concept is a set of requirements on some
type. Frequently, however, some of those requirements involve some
other type. For example, one of the<B> <A href="UnaryFunction.html">Unary Function</A></B>
requirements is that a <B><A href="UnaryFunction.html">Unary Function</A></B> must have an <I>argument
type</I>; if <TT>F</TT> is a type that models <B><A href="UnaryFunction.html">Unary Function</A></B>
and <TT>f</TT> is an object of type <TT>F</TT>, then, in the
expression <TT>f(x)</TT>, <TT>x</TT> must be of <TT>F</TT>'s
argument type. If a concept does have any such associated types, then
they are defined in this section.
<LI>
<B>Notation</B>: The next three sections, <B>definitions</B>, <B>valid
expressions</B>, and <B>expression semantics</B>, present
expressions involving types that model the concept being defined. This
section defines the meaning of the variables and identifiers used in
those expressions.
<LI>
<B>Definitions</B>: Some concepts, such as <B><A href="LessThanComparable.html">LessThan Comparable</A></B>,
use specialized terminology. If a concept requires
any such terminology, it is defined in this section.
<LI>
<B>Valid Expressions</B>: A type that models a concept is required
to support certain operations. In most cases, it doesn't make sense to
describe this in terms of specific functions or member functions: it
doesn't make any difference, for example, whether a type that models
<B><A href="InputIterator.html">Input Iterator</A></B> uses a global function or a member function to
provide <TT>operator++</TT>. This section lists the expressions
that a type modeling this concept must support. It includes any
special requirements (if any) on the types of the expression's
operands, and the expression's return type (if any).
<LI>
<B>Expression Semantics:</B> The previous section, <B>valid
expressions</B>, lists which expressions involving a type must be
supported; it doesn't, however, define the meaning of those
expressions. This section does: it lists the semantics, preconditions,
and postconditions for the expressions defined in the previous section.
<LI>
<B>Complexity Guarantees</B>: In some cases, the run-time
complexity of certain operations is an important part of a concept's
requirements. For example, one of the most significant distinctions
between a <B><A href="BidirectionalIterator.html">Bidirectional Iterator</A></B> and a
<B><A href="RandomAccessIterator.html">Random Access Iterator</A></B> is that, for random access iterators,
expressions like <TT>p + n</TT> take constant time. Any such
requirements on run-time complexity are listed in this section.
<LI>
<B>Invariants:</B> Many concepts require that some property is
always true for objects of a type that models the concept being
defined. For example, <B><A href="LessThanComparable.html">LessThan Comparable</A></B> imposes the
requirement of <I>transitivity</I>: if <TT>x < y</TT> and <TT>y
< z</TT>, then <TT>x < z</TT>. Some such properties are
"axioms" (that is, they are independent of any other
requirements) and some are "theorems" (that is, they follow
either from requirements in the <B>expression semantics</B> section
or from other requirements in the <B>invariants</B> section).
<LI>
<B>Models</B>: A list of examples of types that are models of this
concept. Note that this list is not intended to be complete: in most
cases a complete list would be impossible, because there are an
infinite number of types that could model the concept.
<LI>
<B>Notes</B>: Footnotes (if any) that are referred to by other
parts of the page.
<LI>
<B>See Also</B>: Links to other related pages.
</UL>
<H3>
The format of a <I>type </I>page</H3>
<P>
A page that documents a <I>type</I> has the following sections. </P>
<UL>
<LI>
<B>Description</B>. A summary of the type's properties.
<LI>
<B>Example of use</B>: A code fragment involving the type.
<LI>
<B>Definition</B>: A link to the source code where the type is
defined.
<LI>
<B>Template parameters</B>: Almost all STL structs and classes are
templates. This section lists the name of each template parameter, its
purpose, and its default value (if any).
<LI>
<B>Model of</B>: A list of the concepts that this type is a model
of, and links to those concepts. Note that a type may be a model of
more than one concept: <TT><A href="Vector.html">vector</A></TT>, for example, is a model
of both <B><A href="RandomAccessContainer.html">Random Access Container</A></B> and
<B><A href="BackInsertionSequence.html">Back Insertion Sequence</A></B>. If a type is a model of two different concepts, that
simply means that it satisfies the requirements of both.
<LI>
<B>Type requirements</B>: The template parameters of a class
template usually must satisfy a set of requirements. Many of these can
simply be expressed by listing which concept a template parameter must
conform to, but some type requirements are slightly more complicated,
and involve a relationship between two different template parameters.
<LI>
<B>Public base classes</B>: If this class inherits from any other
classes, they are listed in this section.
<LI>
<B>Members</B>: A list of this type's nested types, member
functions, member variables, and associated non-member functions. In
most cases these members are simply listed, rather than defined: since
the type is a model of some concept, detailed definitions aren't
usually necessary. For example, <TT><A href="Vector.html">vector</A></TT> is a model of <B><A href="Container.html">Container</A></B>,
so the description of the member function <TT>begin()</TT> in the <B><A href="Container.html">Container</A></B>
page applies to <TT><A href="Vector.html">vector</A></TT>, and there is no need to
repeat it in the <TT><A href="Vector.html">vector</A></TT> page. Instead, the <B>Members</B>
section provides a very brief description of each member and a link to
whatever page defines that member more fully.
<LI>
<B>New Members:</B> A type might have some members that are not
part of the requirements of any of the concepts that it models. For
example, <A href="Vector.html">vector</A> has a member function called <TT>capacity()</TT>,
which is not part of the <B><A href="RandomAccessContainer.html">Random Access Container</A></B> or
<B><A href="BackInsertionSequence.html">Back Insertion Sequence</A></B> requirements. These members are defined in
the <B>New members</B> section.
<LI>
<B>Notes</B>: Footnotes (if any) that are referred to by other
parts of the page.
<LI>
<B>See Also</B>: Links to other related pages.
</UL>
<H3>
The format of a <I>function </I>page</H3>
<P>
A page that documents a <I>function</I> has the following sections. </P>
<UL>
<LI>
<B>Prototype:</B> the function's declaration.
<LI>
<B>Description:</B> A summary of what the function does.
<LI>
<B>Definition</B>: A link to the source code where the function is
defined.
<LI>
<B>Requirements on types:</B> Most functions in the STL are function
templates. This section lists the requirements that must be satisfied
by the function's template parameters. Sometimes the requirements can
simply be expressed by listing which concept a template parameter must
conform to, but sometimes they are more complicated and involve a
relationship between two different template parameters. In the case of <TT><A href="find.html">find</A></TT>,
for example, the requirements are that the parameter <TT>InputIterator</TT>
is a model of <B><A href="InputIterator.html">Input Iterator</A></B>, that the parameter <TT>EqualityComparable</TT>
is a model of <B><A href="EqualityComparable.html">Equality Comparable</A></B>, and that comparison
for equality is possible between objects of type <TT>EqualityComparable</TT>
and objects of <TT>InputIterator</TT>'s value types.
<LI>
<B>Preconditions:</B> Functions usually aren't guaranteed to yield
a well-defined result for any possible input, but only for valid input;
it is an error to call a function with invalid input. This section
describes the conditions for validity.
<LI>
<B>Complexity:</B> Guarantees on the function's run-time
complexity. For example, <TT><A href="find.html">find</A></TT>'s run-time complexity is
linear in the length of the input range.
<LI>
<B>Example of use:</B> A code fragment that illustrates how to use
the function.
<LI>
<B>Notes</B>: Footnotes (if any) that are referred to by other
parts of the page.
<LI>
<B>See Also</B>: Links to other related pages.
</UL>
<!--start footer-->
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54"
ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif"
HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright ©
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML>
|
