| blob | 55415affd959e9c01719e76761178a96b0834ab5 |
2 <!DOCTYPE html
3 PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
7 <head>
23 </head>
24 <body>
29 </p>
32 <!-- ####################################################### -->
33 <hr />
35 <ul>
43 </ul>
45 <hr />
47 <!-- ####################################################### -->
50 <p>You're writing some code and can't decide whether to use builtin
51 arrays or some kind of container. There are compelling reasons
52 to use one of the container classes, but you're afraid that you'll
53 eventually run into difficulties, change everything back to arrays,
54 and then have to change all the code that uses those data types to
55 keep up with the change.
56 </p>
57 <p>If your code makes use of the standard algorithms, this isn't as
58 scary as it sounds. The algorithms don't know, nor care, about
60 algorithms are only given endpoints to work with. For the container
63 the address of the first element and the
65 </p>
66 <p>Some very simple wrapper functions can hide all of that from the
67 rest of the code. For example, a pair of functions called
69 that takes a vector. The first returns a pointer to the first
71 iterator.
72 </p>
73 <p>The functions should be made template functions, and should also
74 be declared inline. As pointed out in the comments in the code
76 existence, so you pay absolutely nothing in terms of increased
77 code size or execution time.
78 </p>
79 <p>The result is that if all your algorithm calls look like
80 </p>
81 <pre>
82 std::transform(beginof(foo), endof(foo), beginof(foo), SomeFunction);</pre>
83 <p>then the type of foo can change from an array of ints to a vector
84 of ints to a deque of ints and back again, without ever changing any
85 client code.
86 </p>
89 with some Usenet discussions on a transparent way to find the length
90 of an array. A simplified and much-reduced version for easier
92 </p>
93 <p>Astute readers will notice two things at once: first, that the
98 getting template resolution correct; I find it easier just to
99 give the extra three lines and avoid confusion.
100 </p>
101 <p>Second, the line
102 </p>
103 <pre>
105 <p>looks just weird! Hint: unused parameters can be left nameless.
106 </p>
109 </p>
111 <hr />
113 <p>No, you cannot write code of the form
114 </p>
115 <!-- Careful, the leading spaces in PRE show up directly. -->
116 <pre>
119 void foo (size_t n)
120 {
122 ....
123 } </pre>
125 correct; it is not a bug. That's the way templates work. (Yes, it
127 </p>
128 <p>There are a couple of ways to handle this kind of thing. Please
129 consider all of them before passing judgement. They include, in
130 no particular order:
131 </p>
132 <ul>
136 </ul>
137 <p><strong>A very large N in
139 been pointed out a few times in newsgroups that N bits only takes up
140 (N/8) bytes on most systems, and division by a factor of eight is pretty
141 impressive when speaking of memory. Half a megabyte given over to a
142 bitset (recall that there is zero space overhead for housekeeping info;
143 it is known at compile time exactly how large the set is) will hold over
144 four million bits. If you're using those bits as status flags (e.g.,
146 of state.
147 </p>
149 testing runs on representative data, make note of how many of those bits
150 really need to be there, and then reduce N to a smaller number. Leave
151 some extra space, of course. (If you plan to write code like the
152 incorrect example above, where the bitset is a local variable, then you
153 may have to talk your compiler into allowing that much stack space;
154 there may be zero space overhead, but it's all allocated inside the
155 object.)
156 </p>
158 made provision
159 for the space savings possible with that (N/8) usage previously mentioned,
160 so that you don't have to do wasteful things like
164 specialized for that space savings.
165 </p>
167 normal vector anymore. There have been recent journal articles which
168 discuss the problems (the ones by Herb Sutter in the May and
169 July/August 1999 issues of
173 recommended (although its behavior is sane, you probably will not get
174 the space savings, but the allocation scheme is different than that
175 of vector).
176 </p>
178 access to
179 the compiler and linker at runtime, you can do something insane, like
180 figuring out just how many bits you need, then writing a temporary
181 source code file. That file contains an instantiation of
183 for the required number of bits, inside some wrapper functions with
184 unchanging signatures. Have your program then call the
185 compiler on that file using Position Independent Code, then open the
186 newly-created object file and load those wrapper functions. You'll have
189 that you need at the time. Don't forget to delete the temporary files.
191 </p>
192 <!-- I wonder if this next paragraph will get me in trouble... -->
193 <p>This would be the approach of either a visionary genius or a raving
194 lunatic, depending on your programming and management style. Probably
195 the latter.
196 </p>
197 <p>Which of the above techniques you use, if any, are up to you and your
198 intended application. Some time/space profiling is indicated if it
199 really matters (don't just guess). And, if you manage to do anything
200 along the lines of the third category, the author would love to hear
201 from you...
202 </p>
203 <p>Also note that the implementation of bitset used in libstdc++-v3 has
205 </p>
208 </p>
210 <hr />
212 <p>This section discusses issues surrounding the design of
213 multithreaded applications which use Standard C++ containers.
214 All information in this section is current as of the gcc 3.0
215 release and all later point releases. Although earlier gcc
216 releases had a different approach to threading configuration and
217 proper compilation, the basic code design rules presented here
218 were similar. For information on all other aspects of
219 multithreading as it relates to libstdc++, including details on
220 the proper compilation of threaded code (and compatibility between
221 threaded and non-threaded code), see Chapter 17.
222 </p>
223 <p>Two excellent pages to read when working with the Standard C++
224 containers and threads are
226 http://www.sgi.com/tech/stl/thread_safety.html</a> and
228 http://www.sgi.com/tech/stl/Allocators.html</a>.
229 </p>
230 <p><em>However, please ignore all discussions about the user-level
231 configuration of the lock implementation inside the STL
232 container-memory allocator on those pages. For the sake of this
233 discussion, libstdc++-v3 configures the SGI STL implementation,
234 not you. This is quite different from how gcc pre-3.0 worked.
235 In particular, past advice was for people using g++ to
236 explicitly define _PTHREADS or other macros or port-specific
237 compilation options on the command line to get a thread-safe
238 STL. This is no longer required for any port and should no
239 longer be done unless you really know what you are doing and
240 assume all responsibility.</em>
241 </p>
242 <p>Since the container implementation of libstdc++-v3 uses the SGI
243 code, we use the same definition of thread safety as SGI when
244 discussing design. A key point that beginners may miss is the
245 fourth major paragraph of the first page mentioned above
247 locking must nearly always be done outside the container, by
248 client code (that'd be you, not us). There is a notable
249 exceptions to this rule. Allocators called while a container or
250 element is constructed uses an internal lock obtained and
251 released solely within libstdc++-v3 code (in fact, this is the
252 reason STL requires any knowledge of the thread configuration).
253 </p>
254 <p>For implementing a container which does its own locking, it is
255 trivial to provide a wrapper class which obtains the lock (as
256 SGI suggests), performs the container operation, and then
257 releases the lock. This could be templatized <em>to a certain
258 extent</em>, on the underlying container and/or a locking
259 mechanism. Trying to provide a catch-all general template
260 solution would probably be more trouble than it's worth.
261 </p>
262 <p>The STL implementation is currently configured to use the
263 high-speed caching memory allocator. Some people like to
264 test and/or normally run threaded programs with a different
265 default. For all details about how to globally override this
267 </p>
268 <p>There is a better way (not standardized yet): It is possible to
269 force the malloc-based allocator on a per-case-basis for some
270 application code. The library team generally believes that this
271 is a better way to tune an application for high-speed using this
272 implementation of the STL. There is
274 </p>
277 </p>
279 <hr />
282 for all of the associative containers (map, set, etc):
283 </p>
284 <pre>
285 a.insert(p,t);</pre>
286 <p>where 'p' is an iterator into the container 'a', and 't' is the item
287 to insert. The standard says that "iterator p is a hint
288 pointing to where the insert should start to search," but
289 specifies nothing more. (LWG Issue #233, currently in review,
290 addresses this topic, but I will ignore it here because it is not yet
291 finalized.)
292 </p>
293 <p>Here we'll describe how the hinting works in the libstdc++-v3
294 implementation, and what you need to do in order to take advantage of
295 it. (Insertions can change from logarithmic complexity to amortized
296 constant time, if the hint is properly used.) Also, since the current
297 implementation is based on the SGI STL one, these points may hold true
298 for other library implementations also, since the HP/SGI code is used
299 in a lot of places.
300 </p>
302 than</em> refer to the results of the strict weak ordering imposed on
303 the container by its comparison object, which defaults to (basically)
304 "<". Using those phrases is semantically sloppy, but I
305 didn't want to get bogged down in syntax. I assume that if you are
306 intelligent enough to use your own comparison objects, you are also
308 their new meanings in the next paragraph. *grin*
309 </p>
311 </p>
312 <ul>
314 less than all the other keys in the container. The item will
315 be inserted at the beginning of the container, becoming the new
317 </li>
319 greater than all the other keys in the container. The item will
320 be inserted at the end of the container, becoming the new entry
322 </li>
329 </li>
330 </ul>
335 greater-than-or-equal-to? You probably could in your head, but the
336 mathematicians will tell you that it isn't the same thing.)
337 </p>
338 <p>If the conditions are not met, then the hint is not used, and the
343 argument in those releases.)
344 </p>
346 functions which take an iterator: if used, the new item will be
347 inserted before the iterator passed as an argument, same as the other
348 containers. The exception
352 </p>
354 one-shot. The insertion-with-hint routines check the immediately
355 surrounding entries to ensure that the new item would in fact belong
356 there. If the hint does not point to the correct place, then no
357 further local searching is done; the search begins from scratch in
358 logarithmic time. (Further local searching would only increase the
359 time required when the hint is too far off.)
360 </p>
363 </p>
365 <hr />
367 <p>Bitmasks do not take char* nor const char* arguments in their
368 constructors. This is something of an accident, but you can read
371 link, select the library issues list. Issue number 116 describes the
372 problem.
373 </p>
374 <p>For now you can simply make a temporary string object using the
375 constructor expression:
376 </p>
377 <pre>
379 </pre>
380 instead of
381 <pre>
383 </pre>
386 </p>
388 <hr />
390 <p>Yes it is, and that's okay. This is a decision that we preserved when
391 we imported SGI's STL implementation. The following is quoted from
393 </p>
394 <blockquote>
395 <p>The size() member function, for list and slist, takes time
396 proportional to the number of elements in the list. This was a
397 deliberate tradeoff. The only way to get a constant-time size() for
398 linked lists would be to maintain an extra member variable containing
399 the list's size. This would require taking extra time to update that
400 variable (it would make splice() a linear time operation, for example),
401 and it would also make the list larger. Many list algorithms don't
402 require that extra word (algorithms that do require it might do better
403 with vectors than with lists), and, when it is necessary to maintain
404 an explicit size count, it's something that users can do themselves.
405 </p>
406 <p>This choice is permitted by the C++ standard. The standard says that
409 officially recommended ISO wording for saying that an implementation
410 is supposed to do something unless there is a good reason not to.
411 </p>
412 <p>One implication of linear time size(): you should never write
413 </p>
414 <pre>
415 if (L.size() == 0)
416 ...</pre>
417 Instead, you should write
418 <pre>
419 if (L.empty())
420 ...</pre>
421 </blockquote>
424 </p>
426 <hr />
428 <p>In
430 message to the list</a>, Daniel Kostecky announced work on an
432 on the number of elements to be over-allocated. The design was also
433 described, along with possible implementation choices.
434 </p>
435 <p>The first two alpha releases were announced
437 and
439 The releases themselves are available at
441 http://www.kotelna.sk/dk/sw/caphint/</a>.
442 </p>
445 </p>
448 <!-- ####################################################### -->
450 <hr />
453 Comments and suggestions are welcome, and may be sent to
455 </em></p>
458 </body>
459 </html>