1 <?xml version="1.0" encoding="ISO-8859-1"?>
3 PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
4 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
7 <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
8 <meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards)" />
9 <meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, libg++, STL" />
10 <meta name="DESCRIPTION" content="Notes for the libstdc++ extensions." />
11 <meta name="GENERATOR" content="vi and eight fingers" />
12 <title>libstdc++-v3 HOWTO: Extensions</title>
13 <link rel="StyleSheet" href="../lib3styles.css" />
17 <h1 class="centered"><a name="top">Extensions</a></h1>
19 <p>Here we will make an attempt at describing the non-Standard extensions to
20 the library. Some of these are from SGI's STL, some of these are GNU's,
21 and some just seemed to appear on the doorstep.
23 <p><strong>Before you leap in and use these</strong>, be aware of two things:
26 <li>Non-Standard means exactly that. The behavior, and the very
27 existence, of these extensions may change with little or no
28 warning. (Ideally, the really good ones will appear in the next
29 revision of C++.) Also, other platforms, other compilers, other
30 versions of g++ or libstdc++-v3 may not recognize these names, or
31 treat them differently, or... </li>
32 <li>You should know how to <a href="../faq/index.html#5_4">access
33 these headers properly</a>. </li>
37 <!-- ####################################################### -->
41 <li><a href="#1">Ropes and trees and hashes, oh my!</a></li>
42 <li><a href="#2">Added members and types</a></li>
43 <li><a href="#3">Allocators (versions 3.0, 3.1, 3.2)</a></li>
44 <li><a href="#6">Allocators (version 3.3)</a></li>
45 <li><a href="#4">Compile-time checks</a></li>
46 <li><a href="#5">LWG Issues</a></li>
51 <!-- ####################################################### -->
53 <h2><a name="1">Ropes and trees and hashes, oh my!</a></h2>
54 <p>The SGI headers</p>
63 <p>are all here; <code><bvector></code> exposes the old bit_vector
64 class that was used before specialization of vector<bool> was
65 available (it's actually a typedef for the specialization now).
66 <code><hash_map></code> and <code><hash_set></code>
67 are discussed further below. <code><rope></code> is the SGI
68 specialization for large strings ("rope," "large
69 strings," get it? love those SGI folks).
70 <code><slist></code> is a singly-linked list, for when the
71 doubly-linked <code>list<></code> is too much space overhead, and
72 <code><tree></code> exposes the red-black tree classes used in the
73 implementation of the standard maps and sets.
75 <p>Okay, about those hashing classes... I'm going to foist most of the
76 work off onto SGI's own site.
78 <p>Each of the associative containers map, multimap, set, and multiset
79 have a counterpart which uses a
80 <a href="http://www.sgi.com/Technology/STL/HashFunction.html">hashing
81 function</a> to do the arranging, instead of a strict weak ordering
82 function. The classes take as one of their template parameters a
83 function object that will return the hash value; by default, an
85 <a href="http://www.sgi.com/Technology/STL/hash.html">hash</a>.
86 You should specialize this functor for your class, or define your own,
87 before trying to use one of the hashing classes.
89 <p>The hashing classes support all the usual associative container
90 functions, as well as some extra constructors specifying the number
93 <p>Why would you want to use a hashing class instead of the
94 "normal" implementations? Matt Austern writes:
96 <blockquote><em>[W]ith a well chosen hash function, hash tables
97 generally provide much better average-case performance than binary
98 search trees, and much worse worst-case performance. So if your
99 implementation has hash_map, if you don't mind using nonstandard
100 components, and if you aren't scared about the possibility of
101 pathological cases, you'll probably get better performance from
102 hash_map.</em></blockquote>
103 <p>(Side note: for those of you wondering, <strong>"Why wasn't a hash
104 table included in the Standard in the first #!$@ place?"</strong>
105 I'll give a quick answer: it was proposed, but too late and in too
106 unorganized a fashion. Some sort of hashing will undoubtedly be
107 included in a future Standard.)
109 <p>Return <a href="#top">to top of page</a> or
110 <a href="../faq/index.html">to the FAQ</a>.
114 <h2><a name="2">Added members and types</a></h2>
115 <p>Some of the classes in the Standard Library have additional
116 publicly-available members, and some classes are themselves not in
117 the standard. Of those, some are intended purely for the implementors,
118 for example, additional typedefs. Those won't be described here
122 <li>The extensions added by SGI are so numerous that they have
123 <a href="sgiexts.html">their own page</a>. Since the SGI STL is no
124 longer actively maintained, we will try and keep this code working
126 <li>3.0.x <code>filebuf</code>s have another ctor with this signature:
128 <code>basic_filebuf(__c_file_type*, ios_base::openmode, int_type);</code>
129 <br />This comes in very handy in a number of places, such as
130 attaching Unix sockets, pipes, and anything else which uses file
131 descriptors, into the IOStream buffering classes. The three
132 arguments are as follows:
134 <li><code>__c_file_type* F </code>
135 // the __c_file_type typedef usually boils down to stdio's FILE
137 <li><code>ios_base::openmode M </code>
138 // same as all the other uses of openmode
140 <li><code>int_type B </code>
141 // buffer size, defaults to BUFSIZ if not specified
144 For those wanting to use file descriptors instead of FILE*'s, I
145 invite you to contemplate the mysteries of C's <code>fdopen()</code>.
147 <li>In library snapshot 3.0.95 and later, <code>filebuf</code>s bring
148 back an old extension: the <code>fd()</code> member function. The
149 integer returned from this function can be used for whatever file
150 descriptors can be used for on your platform. Naturally, the
151 library cannot track what you do on your own with a file descriptor,
152 so if you perform any I/O directly, don't expect the library to be
155 <li>Beginning with 3.1, the extra <code>filebuf</code> constructor and
156 the <code>fd()</code> function were removed from the standard
157 filebuf. Instead, <code><ext/stdio_filebuf.h></code> contains
158 a derived class called <code>__gnu_cxx::stdio_filebuf</code>.
161 <p>Return <a href="#top">to top of page</a> or
162 <a href="../faq/index.html">to the FAQ</a>.
166 <h2><a name="3">Allocators (versions 3.0, 3.1, 3.2)</a></h2>
167 <p>Thread-safety, space efficiency, high speed, portability... this is a
168 mess. Where to begin?
171 <p>The C++ standard only gives a few directives in this area:
174 <li>When you add elements to a container, and the container must allocate
175 more memory to hold them, the container makes the request via its
176 <code>Allocator</code> template parameter. This includes adding
177 char's to the string class, which acts as a regular STL container
180 <li>The default <code>Allocator</code> of every container-of-T is
181 <code>std::allocator<T></code>.
183 <li>The interface of the <code>allocator<T></code> class is
184 extremely simple. It has about 20 public declarations (nested
185 typedefs, member functions, etc), but the two which concern us most
188 T* allocate (size_type n, const void* hint = 0);
189 void deallocate (T* p, size_type n);</pre>
190 (This is a simplicifcation; the real signatures use nested typedefs.)
191 The <code>"n"</code> arguments in both those functions is a
192 <em>count</em> of the number of T's to allocate space for,
193 <em>not their total size</em>.
195 <li>"The storage is obtained by calling
196 <code>::operator new(size_t)</code>, but it is unspecified when or
197 how often this function is called. The use of <code>hint</code>
198 is unspecified, but intended as an aid to locality if an
199 implementation so desires." [20.4.1.1]/6
202 <h3>Problems and Possibilities</h3>
203 <p>The easiest way of fulfilling the requirements is to call operator new
204 each time a container needs memory, and to call operator delete each
205 time the container releases memory. <strong>BUT</strong>
206 <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00105.html">this
207 method is horribly slow</a>.
209 <p>Or we can keep old memory around, and reuse it in a pool to save time.
210 The old libstdc++-v2 used a memory pool, and so do we. As of 3.0,
211 <a href="http://gcc.gnu.org/ml/libstdc++/2001-05/msg00136.html">it's
212 on by default</a>. The pool is shared among all the containers in the
213 program: when your program's std::vector<int> gets cut in half
214 and frees a bunch of its storage, that memory can be reused by the
215 private std::list<WonkyWidget> brought in from a KDE library
216 that you linked against. And we don't have to call operators new and
217 delete to pass the memory on, either, which is a speed bonus.
218 <strong>BUT</strong>...
220 <p>What about threads? No problem: in a threadsafe environment, the
221 memory pool is manipulated atomically, so you can grow a container in
222 one thread and shrink it in another, etc. <strong>BUT</strong> what
223 if threads in libstdc++-v3 aren't set up properly?
224 <a href="../faq/index.html#5_6">That's been answered already</a>.
226 <p><strong>BUT</strong> what if you want to use your own allocator? What
227 if you plan on using a runtime-loadable version of malloc() which uses
228 shared telepathic anonymous mmap'd sections serializable over a
229 network, so that memory requests <em>should</em> go through malloc?
230 And what if you need to debug it?
234 <h3>Available allocators in namespace std</h3>
235 <p>First I'll describe the situation as it exists for the code which
236 was released in GCC 3.1 and 3.2. Then I'll describe the differences
237 for 3.0. The allocator classes also have source documentation,
238 which is described <a href="../documentation.html#4">here</a> (you
239 will need to retrieve the maintainer-level docs, as almost none of
240 these entities are in the ISO standard).
242 <p>As a general rule of thumb, users are not allowed to use names which
243 begin with an underscore. This means that to be portable between
244 compilers, none of the following may be used in your program directly.
245 (If you decide to be unportable, then you're free do do what you want,
246 but it's not our fault if stuff breaks.) They are presented here for
247 information for maintainers and contributors in addition to users.
249 <p>These classes are always available:
252 <li><code>__new_alloc</code> simply wraps <code>::operator new</code>
253 and <code>::operator delete</code>.
255 <li><code>__malloc_alloc_template<int inst></code> simply wraps
256 <code>malloc</code> and <code>free</code>. There is also a hook
257 for an out-of-memory handler (for new/delete this is taken care of
258 elsewhere). The <code>inst</code> parameter is described below.
259 This class was called <code>malloc_alloc</code> in earlier versions.
261 <li><code>allocator<T></code> has already been described; it is
262 The Standard Allocator for instances of T. It uses the internal
263 <code>__alloc</code> typedef (see below) to satisy its requests.
265 <li><code>__simple_alloc<T,A></code> is a wrapper around another
266 allocator, A, which itself is an allocator for instances of T.
267 This is primarily used in an internal "allocator traits"
268 class which helps encapsulate the different styles of allocators.
270 <li><code>__debug_alloc<A></code> is also a wrapper around an
271 arbitrary allocator A. It passes on slightly increased size
272 requests to A, and uses the extra memory to store size information.
273 When a pointer is passed to <code>deallocate()</code>, the stored
274 size is checked, and assert() is used to guarantee they match.
276 <li><code>__allocator<T,A></code> is an adaptor. Many of these
277 allocator classes have a consistent yet non-standard interface.
278 Such classes can be changed to a conforming interface with this
279 wrapper: <code>__allocator<T, __alloc></code> is thus the
280 same as <code>allocator<T></code>.
283 <p>An internal typedef, <code> __mem_interface </code>, is defined to be
284 <code>__new_alloc</code> by default.
287 <code> __default_alloc_template<bool thr, int inst> </code>
288 is also available. This is the high-speed pool, called the default
289 node allocator. The reusable memory is shared among identical
291 this type. It calls through <code>__mem_interface</code> to obtain
292 new memory when its lists run out. If a client container requests a
293 block larger than a certain threshold size, then the pool is bypassed,
294 and the allocate/deallocate request is passed to
295 <code>__mem_interface</code> directly.
297 <p>Its <code>inst</code> parameter is described below. The
298 <code>thr</code> boolean determines whether the pool should be
299 manipulated atomically or not. Two typedefs are provided:
300 <code>__alloc</code> is defined as this node allocator with thr=true,
301 and therefore is threadsafe, while <code>__single_client_alloc</code>
302 defines thr=false, and is slightly faster but unsafe for multiple
305 <p>(Note that the GCC thread abstraction layer allows us to provide safe
306 zero-overhead stubs for the threading routines, if threads were
307 disabled at configuration time. In this situation,
308 <code>__alloc</code> should not be noticably slower than
309 <code>__single_client_alloc</code>.)
311 <p>[Another threadsafe allocator where each thread keeps its own free
312 list, so that no locking is needed, might be described here.]
314 <h3>A cannon to swat a fly:<code> __USE_MALLOC</code></h3>
315 <p>If you've already read <a href="../23_containers/howto.html#3">this
316 advice</a> and decided to define this macro, then the situation changes
320 <li><code>__mem_interface</code>, and</li>
321 <li><code>__alloc</code>, and</li>
322 <li><code>__single_client_alloc</code> are all typedef'd to
323 <code>__malloc_alloc_template</code>.</li>
324 <li><code>__default_alloc_template</code> is no longer available.
325 At all. Anywhere.</li>
327 <h3>Writing your own allocators</h3>
328 <p>Depending on your application (a specific program, a generic library,
329 etc), allocator classes tend to be one of two styles: "SGI"
330 or "standard". See the comments in stl_alloc.h for more
331 information on this crucial difference.
333 <p>At the bottom of that header is a helper type,
334 <code>_Alloc_traits</code>, and various specializations of it. This
335 allows the container classes to make possible compile-time
336 optimizations based on features of the allocator. You should provide
337 a specialization of this type for your allocator (doing so takes only
338 two or three statements).
340 <h3>Using non-default allocators</h3>
341 <p>You can specify different memory management schemes on a per-container
342 basis, by overriding the default <code>Allocator</code> template
343 parameter. For example, an easy
345 method of specifying that only malloc/free should be used instead of
346 the default node allocator is:
349 std::list <my_type, std::__malloc_alloc_template<0> > my_malloc_based_list;</pre>
350 Likewise, a debugging form of whichever allocator is currently in use:
352 std::deque <my_type, std::__debug_alloc<std::__alloc> > debug_deque;</pre>
353 <h3><code>inst</code></h3>
354 <p>The <code>__malloc_alloc_template</code> and
355 <code>__default_alloc_template</code> classes take an integer parameter,
356 called inst here. This number is completely unused.
358 <p>The point of the number is to allow multiple instantiations of the
359 classes without changing the semantics at all. All three of
362 typedef __default_alloc_template<true,0> normal;
363 typedef __default_alloc_template<true,1> private;
364 typedef __default_alloc_template<true,42> also_private;</pre>
365 <p>behave exactly the same way. However, the memory pool for each type
366 (and remember that different instantiations result in different types)
369 <p>The library uses <strong>0</strong> in all its instantiations. If you
370 wish to keep separate free lists for a particular purpose, use a
374 <p>For 3.0.x, many of the names were incorrectly <em>not</em> prefixed
375 with underscores. So symbols such as "std::single_client_alloc"
376 are present. Be very careful to not depend on these names any more
377 than you would depend on implementation-only names.
379 <p>Certain macros like <code>_NOTHREADS</code> and <code>__STL_THREADS</code>
380 can affect the 3.0.x allocators. Do not use them. Those macros have
381 been completely removed for 3.1.
383 <p>Return <a href="#top">to top of page</a> or
384 <a href="../faq/index.html">to the FAQ</a>.
388 <h2><a name="6">Allocators (version 3.3)</a></h2>
389 <p>Changes are coming...
391 <p>Return <a href="#top">to top of page</a> or
392 <a href="../faq/index.html">to the FAQ</a>.
396 <h2><a name="4">Compile-time checks</a></h2>
397 <p>Currently libstdc++-v3 uses the concept checkers from the Boost
398 library to perform <a href="../19_diagnostics/howto.html#3">optional
399 compile-time checking</a> of template instantiations of the standard
400 containers. They are described in the linked-to page.
402 <p>Return <a href="#top">to top of page</a> or
403 <a href="../faq/index.html">to the FAQ</a>.
407 <h2><a name="5">LWG Issues</a></h2>
408 <p>Everybody's got issues. Even the C++ Standard Library.
410 <p>The Library Working Group, or LWG, is the ISO subcommittee responsible
411 for making changes to the library. They periodically publish an
412 Issues List containing problems and possible solutions. As they reach
413 a consensus on proposed solutions, we often incorporate the solution
416 <p>Here are the issues which have resulted in code changes to the library.
417 The links are to the specific defect reports from a <strong>partial
418 copy</strong> of the Issues List. You can read the full version online
419 at the <a href="http://www.dkuug.dk/jtc1/sc22/wg21/">ISO C++
420 Committee homepage</a>, linked to on the
421 <a href="http://gcc.gnu.org/readings.html">GCC "Readings"
423 you spend a lot of time reading the issues, we recommend downloading
424 the ZIP file and reading them locally.
426 <p>(NB: <strong>partial copy</strong> means that not all links within
427 the lwg-*.html pages will work.
428 Specifically, links to defect reports that have not been accorded full
429 DR status will probably break. Rather than trying to mirror the
430 entire issues list on our overworked web server, we recommend you go
431 to the LWG homepage instead.)
434 If a DR is not listed here, we may simply not have gotten to it yet;
435 feel free to submit a patch. Search the include/bits and src
436 directories for appearances of _GLIBCPP_RESOLVE_LIB_DEFECTS for
437 examples of style. Note that we usually do not make changes to the code
438 until an issue has reached <a href="lwg-active.html#DR">DR</a> status.
441 <dt><a href="lwg-defects.html#5">5</a>:
442 <em>string::compare specification questionable</em>
444 <dd>This should be two overloaded functions rather than a single function.
447 <dt><a href="lwg-defects.html#17">17</a>:
448 <em>Bad bool parsing</em>
450 <dd>Apparently extracting Boolean values was messed up...
453 <dt><a href="lwg-defects.html#22">22</a>:
454 <em>Member open vs flags</em>
456 <dd>Re-opening a file stream does <em>not</em> clear the state flags.
459 <dt><a href="lwg-defects.html#25">25</a>:
460 <em>String operator<< uses width() value wrong</em>
465 <dt><a href="lwg-defects.html#48">48</a>:
466 <em>Use of non-existent exception constructor</em>
468 <dd>An instance of <code>ios_base::failure</code> is constructed instead.
471 <dt><a href="lwg-defects.html#49">49</a>:
472 <em>Underspecification of ios_base::sync_with_stdio</em>
474 <dd>The return type is the <em>previous</em> state of synchronization.
477 <dt><a href="lwg-defects.html#50">50</a>:
478 <em>Copy constructor and assignment operator of ios_base</em>
480 <dd>These members functions are declared <code>private</code> and are
481 thus inaccessible. Specifying the correct semantics of
482 "copying stream state" was deemed too complicated.
485 <dt><a href="lwg-defects.html#68">68</a>:
486 <em>Extractors for char* should store null at end</em>
488 <dd>And they do now. An editing glitch in the last item in the list of
492 <dt><a href="lwg-defects.html#74">74</a>:
493 <em>Garbled text for codecvt::do_max_length</em>
495 <dd>The text of the standard was gibberish. Typos gone rampant.
498 <dt><a href="lwg-defects.html#83">83</a>:
499 <em>string::npos vs. string::max_size()</em>
501 <dd>Safety checks on the size of the string should test against
502 <code>max_size()</code> rather than <code>npos</code>.
505 <dt><a href="lwg-defects.html#109">109</a>:
506 <em>Missing binders for non-const sequence elements</em>
508 <dd>The <code>binder1st</code> and <code>binder2nd</code> didn't have an
509 <code>operator()</code> taking a non-const parameter.
512 <dt><a href="lwg-defects.html#110">110</a>:
513 <em>istreambuf_iterator::equal not const</em>
515 <dd>This was not a const member function. Note that the DR says to
516 replace the function with a const one; we have instead provided an
517 overloaded version with identical contents.
520 <dt><a href="lwg-defects.html#117">117</a>:
521 <em>basic_ostream uses nonexistent num_put member functions</em>
523 <dd><code>num_put::put()</code> was overloaded on the wrong types.
526 <dt><a href="lwg-defects.html#118">118</a>:
527 <em>basic_istream uses nonexistent num_get member functions</em>
529 <dd>Same as 117, but for <code>num_get::get()</code>.
532 <dt><a href="lwg-defects.html#129">129</a>:
533 <em>Need error indication from seekp() and seekg()</em>
535 <dd>These functions set <code>failbit</code> on error now.
538 <dt><a href="lwg-defects.html#136">136</a>:
539 <em>seekp, seekg setting wrong streams?</em>
541 <dd><code>seekp</code> should only set the output stream, and
542 <code>seekg</code> should only set the input stream.
545 <!--<dt><a href="lwg-defects.html#159">159</a>:
546 <em>Strange use of underflow()</em>
548 <dd>In fstream.tcc, the basic_filebuf<>::showmanyc() function
549 should probably not be calling <code>underflow()</code>.
552 <dt><a href="lwg-active.html#167">167</a>:
553 <em>Improper use of traits_type::length()</em>
555 <dd><code>op<<</code> with a <code>const char*</code> was
556 calculating an incorrect number of characters to write.
559 <dt><a href="lwg-defects.html#181">181</a>:
560 <em>make_pair() unintended behavior</em>
562 <dd>This function used to take its arguments as reference-to-const, now
563 it copies them (pass by value).
566 <dt><a href="lwg-defects.html#195">195</a>:
567 <em>Should basic_istream::sentry's constructor ever set eofbit?</em>
569 <dd>Yes, it can, specifically if EOF is reached while skipping whitespace.
572 <dt><a href="lwg-defects.html#211">211</a>:
573 <em>operator>>(istream&, string&) doesn't set failbit</em>
575 <dd>If nothing is extracted into the string, <code>op>></code> now
576 sets <code>failbit</code> (which can cause an exception, etc, etc).
579 <dt><a href="lwg-defects.html#214">214</a>:
580 <em>set::find() missing const overload</em>
582 <dd>Both <code>set</code> and <code>multiset</code> were missing
583 overloaded find, lower_bound, upper_bound, and equal_range functions
587 <dt><a href="lwg-defects.html#251">251</a>:
588 <em>basic_stringbuf missing allocator_type</em>
590 <dd>This nested typdef was originally not specified.
593 <dt><a href="lwg-defects.html#265">265</a>:
594 <em>std::pair::pair() effects overly restrictive</em>
596 <dd>The default ctor would build its members from copies of temporaries;
597 now it simply uses their respective default ctors.
600 <dt><a href="lwg-defects.html#266">266</a>:
601 <em>bad_exception::~bad_exception() missing Effects clause</em>
603 <dd>The <code>bad_</code>* classes no longer have destructors (they
604 are trivial), since no description of them was ever given.
607 <dt><a href="lwg-defects.html#275">275</a>:
608 <em>Wrong type in num_get::get() overloads</em>
614 <dt><a href="lwg-defects.html#"></a>:
622 <p>Return <a href="#top">to top of page</a> or
623 <a href="../faq/index.html">to the FAQ</a>.
627 <!-- ####################################################### -->
630 <p class="fineprint"><em>
631 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
632 Comments and suggestions are welcome, and may be sent to
633 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.