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
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
|
<!DOCTYPE HTML PUBLIC "-//Netscape Comm. Corp.//DTD HTML//EN">
<!--
-- Copyright (c) 1999
-- Silicon Graphics Computer Systems, Inc.
--
-- Permission to use, copy, modify, distribute and sell this software
-- and its documentation for any purpose is hereby granted without fee,
-- provided that the above copyright notice appears in all copies and
-- that both that copyright notice and this permission notice appear
-- in supporting documentation. Silicon Graphics makes no
-- representations about the suitability of this software for any
-- purpose. It is provided "as is" without express or implied warranty.
--
-->
<HTML>
<HEAD>
<TITLE>SGI STL: Frequently Asked Questions</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-->
<H1>Frequently Asked Questions</H1>
<H2>about the SGI Standard Template Library</H2>
<hr>
<P><b>Is the STL Y2K compliant?</b>
<br>
Yes. The STL does not store or manipulate dates in any way, so there
are no year 2000 issues.
<P><b>Can I download this entire site for offline viewing?</b>
<br>
Yes. From the <A Href="index.html">home page</A>, go to the <b>Download
the STL</b> page. You will find links
for downloading the entire STL documentation as a single <tt>zip</tt>,
<tt>tar</tt>, or <tt>tar.gz</tt> file.
<P>
The documentation is a collection of <tt>HTML</tt> files. It
does not exist in the form of a single text or
PostScript<FONT Size="-1"><SUP>TM</SUP></FONT> document. The
<A Href="other_resources.html">Other Resources</A> page lists
several books about the STL.
<P><b>Which compilers are supported?</b>
<br>
The STL has been tested on these compilers: SGI 7.1 and later, or 7.0
with the -n32 or -64 flag; gcc 2.8 or egcs 1.x; Microsoft 5.0 and
later. (But see below.) Boris Fomitchev distributes a
<A Href="http://www.metabyte.com/~fbp/stl/index.html">port</A> for
some other compilers.
<P>
If you succeed in using the SGI STL with some other compiler, please
<A href="mailto:stl@sgi.com">let us know</A>, and please tell us what
modifications (if any) you had to make. We expect that most of the
changes will be restricted to the <tt><stl_config.h></tt> header.
<P><b>What about older SGI compilers?</b>
<br>
Given the rate of improvement in C++ implementations, SGI strongly
recommends that you upgrade your compiler. If this is not possible,
you might try the version of the STL for older Borland and Microsoft
compilers (see the <b>Download the STL</b> page), or Boris Fomitchev's
<A Href="http://www.metabyte.com/~fbp/stl/index.html">port</A>. Neither
of these is supported.
<P><b>How do I install the SGI STL?</b>
<br>
You should unpack the STL include files in a new directory, and then
use the <tt>-I</tt> (or <tt>/I</tt>) option to direct the compiler to
look there first. We don't recommend overwriting the vendor's include
files.
<P>
At present the SGI STL consists entirely of header files. You don't have
to build or link in any additional runtime libraries.
<P><b>Are there any compatibility issues with Visual C++?</b>
<br>
Visual C++ provides its own STL implementation, and some of the other
Microsoft C++ library headers may rely on that implementation. In
particular, the SGI STL has not been tested in combination with
Microsoft's new <tt><iostream></tt> header. It has been used
successfully with the older <tt><iostream.h></tt> header.
<P><b>Is the SGI STL thread safe?</b>
<br>
Yes. However, you should be aware that not everyone uses the
phrase "thread safe" the same way. See our
<A Href="thread_safety.html">discussion of thread safety</A>
for our design goals.
<P><B>Are hash tables part of the C++ standard?</b>
<br>
No. The hash table classes (<tt><A href="hash_set.html">hash_set</A></tt>, <tt><A href="hash_map.html">hash_map</A></tt>
<tt><A href="hash_multiset.html">hash_multiset</A></tt> <tt><A href="hash_multimap.html">hash_multimap</A></tt> <tt><A href="hash.html">hash</A></tt>)
are an extension. They may be added to a future revision of the C++
standard.
<P>
The <tt><A href="Rope.html">rope</A></tt> and <tt><A href="Slist.html">slist</A></tt> classes are also extensions.
<P><B>Why is <tt>list<>::size()</tt> linear time?</b>
<br>
The <tt>size()</tt> member function, for <tt><A href="List.html">list</A></tt> and
<tt><A href="Slist.html">slist</A></tt>, takes time proportional to the number of elements
in the list. This was a deliberate tradeoff. The only way to get a
constant-time <tt>size()</tt> for linked lists would be to maintain an
extra member variable containing the list's size. This would require
taking extra time to update that variable (it would make
<tt>splice()</tt> a linear time operation, for example), and it would
also make the list larger. Many list algorithms don't require that
extra word (algorithms that do require it might do better with vectors
than with lists), and, when it is necessary to maintain an explicit
size count, it's something that users can do themselves.
<P>
This choice is permitted by the C++ standard. The standard says that
<tt>size()</tt> "should" be constant time, and
"should" does not mean the same thing as "shall".
This is the officially recommended ISO wording for saying that an
implementation is supposed to do something unless there is a good
reason not to.
<P>
One implication of linear time <tt>size()</tt>: you should never write
<pre>
if (L.size() == 0)
...
</pre>
Instead, you should write
<pre>
if (L.empty())
...
</pre>
<P><B>Why doesn't <tt>map</tt>'s operator< use the <tt>map</tt>'s
comparison function?</b>
<br>
A <tt>map</tt> has a notion of comparison, since one of its template
parameters is a comparison function. However, <tt>operator<</tt>
for maps uses the elements' <tt>operator<</tt> rather than that
comparison function. This appears odd, but it is deliberate and we
believe that it is correct.
<P>
At the most trivial level, this isn't a bug in our implementation
because it's what's mandated by the C++ standard. (The behavior of
<tt>operator<</tt> is described in Table 65, in section 23.1.)
<P>
A more interesting question: is the requirement in the standard correct,
or is there actually a bug in the standard?
<P>
We believe that the requirements in the standard are correct.
<P>
First, there's a consistency argument: <tt>operator<</tt> for a
<tt><A href="Vector.html">vector</A></tt> (or <tt><A href="Deque.html">deque</A></tt>, or <tt><A href="List.html">list</A></tt>) uses
the element's <tt>operator<</tt>. Should <tt><A href="Map.html">map</A></tt>'s
<tt>operator<</tt> do something else, just because there is another
plausible way to compare objects? It's reasonable to say, for all
containers, that <tt>operator<</tt> always means
<tt>operator<</tt>, and that if you need a different kind of
comparison you can explicitly use <tt><A href="lexicographical_compare.html">lexicographical_compare</A></tt>.
<P>
Second, if we did use the <tt><A href="Map.html">map</A></tt>'s comparison function,
there would be a problem: which one do we use? There are two
<tt>map</tt> arguments, and, while we know that their comparison
functions have the same type, we don't know that they have the same
behavior. The comparison function, after all, is a function object,
and it might have internal state that affects the comparison. (You
might have a function object to compare strings, for example, with a
boolean flag that determines whether the comparison is
case-sensitive.)
<P>
There's also a related question, incidentally: how should
<tt>operator==</tt> behave for sets? A <tt>set</tt>'s comparison
function induces an equivalence relation, so, just as you can use the
<tt>set</tt>'s comparison function for lexicographical ordering, you
could also use it for a version of equality. Again, though, we define
<tt>operator==(const set&, const set&)</tt> so that it just
calls the elements' <tt>operator==</tt>.
<P><b>Why does a <tt>vector</tt> expand its storage by a factor of two
when it performs a reallocation?</b>
<br>
Expanding a <tt><A href="Vector.html">vector</A></tt> by a factor of two is a time-space tradeoff;
it means that each element will (on average) be copied twice
when you're building a <tt><A href="Vector.html">vector</A></tt> one element at a time, and that
the ratio of wasted to used space is at most 1. (In general,
if the exponent for expansion is r, the worst case wasted/used ratio is
r - 1 and the number of times an element is copied approaches
r/(r - 1). If r = 1.25, for example, then elements are copied
five times instead of twice.)
<P>
If you need to control <tt><A href="Vector.html">vector</A></tt>'s memory usage more finely,
you can use the member functions <tt>capacity()</tt> and
<tt>reserve()</tt> instead of relying on automatic reallocation.
<P><b>Why do the <i>pop</i> member functions return <tt>void</tt>?</b>
<br>
All of the STL's <i>pop</i> member functions (<tt>pop_back</tt> in
<tt><A href="Vector.html">vector</A></tt>, <tt><A href="List.html">list</A></tt>, and <tt><A href="Deque.html">deque</A></tt>;
<tt>pop_front</tt> in <tt><A href="List.html">list</A></tt>, <tt><A href="Slist.html">slist</A></tt>, and
<tt><A href="Deque.html">deque</A></tt>; <tt>pop</tt> in <tt><A href="stack.html">stack</A></tt>,
<tt><A href="queue.html">queue</A></tt>, and <tt><A href="priority_queue.html">priority_queue</A></tt>) return <tt>void</tt>,
rather than returning the element that was removed. This is for the
sake of efficiency.
<P>
If the <tt>pop</tt> member functions were to return the element
that was removed then they would have to return it by value rather
than by reference. (The element is being removed, so there wouldn't
be anything for a reference to point to.) Return by value, however,
would be inefficient; it would involve at least one unnecessary copy
constructor invocation. The <tt>pop</tt> member functions return
nothing because it is impossible for them to return a value in a way
that is both correct and efficient.
<P>
If you need to retrieve the value and then remove it, you can perform
the two operations explicitly. For example:
<pre>
std::stack<T> s;
...
T old_value = s.top();
s.pop();
</pre>
<P><b>How do I sort a range in descending order instead of ascending?</b>
<pre>
sort(first, last, greater<T>());
</pre>
(Note that it must be <tt>greater</tt>, not <tt>greater_eq</tt>. The
comparison function <tt>f</tt> must be one such that <tt>f(x, x)</tt>
is <tt>false</tt> for every <tt>x</tt>.)
<P><b>Why am I getting uninitialized memory reads from Purify<FONT SIZE="-1"><SUP>TM</SUP></FONT>?</b>
<br>
We believe that the uninitialized memory read (UMR) messages in STL
data structures are artifacts and can be ignored.
<P>
There are a number of reasons the compiler might generate reads from
uninitialized memory (<i>e.g.</i> structure padding, inheritance from
empty base classes, which still have nonzero size). Purify tries to
deal with this by distinguishing between uninitialized memory reads
(UMR) and uninitialized memory copies (UMC). The latter are not
displayed by default.
The distinction between the two isn't completely clear, but appears to
be somewhat heuristic. The validity of the heuristic seems to depend
on compiler optimizations, etc. As a result, some perfectly
legitimate code generates UMR messages. It's unfortunately often hard
to tell whether a UMR message represents a genuine problem or just an
artifact.
<P><b>Why does Bounds Checker<FONT SIZE="-1"><SUP>TM</SUP></FONT> say that I have memory leaks?</b>
<br>
This is not an STL bug. It is an artifact of certain kinds of leak detectors.
<P>
In the default STL allocator, memory allocated for blocks of small
objects is not returned to <tt>malloc</tt>. It can only be reused by
subsequent <tt>allocate</tt> requests of (approximately) the same
size. Thus programs that use the default may appear to leak memory
when monitored by certain kinds of simple leak detectors. This is
intentional. Such "leaks" do not accumulate over time. Such
"leaks" are not reported by garbage-collector-like leak
detectors.
<P>
The primary design criterion for the default STL allocator was to make
it no slower than the HP STL per-class allocators, but potentially
thread-safe, and significantly less prone to fragmentation. Like the
HP allocators, it does not maintain the necessary data structures to
free entire chunks of small objects when none of the contained small
objects are in use. This is an intentional choice of execution time
over space use. It may not be appropriate for all programs. On many
systems <tt>malloc_alloc</tt> may be more space efficient, and can be
used when that is crucial.
<P>
The HP allocator design returned entire memory pools when the entire
allocator was no longer needed. To allow this, it maintains a count of
containers using a particular allocator. With the SGI design, this
would only happen when the last container disappears, which is
typically just before program exit. In most environments, this would
be highly counterproductive; <tt>free</tt> would typically have to
touch many long unreferenced pages just before the operating system
reclaims them anyway. It would often introduce a significant delay on
program exit, and would possibly page out large portions of other
applications. There is nothing to be gained by this action, since the
OS reclaims memory on program exit anyway, and it should do so
without touching that memory.
<p>
In general, we recommend that leak detection tests be run with
<tt>malloc_alloc</tt>. This yields more precise results with GC-based
detectors (<i>e.g.</i> Pure Atria's Purify<FONT SIZE="-1"><SUP>TM</SUP></FONT>),
and it provides useful results even with detectors that simply count
allocations and deallocations.
<br>
<!--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>
|
