OSDN Git Service

331f1408a35c690832d0bba55c14e34cbf466b4f
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / xml / manual / appendix_contributing.xml
1 <?xml version='1.0'?>
2 <!DOCTYPE appendix PUBLIC "-//OASIS//DTD DocBook XML V4.5//EN"
3  "http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
4 [ ]>
5
6 <appendix id="appendix.contrib" xreflabel="Contributing">
7 <?dbhtml filename="appendix_contributing.html"?>
8
9 <appendixinfo>
10   <keywordset>
11     <keyword>
12       ISO C++
13     </keyword>
14     <keyword>
15       library
16     </keyword>
17   </keywordset>
18 </appendixinfo>
19
20 <title>
21   Contributing
22   <indexterm>
23     <primary>Appendix</primary>
24     <secondary>Contributing</secondary>
25   </indexterm>
26 </title>
27
28 <para>
29   The GNU C++ Library follows an open development model. Active
30   contributors are assigned maintainer-ship responsibility, and given
31   write access to the source repository. First time contributors
32   should follow this procedure:
33 </para>
34
35 <sect1 id="contrib.list" xreflabel="Contributor Checklist">
36   <title>Contributor Checklist</title>
37
38   <sect2 id="list.reading">
39     <title>Reading</title>
40
41     <itemizedlist>
42       <listitem>
43         <para>
44           Get and read the relevant sections of the C++ language
45           specification. Copies of the full ISO 14882 standard are
46           available on line via the ISO mirror site for committee
47           members. Non-members, or those who have not paid for the
48           privilege of sitting on the committee and sustained their
49           two meeting commitment for voting rights, may get a copy of
50           the standard from their respective national standards
51           organization. In the USA, this national standards
52           organization is ANSI and their web-site is right
53           <ulink url="http://www.ansi.org">here.</ulink>
54           (And if you've already registered with them, clicking this link will take you to directly to the place where you can
55           <ulink url="http://webstore.ansi.org/RecordDetail.aspx?sku=ISO%2FIEC+14882:2003">buy the standard on-line.)</ulink>
56         </para>
57       </listitem>
58
59       <listitem>
60         <para>
61           The library working group bugs, and known defects, can
62           be obtained here:
63           <ulink url="http://www.open-std.org/jtc1/sc22/wg21/">http://www.open-std.org/jtc1/sc22/wg21 </ulink>
64         </para>
65       </listitem>
66
67       <listitem>
68         <para>
69           The newsgroup dedicated to standardization issues is
70           comp.std.c++: this FAQ for this group is quite useful and
71           can be
72           found <ulink url="http://www.comeaucomputing.com/csc/faq.html">
73           here </ulink>.
74       </para>
75       </listitem>
76
77       <listitem>
78         <para>
79           Peruse
80           the <ulink url="http://www.gnu.org/prep/standards">GNU
81           Coding Standards</ulink>, and chuckle when you hit the part
82           about <quote>Using Languages Other Than C</quote>.
83         </para>
84       </listitem>
85
86       <listitem>
87         <para>
88           Be familiar with the extensions that preceded these
89           general GNU rules. These style issues for libstdc++ can be
90           found <link linkend="contrib.coding_style">here</link>.
91       </para>
92       </listitem>
93
94       <listitem>
95         <para>
96           And last but certainly not least, read the
97           library-specific information
98           found <link linkend="appendix.porting"> here</link>.
99       </para>
100       </listitem>
101     </itemizedlist>
102
103   </sect2>
104   <sect2 id="list.copyright">
105     <title>Assignment</title>
106     <para>
107       Small changes can be accepted without a copyright assignment form on
108       file. New code and additions to the library need completed copyright
109       assignment form on file at the FSF. Note: your employer may be required
110       to fill out appropriate disclaimer forms as well.
111     </para>
112
113     <para>
114       Historically, the libstdc++ assignment form added the following
115       question:
116     </para>
117
118     <para>
119       <quote>
120         Which Belgian comic book character is better, Tintin or Asterix, and
121         why?
122       </quote>
123     </para>
124
125     <para>
126       While not strictly necessary, humoring the maintainers and answering
127       this question would be appreciated.
128     </para>
129
130     <para>
131       For more information about getting a copyright assignment, please see
132       <ulink url="http://www.gnu.org/prep/maintain/html_node/Legal-Matters.html">Legal
133         Matters</ulink>.
134     </para>
135
136     <para>
137       Please contact Benjamin Kosnik at
138       <email>bkoz+assign@redhat.com</email> if you are confused
139       about the assignment or have general licensing questions. When
140       requesting an assignment form from
141       <email>mailto:assign@gnu.org</email>, please cc the libstdc++
142       maintainer above so that progress can be monitored.
143     </para>
144   </sect2>
145
146   <sect2 id="list.getting">
147     <title>Getting Sources</title>
148     <para>
149       <ulink url="http://gcc.gnu.org/svnwrite.html">Getting write access
150         (look for &quot;Write after approval&quot;)</ulink>
151     </para>
152   </sect2>
153
154   <sect2 id="list.patches">
155     <title>Submitting Patches</title>
156
157     <para>
158       Every patch must have several pieces of information before it can be
159       properly evaluated. Ideally (and to ensure the fastest possible
160       response from the maintainers) it would have all of these pieces:
161     </para>
162
163     <itemizedlist>
164       <listitem>
165         <para>
166           A description of the bug and how your patch fixes this
167           bug. For new features a description of the feature and your
168           implementation.
169         </para>
170       </listitem>
171
172       <listitem>
173         <para>
174           A ChangeLog entry as plain text; see the various
175           ChangeLog files for format and content. If you are
176           using emacs as your editor, simply position the insertion
177           point at the beginning of your change and hit CX-4a to bring
178           up the appropriate ChangeLog entry. See--magic! Similar
179           functionality also exists for vi.
180         </para>
181       </listitem>
182
183       <listitem>
184         <para>
185           A testsuite submission or sample program that will
186           easily and simply show the existing error or test new
187           functionality.
188         </para>
189       </listitem>
190
191       <listitem>
192         <para>
193           The patch itself. If you are accessing the SVN
194           repository use <command>svn update; svn diff NEW</command>;
195           else, use <command>diff -cp OLD NEW</command> ... If your
196           version of diff does not support these options, then get the
197           latest version of GNU
198           diff. The <ulink url="http://gcc.gnu.org/wiki/SvnTricks">SVN
199           Tricks</ulink> wiki page has information on customising the
200           output of <code>svn diff</code>.
201         </para>
202       </listitem>
203
204       <listitem>
205         <para>
206           When you have all these pieces, bundle them up in a
207           mail message and send it to libstdc++@gcc.gnu.org. All
208           patches and related discussion should be sent to the
209           libstdc++ mailing list.
210         </para>
211       </listitem>
212     </itemizedlist>
213
214   </sect2>
215
216 </sect1>
217
218 <sect1 id="contrib.organization" xreflabel="Source Organization">
219   <?dbhtml filename="source_organization.html"?>
220   <title>Directory Layout and Source Conventions</title>
221
222   <para>
223     The unpacked source directory of libstdc++ contains the files
224     needed to create the GNU C++ Library.
225   </para>
226
227   <literallayout>
228 It has subdirectories:
229
230   doc
231     Files in HTML and text format that document usage, quirks of the
232     implementation, and contributor checklists.
233
234   include
235     All header files for the C++ library are within this directory,
236     modulo specific runtime-related files that are in the libsupc++
237     directory.
238
239     include/std
240       Files meant to be found by #include &lt;name&gt; directives in
241       standard-conforming user programs.
242
243     include/c
244       Headers intended to directly include standard C headers.
245       [NB: this can be enabled via --enable-cheaders=c]
246
247     include/c_global
248       Headers intended to include standard C headers in
249       the global namespace, and put select names into the std::
250       namespace.  [NB: this is the default, and is the same as
251       --enable-cheaders=c_global]
252
253     include/c_std
254       Headers intended to include standard C headers
255       already in namespace std, and put select names into the std::
256       namespace.  [NB: this is the same as --enable-cheaders=c_std]
257
258     include/bits
259       Files included by standard headers and by other files in
260       the bits directory.
261
262     include/backward
263       Headers provided for backward compatibility, such as &lt;iostream.h&gt;.
264       They are not used in this library.
265
266     include/ext
267       Headers that define extensions to the standard library.  No
268       standard header refers to any of them.
269
270   scripts
271     Scripts that are used during the configure, build, make, or test
272     process.
273
274   src
275     Files that are used in constructing the library, but are not
276     installed.
277
278   testsuites/[backward, demangle, ext, performance, thread, 17_* to 27_*]
279     Test programs are here, and may be used to begin to exercise the
280     library.  Support for "make check" and "make check-install" is
281     complete, and runs through all the subdirectories here when this
282     command is issued from the build directory.  Please note that
283     "make check" requires DejaGNU 1.4 or later to be installed.  Please
284     note that "make check-script" calls the script mkcheck, which
285     requires bash, and which may need the paths to bash adjusted to
286     work properly, as /bin/bash is assumed.
287
288 Other subdirectories contain variant versions of certain files
289 that are meant to be copied or linked by the configure script.
290 Currently these are:
291
292   config/abi
293   config/cpu
294   config/io
295   config/locale
296   config/os
297
298 In addition, a subdirectory holds the convenience library libsupc++.
299
300   libsupc++
301     Contains the runtime library for C++, including exception
302     handling and memory allocation and deallocation, RTTI, terminate
303     handlers, etc.
304
305 Note that glibc also has a bits/ subdirectory.  We will either
306 need to be careful not to collide with names in its bits/
307 directory; or rename bits to (e.g.) cppbits/.
308
309 In files throughout the system, lines marked with an "XXX" indicate
310 a bug or incompletely-implemented feature.  Lines marked "XXX MT"
311 indicate a place that may require attention for multi-thread safety.
312   </literallayout>
313
314 </sect1>
315
316 <sect1 id="contrib.coding_style" xreflabel="Coding Style">
317   <?dbhtml filename="source_code_style.html"?>
318   <title>Coding Style</title>
319   <para>
320   </para>
321   <sect2 id="coding_style.bad_identifiers">
322     <title>Bad Identifiers</title>
323     <para>
324       Identifiers that conflict and should be avoided.
325     </para>
326
327     <literallayout>
328       This is the list of names <quote>reserved to the
329       implementation</quote> that have been claimed by certain
330       compilers and system headers of interest, and should not be used
331       in the library. It will grow, of course.  We generally are
332       interested in names that are not all-caps, except for those like
333       "_T"
334
335       For Solaris:
336       _B
337       _C
338       _L
339       _N
340       _P
341       _S
342       _U
343       _X
344       _E1
345       ..
346       _E24
347
348       Irix adds:
349       _A
350       _G
351
352       MS adds:
353       _T
354
355       BSD adds:
356       __used
357       __unused
358       __inline
359       _Complex
360       __istype
361       __maskrune
362       __tolower
363       __toupper
364       __wchar_t
365       __wint_t
366       _res
367       _res_ext
368       __tg_*
369
370       SPU adds:
371       __ea
372
373       For GCC:
374
375       [Note that this list is out of date. It applies to the old
376       name-mangling; in G++ 3.0 and higher a different name-mangling is
377       used. In addition, many of the bugs relating to G++ interpreting
378       these names as operators have been fixed.]
379
380       The full set of __* identifiers (combined from gcc/cp/lex.c and
381       gcc/cplus-dem.c) that are either old or new, but are definitely
382       recognized by the demangler, is:
383
384       __aa
385       __aad
386       __ad
387       __addr
388       __adv
389       __aer
390       __als
391       __alshift
392       __amd
393       __ami
394       __aml
395       __amu
396       __aor
397       __apl
398       __array
399       __ars
400       __arshift
401       __as
402       __bit_and
403       __bit_ior
404       __bit_not
405       __bit_xor
406       __call
407       __cl
408       __cm
409       __cn
410       __co
411       __component
412       __compound
413       __cond
414       __convert
415       __delete
416       __dl
417       __dv
418       __eq
419       __er
420       __ge
421       __gt
422       __indirect
423       __le
424       __ls
425       __lt
426       __max
427       __md
428       __method_call
429       __mi
430       __min
431       __minus
432       __ml
433       __mm
434       __mn
435       __mult
436       __mx
437       __ne
438       __negate
439       __new
440       __nop
441       __nt
442       __nw
443       __oo
444       __op
445       __or
446       __pl
447       __plus
448       __postdecrement
449       __postincrement
450       __pp
451       __pt
452       __rf
453       __rm
454       __rs
455       __sz
456       __trunc_div
457       __trunc_mod
458       __truth_andif
459       __truth_not
460       __truth_orif
461       __vc
462       __vd
463       __vn
464
465       SGI badnames:
466       __builtin_alloca
467       __builtin_fsqrt
468       __builtin_sqrt
469       __builtin_fabs
470       __builtin_dabs
471       __builtin_cast_f2i
472       __builtin_cast_i2f
473       __builtin_cast_d2ll
474       __builtin_cast_ll2d
475       __builtin_copy_dhi2i
476       __builtin_copy_i2dhi
477       __builtin_copy_dlo2i
478       __builtin_copy_i2dlo
479       __add_and_fetch
480       __sub_and_fetch
481       __or_and_fetch
482       __xor_and_fetch
483       __and_and_fetch
484       __nand_and_fetch
485       __mpy_and_fetch
486       __min_and_fetch
487       __max_and_fetch
488       __fetch_and_add
489       __fetch_and_sub
490       __fetch_and_or
491       __fetch_and_xor
492       __fetch_and_and
493       __fetch_and_nand
494       __fetch_and_mpy
495       __fetch_and_min
496       __fetch_and_max
497       __lock_test_and_set
498       __lock_release
499       __lock_acquire
500       __compare_and_swap
501       __synchronize
502       __high_multiply
503       __unix
504       __sgi
505       __linux__
506       __i386__
507       __i486__
508       __cplusplus
509       __embedded_cplusplus
510       // long double conversion members mangled as __opr
511       // http://gcc.gnu.org/ml/libstdc++/1999-q4/msg00060.html
512       _opr
513     </literallayout>
514   </sect2>
515
516   <sect2 id="coding_style.example">
517     <title>By Example</title>
518     <literallayout>
519       This library is written to appropriate C++ coding standards. As such,
520       it is intended to precede the recommendations of the GNU Coding
521       Standard, which can be referenced in full here:
522
523       http://www.gnu.org/prep/standards/standards.html#Formatting
524
525       The rest of this is also interesting reading, but skip the "Design
526       Advice" part.
527
528       The GCC coding conventions are here, and are also useful:
529       http://gcc.gnu.org/codingconventions.html
530
531       In addition, because it doesn't seem to be stated explicitly anywhere
532       else, there is an 80 column source limit.
533
534       ChangeLog entries for member functions should use the
535       classname::member function name syntax as follows:
536
537       1999-04-15  Dennis Ritchie  &lt;dr@att.com&gt;
538
539       * src/basic_file.cc (__basic_file::open): Fix thinko in
540       _G_HAVE_IO_FILE_OPEN bits.
541
542       Notable areas of divergence from what may be previous local practice
543       (particularly for GNU C) include:
544
545       01. Pointers and references
546       char* p = "flop";
547       char&amp; c = *p;
548       -NOT-
549       char *p = "flop";  // wrong
550       char &amp;c = *p;      // wrong
551
552       Reason: In C++, definitions are mixed with executable code. Here,
553       p is being initialized, not *p. This is near-universal
554       practice among C++ programmers; it is normal for C hackers
555       to switch spontaneously as they gain experience.
556
557       02. Operator names and parentheses
558       operator==(type)
559       -NOT-
560       operator == (type)  // wrong
561
562       Reason: The == is part of the function name. Separating
563       it makes the declaration look like an expression.
564
565       03. Function names and parentheses
566       void mangle()
567       -NOT-
568       void mangle ()  // wrong
569
570       Reason: no space before parentheses (except after a control-flow
571       keyword) is near-universal practice for C++. It identifies the
572       parentheses as the function-call operator or declarator, as
573       opposed to an expression or other overloaded use of parentheses.
574
575       04. Template function indentation
576       template&lt;typename T&gt;
577       void
578       template_function(args)
579       { }
580       -NOT-
581       template&lt;class T&gt;
582       void template_function(args) {};
583
584       Reason: In class definitions, without indentation whitespace is
585       needed both above and below the declaration to distinguish
586       it visually from other members. (Also, re: "typename"
587       rather than "class".)  T often could be int, which is
588       not a class. ("class", here, is an anachronism.)
589
590       05. Template class indentation
591       template&lt;typename _CharT, typename _Traits&gt;
592       class basic_ios : public ios_base
593       {
594       public:
595       // Types:
596       };
597       -NOT-
598       template&lt;class _CharT, class _Traits&gt;
599       class basic_ios : public ios_base
600       {
601       public:
602       // Types:
603       };
604       -NOT-
605       template&lt;class _CharT, class _Traits&gt;
606       class basic_ios : public ios_base
607       {
608       public:
609       // Types:
610       };
611
612       06. Enumerators
613       enum
614       {
615       space = _ISspace,
616       print = _ISprint,
617       cntrl = _IScntrl
618       };
619       -NOT-
620       enum { space = _ISspace, print = _ISprint, cntrl = _IScntrl };
621
622       07. Member initialization lists
623       All one line, separate from class name.
624
625       gribble::gribble()
626       : _M_private_data(0), _M_more_stuff(0), _M_helper(0);
627       { }
628       -NOT-
629       gribble::gribble() : _M_private_data(0), _M_more_stuff(0), _M_helper(0);
630       { }
631
632       08. Try/Catch blocks
633       try
634       {
635       //
636       }
637       catch (...)
638       {
639       //
640       }
641       -NOT-
642       try {
643       //
644       } catch(...) {
645       //
646       }
647
648       09. Member functions declarations and definitions
649       Keywords such as extern, static, export, explicit, inline, etc
650       go on the line above the function name. Thus
651
652       virtual int
653       foo()
654       -NOT-
655       virtual int foo()
656
657       Reason: GNU coding conventions dictate return types for functions
658       are on a separate line than the function name and parameter list
659       for definitions. For C++, where we have member functions that can
660       be either inline definitions or declarations, keeping to this
661       standard allows all member function names for a given class to be
662       aligned to the same margin, increasing readability.
663
664
665       10. Invocation of member functions with "this-&gt;"
666       For non-uglified names, use this-&gt;name to call the function.
667
668       this-&gt;sync()
669       -NOT-
670       sync()
671
672       Reason: Koenig lookup.
673
674       11. Namespaces
675       namespace std
676       {
677       blah blah blah;
678       } // namespace std
679
680       -NOT-
681
682       namespace std {
683       blah blah blah;
684       } // namespace std
685
686       12. Spacing under protected and private in class declarations:
687       space above, none below
688       i.e.
689
690       public:
691       int foo;
692
693       -NOT-
694       public:
695
696       int foo;
697
698       13. Spacing WRT return statements.
699       no extra spacing before returns, no parenthesis
700       i.e.
701
702       }
703       return __ret;
704
705       -NOT-
706       }
707
708       return __ret;
709
710       -NOT-
711
712       }
713       return (__ret);
714
715
716       14. Location of global variables.
717       All global variables of class type, whether in the "user visible"
718       space (e.g., cin) or the implementation namespace, must be defined
719       as a character array with the appropriate alignment and then later
720       re-initialized to the correct value.
721
722       This is due to startup issues on certain platforms, such as AIX.
723       For more explanation and examples, see src/globals.cc. All such
724       variables should be contained in that file, for simplicity.
725
726       15. Exception abstractions
727       Use the exception abstractions found in functexcept.h, which allow
728       C++ programmers to use this library with -fno-exceptions. (Even if
729       that is rarely advisable, it's a necessary evil for backwards
730       compatibility.)
731
732       16. Exception error messages
733       All start with the name of the function where the exception is
734       thrown, and then (optional) descriptive text is added. Example:
735
736       __throw_logic_error(__N("basic_string::_S_construct NULL not valid"));
737
738       Reason: The verbose terminate handler prints out exception::what(),
739       as well as the typeinfo for the thrown exception. As this is the
740       default terminate handler, by putting location info into the
741       exception string, a very useful error message is printed out for
742       uncaught exceptions. So useful, in fact, that non-programmers can
743       give useful error messages, and programmers can intelligently
744       speculate what went wrong without even using a debugger.
745
746       17. The doxygen style guide to comments is a separate document,
747       see index.
748
749       The library currently has a mixture of GNU-C and modern C++ coding
750       styles. The GNU C usages will be combed out gradually.
751
752       Name patterns:
753
754       For nonstandard names appearing in Standard headers, we are constrained
755       to use names that begin with underscores. This is called "uglification".
756       The convention is:
757
758       Local and argument names:  __[a-z].*
759
760       Examples:  __count  __ix  __s1
761
762       Type names and template formal-argument names: _[A-Z][^_].*
763
764       Examples:  _Helper  _CharT  _N
765
766       Member data and function names: _M_.*
767
768       Examples:  _M_num_elements  _M_initialize ()
769
770       Static data members, constants, and enumerations: _S_.*
771
772       Examples: _S_max_elements  _S_default_value
773
774       Don't use names in the same scope that differ only in the prefix,
775       e.g. _S_top and _M_top. See BADNAMES for a list of forbidden names.
776       (The most tempting of these seem to be and "_T" and "__sz".)
777
778       Names must never have "__" internally; it would confuse name
779       unmanglers on some targets. Also, never use "__[0-9]", same reason.
780
781       --------------------------
782
783       [BY EXAMPLE]
784
785       #ifndef  _HEADER_
786       #define  _HEADER_ 1
787
788       namespace std
789       {
790       class gribble
791       {
792       public:
793       gribble() throw();
794
795       gribble(const gribble&amp;);
796
797       explicit
798       gribble(int __howmany);
799
800       gribble&amp;
801       operator=(const gribble&amp;);
802
803       virtual
804       ~gribble() throw ();
805
806       // Start with a capital letter, end with a period.
807       inline void
808       public_member(const char* __arg) const;
809
810       // In-class function definitions should be restricted to one-liners.
811       int
812       one_line() { return 0 }
813
814       int
815       two_lines(const char* arg)
816       { return strchr(arg, 'a'); }
817
818       inline int
819       three_lines();  // inline, but defined below.
820
821       // Note indentation.
822       template&lt;typename _Formal_argument&gt;
823       void
824       public_template() const throw();
825
826       template&lt;typename _Iterator&gt;
827       void
828       other_template();
829
830       private:
831       class _Helper;
832
833       int _M_private_data;
834       int _M_more_stuff;
835       _Helper* _M_helper;
836       int _M_private_function();
837
838       enum _Enum
839       {
840       _S_one,
841       _S_two
842       };
843
844       static void
845       _S_initialize_library();
846       };
847
848       // More-or-less-standard language features described by lack, not presence.
849       # ifndef _G_NO_LONGLONG
850       extern long long _G_global_with_a_good_long_name;  // avoid globals!
851       # endif
852
853       // Avoid in-class inline definitions, define separately;
854       // likewise for member class definitions:
855       inline int
856       gribble::public_member() const
857       { int __local = 0; return __local; }
858
859       class gribble::_Helper
860       {
861       int _M_stuff;
862
863       friend class gribble;
864       };
865       }
866
867       // Names beginning with "__": only for arguments and
868       //   local variables; never use "__" in a type name, or
869       //   within any name; never use "__[0-9]".
870
871       #endif /* _HEADER_ */
872
873
874       namespace std
875       {
876       template&lt;typename T&gt;  // notice: "typename", not "class", no space
877       long_return_value_type&lt;with_many, args&gt;
878       function_name(char* pointer,               // "char *pointer" is wrong.
879       char* argument,
880       const Reference&amp; ref)
881       {
882       // int a_local;  /* wrong; see below. */
883       if (test)
884       {
885       nested code
886       }
887
888       int a_local = 0;  // declare variable at first use.
889
890       //  char a, b, *p;   /* wrong */
891       char a = 'a';
892       char b = a + 1;
893       char* c = "abc";  // each variable goes on its own line, always.
894
895       // except maybe here...
896       for (unsigned i = 0, mask = 1; mask; ++i, mask &lt;&lt;= 1) {
897       // ...
898       }
899       }
900
901       gribble::gribble()
902       : _M_private_data(0), _M_more_stuff(0), _M_helper(0);
903       { }
904
905       inline int
906       gribble::three_lines()
907       {
908       // doesn't fit in one line.
909       }
910       } // namespace std
911     </literallayout>
912   </sect2>
913 </sect1>
914
915 <sect1 id="contrib.doc_style" xreflabel="Documentation Style">
916   <?dbhtml filename="documentation_style.html"?>
917   <title>Documentation Style</title>
918   <sect2 id="doc_style.doxygen">
919     <title>Doxygen</title>
920     <sect3 id="doxygen.prereq">
921       <title>Prerequisites</title>
922       <para>
923         Prerequisite tools are Bash 2.x,
924         <ulink url="http://www.doxygen.org/">Doxygen</ulink>, and
925         the <ulink url="http://www.gnu.org/software/coreutils/">GNU
926         coreutils</ulink>. (GNU versions of find, xargs, and possibly
927         sed and grep are used, just because the GNU versions make
928         things very easy.)
929       </para>
930
931       <para>
932         To generate the pretty pictures and hierarchy
933         graphs, the
934         <ulink url="http://www.graphviz.org">Graphviz</ulink>
935         package will need to be installed.
936       </para>
937     </sect3>
938
939     <sect3 id="doxygen.rules">
940       <title>Generating the Doxygen Files</title>
941       <para>
942         The following Makefile rules run Doxygen to generate HTML
943         docs, XML docs, and the man pages.
944       </para>
945
946       <para>
947       <screen><userinput>make doc-html-doxygen</userinput></screen>
948       </para>
949
950       <para>
951       <screen><userinput>make doc-xml-doxygen</userinput></screen>
952       </para>
953
954       <para>
955       <screen><userinput>make doc-man-doxygen</userinput></screen>
956       </para>
957
958       <para>
959         Careful observers will see that the Makefile rules simply call
960         a script from the source tree, <filename>run_doxygen</filename>, which
961         does the actual work of running Doxygen and then (most
962         importantly) massaging the output files. If for some reason
963         you prefer to not go through the Makefile, you can call this
964         script directly. (Start by passing <literal>--help</literal>.)
965       </para>
966
967       <para>
968         If you wish to tweak the Doxygen settings, do so by editing
969         <filename>doc/doxygen/user.cfg.in</filename>. Notes to fellow
970         library hackers are written in triple-# comments.
971       </para>
972
973     </sect3>
974
975     <sect3 id="doxygen.markup">
976       <title>Markup</title>
977
978       <para>
979         In general, libstdc++ files should be formatted according to
980         the rules found in the
981         <link linkend="contrib.coding_style">Coding Standard</link>. Before
982         any doxygen-specific formatting tweaks are made, please try to
983         make sure that the initial formatting is sound.
984       </para>
985
986       <para>
987         Adding Doxygen markup to a file (informally called
988         <quote>doxygenating</quote>) is very simple. The Doxygen manual can be
989         found
990         <ulink url="http://www.stack.nl/~dimitri/doxygen/download.html#latestman">here</ulink>.
991         We try to use a very-recent version of Doxygen.
992       </para>
993
994       <para>
995         For classes, use
996         <classname>deque</classname>/<classname>vector</classname>/<classname>list</classname>
997         and <classname>std::pair</classname> as examples.  For
998         functions, see their member functions, and the free functions
999         in <filename>stl_algobase.h</filename>. Member functions of
1000         other container-like types should read similarly to these
1001         member functions.
1002       </para>
1003
1004       <para>
1005         Some commentary to accompany
1006         the first list in the <ulink url="http://www.stack.nl/~dimitri/doxygen/docblocks.html">Special
1007         Documentation Blocks</ulink> section of
1008         the Doxygen manual:
1009       </para>
1010
1011       <orderedlist>
1012         <listitem>
1013           <para>For longer comments, use the Javadoc style...</para>
1014         </listitem>
1015
1016         <listitem>
1017           <para>
1018             ...not the Qt style. The intermediate *'s are preferred.
1019           </para>
1020         </listitem>
1021
1022         <listitem>
1023           <para>
1024             Use the triple-slash style only for one-line comments (the
1025             <quote>brief</quote> mode).
1026           </para>
1027         </listitem>
1028
1029         <listitem>
1030           <para>
1031             This is disgusting. Don't do this.
1032           </para>
1033         </listitem>
1034       </orderedlist>
1035
1036       <para>
1037         Some specific guidelines:
1038       </para>
1039
1040       <para>
1041         Use the @-style of commands, not the !-style. Please be
1042         careful about whitespace in your markup comments. Most of the
1043         time it doesn't matter; doxygen absorbs most whitespace, and
1044         both HTML and *roff are agnostic about whitespace. However,
1045         in &lt;pre&gt; blocks and @code/@endcode sections, spacing can
1046         have <quote>interesting</quote> effects.
1047       </para>
1048
1049       <para>
1050         Use either kind of grouping, as
1051         appropriate. <filename>doxygroups.cc</filename> exists for this
1052         purpose. See <filename>stl_iterator.h</filename> for a good example
1053         of the <quote>other</quote> kind of grouping.
1054       </para>
1055
1056       <para>
1057         Please use markup tags like @p and @a when referring to things
1058         such as the names of function parameters. Use @e for emphasis
1059         when necessary. Use @c to refer to other standard names.
1060         (Examples of all these abound in the present code.)
1061       </para>
1062
1063       <para>
1064         Complicated math functions should use the multi-line
1065         format. An example from <filename>random.h</filename>:
1066       </para>
1067
1068       <para>
1069 <literallayout>
1070   /**
1071    * @brief A model of a linear congruential random number generator.
1072    *
1073    * @f[
1074    *     x_{i+1}\leftarrow(ax_{i} + c) \bmod m
1075    * @f]
1076    */
1077 </literallayout>
1078       </para>
1079
1080       <para>
1081         Be careful about using certain, special characters when
1082         writing Doxygen comments. Single and double quotes, and
1083         separators in filenames are two common trouble spots. When in
1084         doubt, consult the following table.
1085       </para>
1086
1087 <table frame='all'>
1088 <title>HTML to Doxygen Markup Comparison</title>
1089 <tgroup cols='2' align='left' colsep='1' rowsep='1'>
1090 <colspec colname='c1'></colspec>
1091 <colspec colname='c2'></colspec>
1092
1093   <thead>
1094     <row>
1095       <entry>HTML</entry>
1096       <entry>Doxygen</entry>
1097     </row>
1098   </thead>
1099
1100   <tbody>
1101     <row>
1102       <entry>\</entry>
1103       <entry>\\</entry>
1104     </row>
1105
1106     <row>
1107       <entry>&quot;</entry>
1108       <entry>\"</entry>
1109     </row>
1110
1111     <row>
1112       <entry>&apos;</entry>
1113       <entry>\'</entry>
1114     </row>
1115
1116     <row>
1117       <entry>&lt;i&gt;</entry>
1118       <entry>@a word</entry>
1119     </row>
1120
1121     <row>
1122       <entry>&lt;b&gt;</entry>
1123       <entry>@b word</entry>
1124     </row>
1125
1126     <row>
1127       <entry>&lt;code&gt;</entry>
1128       <entry>@c word</entry>
1129     </row>
1130
1131     <row>
1132       <entry>&lt;em&gt;</entry>
1133       <entry>@a word</entry>
1134     </row>
1135
1136     <row>
1137       <entry>&lt;em&gt;</entry>
1138       <entry>&lt;em&gt;two words or more&lt;/em&gt;</entry>
1139     </row>
1140   </tbody>
1141
1142 </tgroup>
1143 </table>
1144
1145
1146     </sect3>
1147
1148   </sect2>
1149
1150   <sect2 id="doc_style.docbook">
1151     <title>Docbook</title>
1152
1153     <sect3 id="docbook.prereq">
1154       <title>Prerequisites</title>
1155       <para>
1156         Editing the DocBook sources requires an XML editor. Many
1157         exist: some notable options
1158         include <command>emacs</command>, <application>Kate</application>,
1159         or <application>Conglomerate</application>.
1160       </para>
1161
1162       <para>
1163         Some editors support special <quote>XML Validation</quote>
1164         modes that can validate the file as it is
1165         produced. Recommended is the <command>nXML Mode</command>
1166         for <command>emacs</command>.
1167       </para>
1168
1169       <para>
1170         Besides an editor, additional DocBook files and XML tools are
1171         also required.
1172       </para>
1173
1174       <para>
1175         Access to the DocBook stylesheets and DTD is required. The
1176         stylesheets are usually packaged by vendor, in something
1177         like <filename>docbook-style-xsl</filename>. To exactly match
1178         generated output, please use a version of the stylesheets
1179         equivalent
1180         to <filename>docbook-style-xsl-1.74.0-5</filename>. The
1181         installation directory for this package corresponds to
1182         the <literal>XSL_STYLE_DIR</literal>
1183         in <filename>doc/Makefile.am</filename> and defaults
1184         to <filename class="directory">/usr/share/sgml/docbook/xsl-stylesheets</filename>.
1185       </para>
1186
1187       <para>
1188         For processing XML, an XML processor and some style
1189         sheets are necessary. Defaults are <command>xsltproc</command>
1190         provided by <filename>libxslt</filename>.
1191       </para>
1192
1193       <para>
1194         For validating the XML document, you'll need
1195         something like <command>xmllint</command> and access to the
1196         DocBook DTD. These are provided
1197         by a vendor package like <filename>libxml2</filename>.
1198       </para>
1199
1200       <para>
1201         For PDF output, something that transforms valid XML to PDF is
1202         required. Possible solutions include <command>xmlto</command>,
1203         <ulink url="http://xmlgraphics.apache.org/fop/">Apache
1204         FOP</ulink>, or <command>prince</command>. Other options are
1205         listed on the DocBook web <ulink
1206         url="http://wiki.docbook.org/topic/DocBookPublishingTools">pages</ulink>. Please
1207         consult the <email>libstdc++@gcc.gnu.org</email> list when
1208         preparing printed manuals for current best practice and suggestions.
1209       </para>
1210
1211       <para>
1212         Make sure that the XML documentation and markup is valid for
1213         any change. This can be done easily, with the validation rules
1214         in the <filename>Makefile</filename>, which is equivalent to doing:
1215       </para>
1216
1217         <screen>
1218           <userinput>
1219 xmllint --noout --valid <filename>xml/index.xml</filename>
1220           </userinput>
1221         </screen>
1222     </sect3>
1223
1224     <sect3 id="docbook.rules">
1225       <title>Generating the DocBook Files</title>
1226
1227       <para>
1228         The following Makefile rules generate (in order): an HTML
1229         version of all the DocBook documentation, a PDF version of the same, a
1230         single XML document, and the result of validating the entire XML
1231         document.
1232       </para>
1233
1234       <para>
1235       <screen><userinput>make doc-html-docbook</userinput></screen>
1236       </para>
1237
1238       <para>
1239       <screen><userinput>make doc-pdf-docbook</userinput></screen>
1240       </para>
1241
1242       <para>
1243       <screen><userinput>make doc-xml-single-docbook</userinput></screen>
1244       </para>
1245
1246       <para>
1247       <screen><userinput>make doc-xml-validate-docbook</userinput></screen>
1248       </para>
1249
1250     </sect3>
1251
1252     <sect3 id="docbook.examples">
1253       <title>File Organization and Basics</title>
1254
1255     <literallayout>
1256       <emphasis>Which files are important</emphasis>
1257
1258       All Docbook files are in the directory
1259       libstdc++-v3/doc/xml
1260
1261       Inside this directory, the files of importance:
1262       spine.xml         - index to documentation set
1263       manual/spine.xml  - index to manual
1264       manual/*.xml      - individual chapters and sections of the manual
1265       faq.xml           - index to FAQ
1266       api.xml           - index to source level / API
1267
1268       All *.txml files are template xml files, i.e., otherwise empty files with
1269       the correct structure, suitable for filling in with new information.
1270
1271       <emphasis>Canonical Writing Style</emphasis>
1272
1273       class template
1274       function template
1275       member function template
1276       (via C++ Templates, Vandevoorde)
1277
1278       class in namespace std: allocator, not std::allocator
1279
1280       header file: iostream, not &lt;iostream&gt;
1281
1282
1283       <emphasis>General structure</emphasis>
1284
1285       &lt;set&gt;
1286       &lt;book&gt;
1287       &lt;/book&gt;
1288
1289       &lt;book&gt;
1290       &lt;chapter&gt;
1291       &lt;/chapter&gt;
1292       &lt;/book&gt;
1293
1294       &lt;book&gt;
1295       &lt;part&gt;
1296       &lt;chapter&gt;
1297       &lt;section&gt;
1298       &lt;/section&gt;
1299
1300       &lt;sect1&gt;
1301       &lt;/sect1&gt;
1302
1303       &lt;sect1&gt;
1304       &lt;sect2&gt;
1305       &lt;/sect2&gt;
1306       &lt;/sect1&gt;
1307       &lt;/chapter&gt;
1308
1309       &lt;chapter&gt;
1310       &lt;/chapter&gt;
1311       &lt;/part&gt;
1312       &lt;/book&gt;
1313
1314       &lt;/set&gt;
1315     </literallayout>
1316     </sect3>
1317
1318     <sect3 id="docbook.markup">
1319       <title>Markup By Example</title>
1320
1321       <para>
1322         Complete details on Docbook markup can be found in the DocBook
1323         Element Reference,
1324         <ulink url="http://www.docbook.org/tdg/en/html/part2.html">online</ulink>.
1325         An incomplete reference for HTML to Docbook conversion is
1326         detailed in the table below.
1327       </para>
1328
1329 <table frame='all'>
1330 <title>HTML to Docbook XML Markup Comparison</title>
1331 <tgroup cols='2' align='left' colsep='1' rowsep='1'>
1332 <colspec colname='c1'></colspec>
1333 <colspec colname='c2'></colspec>
1334
1335   <thead>
1336     <row>
1337       <entry>HTML</entry>
1338       <entry>Docbook</entry>
1339     </row>
1340   </thead>
1341
1342   <tbody>
1343     <row>
1344       <entry>&lt;p&gt;</entry>
1345       <entry>&lt;para&gt;</entry>
1346     </row>
1347     <row>
1348       <entry>&lt;pre&gt;</entry>
1349       <entry>&lt;computeroutput&gt;, &lt;programlisting&gt;,
1350         &lt;literallayout&gt;</entry>
1351     </row>
1352     <row>
1353       <entry>&lt;ul&gt;</entry>
1354       <entry>&lt;itemizedlist&gt;</entry>
1355     </row>
1356     <row>
1357       <entry>&lt;ol&gt;</entry>
1358       <entry>&lt;orderedlist&gt;</entry>
1359     </row>
1360     <row>
1361       <entry>&lt;il&gt;</entry>
1362       <entry>&lt;listitem&gt;</entry>
1363     </row>
1364     <row>
1365       <entry>&lt;dl&gt;</entry>
1366       <entry>&lt;variablelist&gt;</entry>
1367     </row>
1368     <row>
1369       <entry>&lt;dt&gt;</entry>
1370       <entry>&lt;term&gt;</entry>
1371     </row>
1372     <row>
1373       <entry>&lt;dd&gt;</entry>
1374       <entry>&lt;listitem&gt;</entry>
1375     </row>
1376
1377     <row>
1378       <entry>&lt;a href=""&gt;</entry>
1379       <entry>&lt;ulink url=""&gt;</entry>
1380     </row>
1381     <row>
1382       <entry>&lt;code&gt;</entry>
1383       <entry>&lt;literal&gt;, &lt;programlisting&gt;</entry>
1384     </row>
1385     <row>
1386       <entry>&lt;strong&gt;</entry>
1387       <entry>&lt;emphasis&gt;</entry>
1388     </row>
1389     <row>
1390       <entry>&lt;em&gt;</entry>
1391       <entry>&lt;emphasis&gt;</entry>
1392     </row>
1393     <row>
1394       <entry>&quot;</entry>
1395       <entry>&lt;quote&gt;</entry>
1396     </row>
1397    </tbody>
1398 </tgroup>
1399 </table>
1400
1401 <para>
1402   And examples of detailed markup for which there are no real HTML
1403   equivalents are listed in the table below.
1404 </para>
1405
1406 <table frame='all'>
1407 <title>Docbook XML Element Use</title>
1408 <tgroup cols='2' align='left' colsep='1' rowsep='1'>
1409 <colspec colname='c1'></colspec>
1410 <colspec colname='c2'></colspec>
1411
1412   <thead>
1413     <row>
1414       <entry>Element</entry>
1415       <entry>Use</entry>
1416     </row>
1417   </thead>
1418
1419   <tbody>
1420     <row>
1421       <entry>&lt;structname&gt;</entry>
1422       <entry>&lt;structname&gt;char_traits&lt;/structname&gt;</entry>
1423     </row>
1424     <row>
1425       <entry>&lt;classname&gt;</entry>
1426       <entry>&lt;classname&gt;string&lt;/classname&gt;</entry>
1427     </row>
1428     <row>
1429       <entry>&lt;function&gt;</entry>
1430       <entry>
1431         <para>&lt;function&gt;clear()&lt;/function&gt;</para>
1432         <para>&lt;function&gt;fs.clear()&lt;/function&gt;</para>
1433       </entry>
1434     </row>
1435     <row>
1436       <entry>&lt;type&gt;</entry>
1437       <entry>&lt;type&gt;long long&lt;/type&gt;</entry>
1438     </row>
1439     <row>
1440       <entry>&lt;varname&gt;</entry>
1441       <entry>&lt;varname&gt;fs&lt;/varname&gt;</entry>
1442     </row>
1443     <row>
1444       <entry>&lt;literal&gt;</entry>
1445       <entry>
1446         <para>&lt;literal&gt;-Weffc++&lt;/literal&gt;</para>
1447         <para>&lt;literal&gt;rel_ops&lt;/literal&gt;</para>
1448       </entry>
1449     </row>
1450     <row>
1451       <entry>&lt;constant&gt;</entry>
1452       <entry>
1453         <para>&lt;constant&gt;_GNU_SOURCE&lt;/constant&gt;</para>
1454         <para>&lt;constant&gt;3.0&lt;/constant&gt;</para>
1455       </entry>
1456     </row>
1457     <row>
1458       <entry>&lt;command&gt;</entry>
1459       <entry>&lt;command&gt;g++&lt;/command&gt;</entry>
1460     </row>
1461     <row>
1462       <entry>&lt;errortext&gt;</entry>
1463       <entry>&lt;errortext&gt;In instantiation of&lt;/errortext&gt;</entry>
1464     </row>
1465     <row>
1466       <entry>&lt;filename&gt;</entry>
1467       <entry>
1468         <para>&lt;filename class="headerfile"&gt;ctype.h&lt;/filename&gt;</para>
1469         <para>&lt;filename class="directory"&gt;/home/gcc/build&lt;/filename&gt;</para>
1470         <para>&lt;filename class="libraryfile"&gt;libstdc++.so&lt;/filename&gt;</para>
1471       </entry>
1472     </row>
1473    </tbody>
1474 </tgroup>
1475 </table>
1476
1477     </sect3>
1478   </sect2>
1479
1480   <sect2 id="doc_style.combines">
1481     <title>Combines</title>
1482
1483     <sect3 id="combines.rules">
1484       <title>Generating Combines and Assemblages</title>
1485
1486       <para>
1487         The following Makefile rules are defaults, and are usually
1488         aliased to variable rules.
1489       </para>
1490
1491       <para>
1492       <screen><userinput>make doc-html</userinput></screen>
1493       </para>
1494
1495       <para>
1496       <screen><userinput>make doc-man</userinput></screen>
1497       </para>
1498
1499       <para>
1500       <screen><userinput>make doc-pdf</userinput></screen>
1501       </para>
1502
1503       <para>
1504         The following Makefile rules generate (in order): an HTML
1505         version of all the DocBook documentation with links into an
1506         local Doxygen cache, and a PDF version of the same.
1507       </para>
1508
1509       <para>
1510       <screen><userinput>make doc-html-combine</userinput></screen>
1511       </para>
1512
1513       <para>
1514       <screen><userinput>make doc-pdf-combine</userinput></screen>
1515       </para>
1516   </sect3>
1517   </sect2>
1518 </sect1>
1519
1520 <sect1 id="contrib.design_notes" xreflabel="Design Notes">
1521   <?dbhtml filename="source_design_notes.html"?>
1522   <title>Design Notes</title>
1523   <para>
1524   </para>
1525
1526   <literallayout>
1527
1528     The Library
1529     -----------
1530
1531     This paper is covers two major areas:
1532
1533     - Features and policies not mentioned in the standard that
1534     the quality of the library implementation depends on, including
1535     extensions and "implementation-defined" features;
1536
1537     - Plans for required but unimplemented library features and
1538     optimizations to them.
1539
1540     Overhead
1541     --------
1542
1543     The standard defines a large library, much larger than the standard
1544     C library. A naive implementation would suffer substantial overhead
1545     in compile time, executable size, and speed, rendering it unusable
1546     in many (particularly embedded) applications. The alternative demands
1547     care in construction, and some compiler support, but there is no
1548     need for library subsets.
1549
1550     What are the sources of this overhead?  There are four main causes:
1551
1552     - The library is specified almost entirely as templates, which
1553     with current compilers must be included in-line, resulting in
1554     very slow builds as tens or hundreds of thousands of lines
1555     of function definitions are read for each user source file.
1556     Indeed, the entire SGI STL, as well as the dos Reis valarray,
1557     are provided purely as header files, largely for simplicity in
1558     porting. Iostream/locale is (or will be) as large again.
1559
1560     - The library is very flexible, specifying a multitude of hooks
1561     where users can insert their own code in place of defaults.
1562     When these hooks are not used, any time and code expended to
1563     support that flexibility is wasted.
1564
1565     - Templates are often described as causing to "code bloat". In
1566     practice, this refers (when it refers to anything real) to several
1567     independent processes. First, when a class template is manually
1568     instantiated in its entirely, current compilers place the definitions
1569     for all members in a single object file, so that a program linking
1570     to one member gets definitions of all. Second, template functions
1571     which do not actually depend on the template argument are, under
1572     current compilers, generated anew for each instantiation, rather
1573     than being shared with other instantiations. Third, some of the
1574     flexibility mentioned above comes from virtual functions (both in
1575     regular classes and template classes) which current linkers add
1576     to the executable file even when they manifestly cannot be called.
1577
1578     - The library is specified to use a language feature, exceptions,
1579     which in the current gcc compiler ABI imposes a run time and
1580     code space cost to handle the possibility of exceptions even when
1581     they are not used. Under the new ABI (accessed with -fnew-abi),
1582     there is a space overhead and a small reduction in code efficiency
1583     resulting from lost optimization opportunities associated with
1584     non-local branches associated with exceptions.
1585
1586     What can be done to eliminate this overhead?  A variety of coding
1587     techniques, and compiler, linker and library improvements and
1588     extensions may be used, as covered below. Most are not difficult,
1589     and some are already implemented in varying degrees.
1590
1591     Overhead: Compilation Time
1592     --------------------------
1593
1594     Providing "ready-instantiated" template code in object code archives
1595     allows us to avoid generating and optimizing template instantiations
1596     in each compilation unit which uses them. However, the number of such
1597     instantiations that are useful to provide is limited, and anyway this
1598     is not enough, by itself, to minimize compilation time. In particular,
1599     it does not reduce time spent parsing conforming headers.
1600
1601     Quicker header parsing will depend on library extensions and compiler
1602     improvements.  One approach is some variation on the techniques
1603     previously marketed as "pre-compiled headers", now standardized as
1604     support for the "export" keyword. "Exported" template definitions
1605     can be placed (once) in a "repository" -- really just a library, but
1606     of template definitions rather than object code -- to be drawn upon
1607     at link time when an instantiation is needed, rather than placed in
1608     header files to be parsed along with every compilation unit.
1609
1610     Until "export" is implemented we can put some of the lengthy template
1611     definitions in #if guards or alternative headers so that users can skip
1612     over the full definitions when they need only the ready-instantiated
1613     specializations.
1614
1615     To be precise, this means that certain headers which define
1616     templates which users normally use only for certain arguments
1617     can be instrumented to avoid exposing the template definitions
1618     to the compiler unless a macro is defined. For example, in
1619     &lt;string&gt;, we might have:
1620
1621     template &lt;class _CharT, ... &gt; class basic_string {
1622     ... // member declarations
1623     };
1624     ... // operator declarations
1625
1626     #ifdef _STRICT_ISO_
1627     # if _G_NO_TEMPLATE_EXPORT
1628     #   include &lt;bits/std_locale.h&gt;  // headers needed by definitions
1629     #   ...
1630     #   include &lt;bits/string.tcc&gt;  // member and global template definitions.
1631     # endif
1632     #endif
1633
1634     Users who compile without specifying a strict-ISO-conforming flag
1635     would not see many of the template definitions they now see, and rely
1636     instead on ready-instantiated specializations in the library. This
1637     technique would be useful for the following substantial components:
1638     string, locale/iostreams, valarray. It would *not* be useful or
1639     usable with the following: containers, algorithms, iterators,
1640     allocator. Since these constitute a large (though decreasing)
1641     fraction of the library, the benefit the technique offers is
1642     limited.
1643
1644     The language specifies the semantics of the "export" keyword, but
1645     the gcc compiler does not yet support it. When it does, problems
1646     with large template inclusions can largely disappear, given some
1647     minor library reorganization, along with the need for the apparatus
1648     described above.
1649
1650     Overhead: Flexibility Cost
1651     --------------------------
1652
1653     The library offers many places where users can specify operations
1654     to be performed by the library in place of defaults. Sometimes
1655     this seems to require that the library use a more-roundabout, and
1656     possibly slower, way to accomplish the default requirements than
1657     would be used otherwise.
1658
1659     The primary protection against this overhead is thorough compiler
1660     optimization, to crush out layers of inline function interfaces.
1661     Kuck &amp; Associates has demonstrated the practicality of this kind
1662     of optimization.
1663
1664     The second line of defense against this overhead is explicit
1665     specialization. By defining helper function templates, and writing
1666     specialized code for the default case, overhead can be eliminated
1667     for that case without sacrificing flexibility. This takes full
1668     advantage of any ability of the optimizer to crush out degenerate
1669     code.
1670
1671     The library specifies many virtual functions which current linkers
1672     load even when they cannot be called. Some minor improvements to the
1673     compiler and to ld would eliminate any such overhead by simply
1674     omitting virtual functions that the complete program does not call.
1675     A prototype of this work has already been done. For targets where
1676     GNU ld is not used, a "pre-linker" could do the same job.
1677
1678     The main areas in the standard interface where user flexibility
1679     can result in overhead are:
1680
1681     - Allocators:  Containers are specified to use user-definable
1682     allocator types and objects, making tuning for the container
1683     characteristics tricky.
1684
1685     - Locales: the standard specifies locale objects used to implement
1686     iostream operations, involving many virtual functions which use
1687     streambuf iterators.
1688
1689     - Algorithms and containers: these may be instantiated on any type,
1690     frequently duplicating code for identical operations.
1691
1692     - Iostreams and strings: users are permitted to use these on their
1693     own types, and specify the operations the stream must use on these
1694     types.
1695
1696     Note that these sources of overhead are _avoidable_. The techniques
1697     to avoid them are covered below.
1698
1699     Code Bloat
1700     ----------
1701
1702     In the SGI STL, and in some other headers, many of the templates
1703     are defined "inline" -- either explicitly or by their placement
1704     in class definitions -- which should not be inline. This is a
1705     source of code bloat. Matt had remarked that he was relying on
1706     the compiler to recognize what was too big to benefit from inlining,
1707     and generate it out-of-line automatically. However, this also can
1708     result in code bloat except where the linker can eliminate the extra
1709     copies.
1710
1711     Fixing these cases will require an audit of all inline functions
1712     defined in the library to determine which merit inlining, and moving
1713     the rest out of line. This is an issue mainly in chapters 23, 25, and
1714     27. Of course it can be done incrementally, and we should generally
1715     accept patches that move large functions out of line and into ".tcc"
1716     files, which can later be pulled into a repository. Compiler/linker
1717     improvements to recognize very large inline functions and move them
1718     out-of-line, but shared among compilation units, could make this
1719     work unnecessary.
1720
1721     Pre-instantiating template specializations currently produces large
1722     amounts of dead code which bloats statically linked programs. The
1723     current state of the static library, libstdc++.a, is intolerable on
1724     this account, and will fuel further confused speculation about a need
1725     for a library "subset". A compiler improvement that treats each
1726     instantiated function as a separate object file, for linking purposes,
1727     would be one solution to this problem. An alternative would be to
1728     split up the manual instantiation files into dozens upon dozens of
1729     little files, each compiled separately, but an abortive attempt at
1730     this was done for &lt;string&gt; and, though it is far from complete, it
1731     is already a nuisance. A better interim solution (just until we have
1732     "export") is badly needed.
1733
1734     When building a shared library, the current compiler/linker cannot
1735     automatically generate the instantiations needed. This creates a
1736     miserable situation; it means any time something is changed in the
1737     library, before a shared library can be built someone must manually
1738     copy the declarations of all templates that are needed by other parts
1739     of the library to an "instantiation" file, and add it to the build
1740     system to be compiled and linked to the library. This process is
1741     readily automated, and should be automated as soon as possible.
1742     Users building their own shared libraries experience identical
1743     frustrations.
1744
1745     Sharing common aspects of template definitions among instantiations
1746     can radically reduce code bloat. The compiler could help a great
1747     deal here by recognizing when a function depends on nothing about
1748     a template parameter, or only on its size, and giving the resulting
1749     function a link-name "equate" that allows it to be shared with other
1750     instantiations. Implementation code could take advantage of the
1751     capability by factoring out code that does not depend on the template
1752     argument into separate functions to be merged by the compiler.
1753
1754     Until such a compiler optimization is implemented, much can be done
1755     manually (if tediously) in this direction. One such optimization is
1756     to derive class templates from non-template classes, and move as much
1757     implementation as possible into the base class. Another is to partial-
1758     specialize certain common instantiations, such as vector&lt;T*&gt;, to share
1759     code for instantiations on all types T. While these techniques work,
1760     they are far from the complete solution that a compiler improvement
1761     would afford.
1762
1763     Overhead: Expensive Language Features
1764     -------------------------------------
1765
1766     The main "expensive" language feature used in the standard library
1767     is exception support, which requires compiling in cleanup code with
1768     static table data to locate it, and linking in library code to use
1769     the table. For small embedded programs the amount of such library
1770     code and table data is assumed by some to be excessive. Under the
1771     "new" ABI this perception is generally exaggerated, although in some
1772     cases it may actually be excessive.
1773
1774     To implement a library which does not use exceptions directly is
1775     not difficult given minor compiler support (to "turn off" exceptions
1776     and ignore exception constructs), and results in no great library
1777     maintenance difficulties. To be precise, given "-fno-exceptions",
1778     the compiler should treat "try" blocks as ordinary blocks, and
1779     "catch" blocks as dead code to ignore or eliminate. Compiler
1780     support is not strictly necessary, except in the case of "function
1781     try blocks"; otherwise the following macros almost suffice:
1782
1783     #define throw(X)
1784     #define try      if (true)
1785     #define catch(X) else if (false)
1786
1787     However, there may be a need to use function try blocks in the
1788     library implementation, and use of macros in this way can make
1789     correct diagnostics impossible. Furthermore, use of this scheme
1790     would require the library to call a function to re-throw exceptions
1791     from a try block. Implementing the above semantics in the compiler
1792     is preferable.
1793
1794     Given the support above (however implemented) it only remains to
1795     replace code that "throws" with a call to a well-documented "handler"
1796     function in a separate compilation unit which may be replaced by
1797     the user. The main source of exceptions that would be difficult
1798     for users to avoid is memory allocation failures, but users can
1799     define their own memory allocation primitives that never throw.
1800     Otherwise, the complete list of such handlers, and which library
1801     functions may call them, would be needed for users to be able to
1802     implement the necessary substitutes. (Fortunately, they have the
1803     source code.)
1804
1805     Opportunities
1806     -------------
1807
1808     The template capabilities of C++ offer enormous opportunities for
1809     optimizing common library operations, well beyond what would be
1810     considered "eliminating overhead". In particular, many operations
1811     done in Glibc with macros that depend on proprietary language
1812     extensions can be implemented in pristine Standard C++. For example,
1813     the chapter 25 algorithms, and even C library functions such as strchr,
1814     can be specialized for the case of static arrays of known (small) size.
1815
1816     Detailed optimization opportunities are identified below where
1817     the component where they would appear is discussed. Of course new
1818     opportunities will be identified during implementation.
1819
1820     Unimplemented Required Library Features
1821     ---------------------------------------
1822
1823     The standard specifies hundreds of components, grouped broadly by
1824     chapter. These are listed in excruciating detail in the CHECKLIST
1825     file.
1826
1827     17 general
1828     18 support
1829     19 diagnostics
1830     20 utilities
1831     21 string
1832     22 locale
1833     23 containers
1834     24 iterators
1835     25 algorithms
1836     26 numerics
1837     27 iostreams
1838     Annex D  backward compatibility
1839
1840     Anyone participating in implementation of the library should obtain
1841     a copy of the standard, ISO 14882.  People in the U.S. can obtain an
1842     electronic copy for US$18 from ANSI's web site. Those from other
1843     countries should visit http://www.iso.org/ to find out the location
1844     of their country's representation in ISO, in order to know who can
1845     sell them a copy.
1846
1847     The emphasis in the following sections is on unimplemented features
1848     and optimization opportunities.
1849
1850     Chapter 17  General
1851     -------------------
1852
1853     Chapter 17 concerns overall library requirements.
1854
1855     The standard doesn't mention threads. A multi-thread (MT) extension
1856     primarily affects operators new and delete (18), allocator (20),
1857     string (21), locale (22), and iostreams (27). The common underlying
1858     support needed for this is discussed under chapter 20.
1859
1860     The standard requirements on names from the C headers create a
1861     lot of work, mostly done. Names in the C headers must be visible
1862     in the std:: and sometimes the global namespace; the names in the
1863     two scopes must refer to the same object. More stringent is that
1864     Koenig lookup implies that any types specified as defined in std::
1865     really are defined in std::. Names optionally implemented as
1866     macros in C cannot be macros in C++. (An overview may be read at
1867     &lt;http://www.cantrip.org/cheaders.html&gt;). The scripts "inclosure"
1868     and "mkcshadow", and the directories shadow/ and cshadow/, are the
1869     beginning of an effort to conform in this area.
1870
1871     A correct conforming definition of C header names based on underlying
1872     C library headers, and practical linking of conforming namespaced
1873     customer code with third-party C libraries depends ultimately on
1874     an ABI change, allowing namespaced C type names to be mangled into
1875     type names as if they were global, somewhat as C function names in a
1876     namespace, or C++ global variable names, are left unmangled. Perhaps
1877     another "extern" mode, such as 'extern "C-global"' would be an
1878     appropriate place for such type definitions. Such a type would
1879     affect mangling as follows:
1880
1881     namespace A {
1882     struct X {};
1883     extern "C-global" {  // or maybe just 'extern "C"'
1884     struct Y {};
1885     };
1886     }
1887     void f(A::X*);  // mangles to f__FPQ21A1X
1888     void f(A::Y*);  // mangles to f__FP1Y
1889
1890     (It may be that this is really the appropriate semantics for regular
1891     'extern "C"', and 'extern "C-global"', as an extension, would not be
1892     necessary.) This would allow functions declared in non-standard C headers
1893     (and thus fixable by neither us nor users) to link properly with functions
1894     declared using C types defined in properly-namespaced headers. The
1895     problem this solves is that C headers (which C++ programmers do persist
1896     in using) frequently forward-declare C struct tags without including
1897     the header where the type is defined, as in
1898
1899     struct tm;
1900     void munge(tm*);
1901
1902     Without some compiler accommodation, munge cannot be called by correct
1903     C++ code using a pointer to a correctly-scoped tm* value.
1904
1905     The current C headers use the preprocessor extension "#include_next",
1906     which the compiler complains about when run "-pedantic".
1907     (Incidentally, it appears that "-fpedantic" is currently ignored,
1908     probably a bug.)  The solution in the C compiler is to use
1909     "-isystem" rather than "-I", but unfortunately in g++ this seems
1910     also to wrap the whole header in an 'extern "C"' block, so it's
1911     unusable for C++ headers. The correct solution appears to be to
1912     allow the various special include-directory options, if not given
1913     an argument, to affect subsequent include-directory options additively,
1914     so that if one said
1915
1916     -pedantic -iprefix $(prefix) \
1917     -idirafter -ino-pedantic -ino-extern-c -iwithprefix -I g++-v3 \
1918     -iwithprefix -I g++-v3/ext
1919
1920     the compiler would search $(prefix)/g++-v3 and not report
1921     pedantic warnings for files found there, but treat files in
1922     $(prefix)/g++-v3/ext pedantically. (The undocumented semantics
1923     of "-isystem" in g++ stink. Can they be rescinded?  If not it
1924     must be replaced with something more rationally behaved.)
1925
1926     All the C headers need the treatment above; in the standard these
1927     headers are mentioned in various chapters. Below, I have only
1928     mentioned those that present interesting implementation issues.
1929
1930     The components identified as "mostly complete", below, have not been
1931     audited for conformance. In many cases where the library passes
1932     conformance tests we have non-conforming extensions that must be
1933     wrapped in #if guards for "pedantic" use, and in some cases renamed
1934     in a conforming way for continued use in the implementation regardless
1935     of conformance flags.
1936
1937     The STL portion of the library still depends on a header
1938     stl/bits/stl_config.h full of #ifdef clauses. This apparatus
1939     should be replaced with autoconf/automake machinery.
1940
1941     The SGI STL defines a type_traits&lt;&gt; template, specialized for
1942     many types in their code including the built-in numeric and
1943     pointer types and some library types, to direct optimizations of
1944     standard functions. The SGI compiler has been extended to generate
1945     specializations of this template automatically for user types,
1946     so that use of STL templates on user types can take advantage of
1947     these optimizations. Specializations for other, non-STL, types
1948     would make more optimizations possible, but extending the gcc
1949     compiler in the same way would be much better. Probably the next
1950     round of standardization will ratify this, but probably with
1951     changes, so it probably should be renamed to place it in the
1952     implementation namespace.
1953
1954     The SGI STL also defines a large number of extensions visible in
1955     standard headers. (Other extensions that appear in separate headers
1956     have been sequestered in subdirectories ext/ and backward/.)  All
1957     these extensions should be moved to other headers where possible,
1958     and in any case wrapped in a namespace (not std!), and (where kept
1959     in a standard header) girded about with macro guards. Some cannot be
1960     moved out of standard headers because they are used to implement
1961     standard features.  The canonical method for accommodating these
1962     is to use a protected name, aliased in macro guards to a user-space
1963     name. Unfortunately C++ offers no satisfactory template typedef
1964     mechanism, so very ad-hoc and unsatisfactory aliasing must be used
1965     instead.
1966
1967     Implementation of a template typedef mechanism should have the highest
1968     priority among possible extensions, on the same level as implementation
1969     of the template "export" feature.
1970
1971     Chapter 18  Language support
1972     ----------------------------
1973
1974     Headers: &lt;limits&gt; &lt;new&gt; &lt;typeinfo&gt; &lt;exception&gt;
1975     C headers: &lt;cstddef&gt; &lt;climits&gt; &lt;cfloat&gt;  &lt;cstdarg&gt; &lt;csetjmp&gt;
1976     &lt;ctime&gt;   &lt;csignal&gt; &lt;cstdlib&gt; (also 21, 25, 26)
1977
1978     This defines the built-in exceptions, rtti, numeric_limits&lt;&gt;,
1979     operator new and delete. Much of this is provided by the
1980     compiler in its static runtime library.
1981
1982     Work to do includes defining numeric_limits&lt;&gt; specializations in
1983     separate files for all target architectures. Values for integer types
1984     except for bool and wchar_t are readily obtained from the C header
1985     &lt;limits.h&gt;, but values for the remaining numeric types (bool, wchar_t,
1986     float, double, long double) must be entered manually. This is
1987     largely dog work except for those members whose values are not
1988     easily deduced from available documentation. Also, this involves
1989     some work in target configuration to identify the correct choice of
1990     file to build against and to install.
1991
1992     The definitions of the various operators new and delete must be
1993     made thread-safe, which depends on a portable exclusion mechanism,
1994     discussed under chapter 20.  Of course there is always plenty of
1995     room for improvements to the speed of operators new and delete.
1996
1997     &lt;cstdarg&gt;, in Glibc, defines some macros that gcc does not allow to
1998     be wrapped into an inline function. Probably this header will demand
1999     attention whenever a new target is chosen. The functions atexit(),
2000     exit(), and abort() in cstdlib have different semantics in C++, so
2001     must be re-implemented for C++.
2002
2003     Chapter 19  Diagnostics
2004     -----------------------
2005
2006     Headers: &lt;stdexcept&gt;
2007     C headers: &lt;cassert&gt; &lt;cerrno&gt;
2008
2009     This defines the standard exception objects, which are "mostly complete".
2010     Cygnus has a version, and now SGI provides a slightly different one.
2011     It makes little difference which we use.
2012
2013     The C global name "errno", which C allows to be a variable or a macro,
2014     is required in C++ to be a macro. For MT it must typically result in
2015     a function call.
2016
2017     Chapter 20  Utilities
2018     ---------------------
2019     Headers: &lt;utility&gt; &lt;functional&gt; &lt;memory&gt;
2020     C header: &lt;ctime&gt; (also in 18)
2021
2022     SGI STL provides "mostly complete" versions of all the components
2023     defined in this chapter. However, the auto_ptr&lt;&gt; implementation
2024     is known to be wrong. Furthermore, the standard definition of it
2025     is known to be unimplementable as written. A minor change to the
2026     standard would fix it, and auto_ptr&lt;&gt; should be adjusted to match.
2027
2028     Multi-threading affects the allocator implementation, and there must
2029     be configuration/installation choices for different users' MT
2030     requirements. Anyway, users will want to tune allocator options
2031     to support different target conditions, MT or no.
2032
2033     The primitives used for MT implementation should be exposed, as an
2034     extension, for users' own work. We need cross-CPU "mutex" support,
2035     multi-processor shared-memory atomic integer operations, and single-
2036     processor uninterruptible integer operations, and all three configurable
2037     to be stubbed out for non-MT use, or to use an appropriately-loaded
2038     dynamic library for the actual runtime environment, or statically
2039     compiled in for cases where the target architecture is known.
2040
2041     Chapter 21  String
2042     ------------------
2043     Headers: &lt;string&gt;
2044     C headers: &lt;cctype&gt; &lt;cwctype&gt; &lt;cstring&gt; &lt;cwchar&gt; (also in 27)
2045     &lt;cstdlib&gt; (also in 18, 25, 26)
2046
2047     We have "mostly-complete" char_traits&lt;&gt; implementations. Many of the
2048     char_traits&lt;char&gt; operations might be optimized further using existing
2049     proprietary language extensions.
2050
2051     We have a "mostly-complete" basic_string&lt;&gt; implementation. The work
2052     to manually instantiate char and wchar_t specializations in object
2053     files to improve link-time behavior is extremely unsatisfactory,
2054     literally tripling library-build time with no commensurate improvement
2055     in static program link sizes. It must be redone. (Similar work is
2056     needed for some components in chapters 22 and 27.)
2057
2058     Other work needed for strings is MT-safety, as discussed under the
2059     chapter 20 heading.
2060
2061     The standard C type mbstate_t from &lt;cwchar&gt; and used in char_traits&lt;&gt;
2062     must be different in C++ than in C, because in C++ the default constructor
2063     value mbstate_t() must be the "base" or "ground" sequence state.
2064     (According to the likely resolution of a recently raised Core issue,
2065     this may become unnecessary. However, there are other reasons to
2066     use a state type not as limited as whatever the C library provides.)
2067     If we might want to provide conversions from (e.g.) internally-
2068     represented EUC-wide to externally-represented Unicode, or vice-
2069     versa, the mbstate_t we choose will need to be more accommodating
2070     than what might be provided by an underlying C library.
2071
2072     There remain some basic_string template-member functions which do
2073     not overload properly with their non-template brethren. The infamous
2074     hack akin to what was done in vector&lt;&gt; is needed, to conform to
2075     23.1.1 para 10. The CHECKLIST items for basic_string marked 'X',
2076     or incomplete, are so marked for this reason.
2077
2078     Replacing the string iterators, which currently are simple character
2079     pointers, with class objects would greatly increase the safety of the
2080     client interface, and also permit a "debug" mode in which range,
2081     ownership, and validity are rigorously checked. The current use of
2082     raw pointers as string iterators is evil. vector&lt;&gt; iterators need the
2083     same treatment. Note that the current implementation freely mixes
2084     pointers and iterators, and that must be fixed before safer iterators
2085     can be introduced.
2086
2087     Some of the functions in &lt;cstring&gt; are different from the C version.
2088     generally overloaded on const and non-const argument pointers. For
2089     example, in &lt;cstring&gt; strchr is overloaded. The functions isupper
2090     etc. in &lt;cctype&gt; typically implemented as macros in C are functions
2091     in C++, because they are overloaded with others of the same name
2092     defined in &lt;locale&gt;.
2093
2094     Many of the functions required in &lt;cwctype&gt; and &lt;cwchar&gt; cannot be
2095     implemented using underlying C facilities on intended targets because
2096     such facilities only partly exist.
2097
2098     Chapter 22  Locale
2099     ------------------
2100     Headers: &lt;locale&gt;
2101     C headers: &lt;clocale&gt;
2102
2103     We have a "mostly complete" class locale, with the exception of
2104     code for constructing, and handling the names of, named locales.
2105     The ways that locales are named (particularly when categories
2106     (e.g. LC_TIME, LC_COLLATE) are different) varies among all target
2107     environments. This code must be written in various versions and
2108     chosen by configuration parameters.
2109
2110     Members of many of the facets defined in &lt;locale&gt; are stubs. Generally,
2111     there are two sets of facets: the base class facets (which are supposed
2112     to implement the "C" locale) and the "byname" facets, which are supposed
2113     to read files to determine their behavior. The base ctype&lt;&gt;, collate&lt;&gt;,
2114     and numpunct&lt;&gt; facets are "mostly complete", except that the table of
2115     bitmask values used for "is" operations, and corresponding mask values,
2116     are still defined in libio and just included/linked. (We will need to
2117     implement these tables independently, soon, but should take advantage
2118     of libio where possible.)  The num_put&lt;&gt;::put members for integer types
2119     are "mostly complete".
2120
2121     A complete list of what has and has not been implemented may be
2122     found in CHECKLIST. However, note that the current definition of
2123     codecvt&lt;wchar_t,char,mbstate_t&gt; is wrong. It should simply write
2124     out the raw bytes representing the wide characters, rather than
2125     trying to convert each to a corresponding single "char" value.
2126
2127     Some of the facets are more important than others. Specifically,
2128     the members of ctype&lt;&gt;, numpunct&lt;&gt;, num_put&lt;&gt;, and num_get&lt;&gt; facets
2129     are used by other library facilities defined in &lt;string&gt;, &lt;istream&gt;,
2130     and &lt;ostream&gt;, and the codecvt&lt;&gt; facet is used by basic_filebuf&lt;&gt;
2131     in &lt;fstream&gt;, so a conforming iostream implementation depends on
2132     these.
2133
2134     The "long long" type eventually must be supported, but code mentioning
2135     it should be wrapped in #if guards to allow pedantic-mode compiling.
2136
2137     Performance of num_put&lt;&gt; and num_get&lt;&gt; depend critically on
2138     caching computed values in ios_base objects, and on extensions
2139     to the interface with streambufs.
2140
2141     Specifically: retrieving a copy of the locale object, extracting
2142     the needed facets, and gathering data from them, for each call to
2143     (e.g.) operator&lt;&lt; would be prohibitively slow.  To cache format
2144     data for use by num_put&lt;&gt; and num_get&lt;&gt; we have a _Format_cache&lt;&gt;
2145     object stored in the ios_base::pword() array. This is constructed
2146     and initialized lazily, and is organized purely for utility. It
2147     is discarded when a new locale with different facets is imbued.
2148
2149     Using only the public interfaces of the iterator arguments to the
2150     facet functions would limit performance by forbidding "vector-style"
2151     character operations. The streambuf iterator optimizations are
2152     described under chapter 24, but facets can also bypass the streambuf
2153     iterators via explicit specializations and operate directly on the
2154     streambufs, and use extended interfaces to get direct access to the
2155     streambuf internal buffer arrays. These extensions are mentioned
2156     under chapter 27. These optimizations are particularly important
2157     for input parsing.
2158
2159     Unused virtual members of locale facets can be omitted, as mentioned
2160     above, by a smart linker.
2161
2162     Chapter 23  Containers
2163     ----------------------
2164     Headers: &lt;deque&gt; &lt;list&gt; &lt;queue&gt; &lt;stack&gt; &lt;vector&gt; &lt;map&gt; &lt;set&gt; &lt;bitset&gt;
2165
2166     All the components in chapter 23 are implemented in the SGI STL.
2167     They are "mostly complete"; they include a large number of
2168     nonconforming extensions which must be wrapped. Some of these
2169     are used internally and must be renamed or duplicated.
2170
2171     The SGI components are optimized for large-memory environments. For
2172     embedded targets, different criteria might be more appropriate. Users
2173     will want to be able to tune this behavior. We should provide
2174     ways for users to compile the library with different memory usage
2175     characteristics.
2176
2177     A lot more work is needed on factoring out common code from different
2178     specializations to reduce code size here and in chapter 25. The
2179     easiest fix for this would be a compiler/ABI improvement that allows
2180     the compiler to recognize when a specialization depends only on the
2181     size (or other gross quality) of a template argument, and allow the
2182     linker to share the code with similar specializations. In its
2183     absence, many of the algorithms and containers can be partial-
2184     specialized, at least for the case of pointers, but this only solves
2185     a small part of the problem. Use of a type_traits-style template
2186     allows a few more optimization opportunities, more if the compiler
2187     can generate the specializations automatically.
2188
2189     As an optimization, containers can specialize on the default allocator
2190     and bypass it, or take advantage of details of its implementation
2191     after it has been improved upon.
2192
2193     Replacing the vector iterators, which currently are simple element
2194     pointers, with class objects would greatly increase the safety of the
2195     client interface, and also permit a "debug" mode in which range,
2196     ownership, and validity are rigorously checked. The current use of
2197     pointers for iterators is evil.
2198
2199     As mentioned for chapter 24, the deque iterator is a good example of
2200     an opportunity to implement a "staged" iterator that would benefit
2201     from specializations of some algorithms.
2202
2203     Chapter 24  Iterators
2204     ---------------------
2205     Headers: &lt;iterator&gt;
2206
2207     Standard iterators are "mostly complete", with the exception of
2208     the stream iterators, which are not yet templatized on the
2209     stream type. Also, the base class template iterator&lt;&gt; appears
2210     to be wrong, so everything derived from it must also be wrong,
2211     currently.
2212
2213     The streambuf iterators (currently located in stl/bits/std_iterator.h,
2214     but should be under bits/) can be rewritten to take advantage of
2215     friendship with the streambuf implementation.
2216
2217     Matt Austern has identified opportunities where certain iterator
2218     types, particularly including streambuf iterators and deque
2219     iterators, have a "two-stage" quality, such that an intermediate
2220     limit can be checked much more quickly than the true limit on
2221     range operations. If identified with a member of iterator_traits,
2222     algorithms may be specialized for this case. Of course the
2223     iterators that have this quality can be identified by specializing
2224     a traits class.
2225
2226     Many of the algorithms must be specialized for the streambuf
2227     iterators, to take advantage of block-mode operations, in order
2228     to allow iostream/locale operations' performance not to suffer.
2229     It may be that they could be treated as staged iterators and
2230     take advantage of those optimizations.
2231
2232     Chapter 25  Algorithms
2233     ----------------------
2234     Headers: &lt;algorithm&gt;
2235     C headers: &lt;cstdlib&gt; (also in 18, 21, 26))
2236
2237     The algorithms are "mostly complete". As mentioned above, they
2238     are optimized for speed at the expense of code and data size.
2239
2240     Specializations of many of the algorithms for non-STL types would
2241     give performance improvements, but we must use great care not to
2242     interfere with fragile template overloading semantics for the
2243     standard interfaces. Conventionally the standard function template
2244     interface is an inline which delegates to a non-standard function
2245     which is then overloaded (this is already done in many places in
2246     the library). Particularly appealing opportunities for the sake of
2247     iostream performance are for copy and find applied to streambuf
2248     iterators or (as noted elsewhere) for staged iterators, of which
2249     the streambuf iterators are a good example.
2250
2251     The bsearch and qsort functions cannot be overloaded properly as
2252     required by the standard because gcc does not yet allow overloading
2253     on the extern-"C"-ness of a function pointer.
2254
2255     Chapter 26  Numerics
2256     --------------------
2257     Headers: &lt;complex&gt; &lt;valarray&gt; &lt;numeric&gt;
2258     C headers: &lt;cmath&gt;, &lt;cstdlib&gt; (also 18, 21, 25)
2259
2260     Numeric components: Gabriel dos Reis's valarray, Drepper's complex,
2261     and the few algorithms from the STL are "mostly done".  Of course
2262     optimization opportunities abound for the numerically literate. It
2263     is not clear whether the valarray implementation really conforms
2264     fully, in the assumptions it makes about aliasing (and lack thereof)
2265     in its arguments.
2266
2267     The C div() and ldiv() functions are interesting, because they are the
2268     only case where a C library function returns a class object by value.
2269     Since the C++ type div_t must be different from the underlying C type
2270     (which is in the wrong namespace) the underlying functions div() and
2271     ldiv() cannot be re-used efficiently. Fortunately they are trivial to
2272     re-implement.
2273
2274     Chapter 27  Iostreams
2275     ---------------------
2276     Headers: &lt;iosfwd&gt; &lt;streambuf&gt; &lt;ios&gt; &lt;ostream&gt; &lt;istream&gt; &lt;iostream&gt;
2277     &lt;iomanip&gt; &lt;sstream&gt; &lt;fstream&gt;
2278     C headers: &lt;cstdio&gt; &lt;cwchar&gt; (also in 21)
2279
2280     Iostream is currently in a very incomplete state. &lt;iosfwd&gt;, &lt;iomanip&gt;,
2281     ios_base, and basic_ios&lt;&gt; are "mostly complete". basic_streambuf&lt;&gt; and
2282     basic_ostream&lt;&gt; are well along, but basic_istream&lt;&gt; has had little work
2283     done. The standard stream objects, &lt;sstream&gt; and &lt;fstream&gt; have been
2284     started; basic_filebuf&lt;&gt; "write" functions have been implemented just
2285     enough to do "hello, world".
2286
2287     Most of the istream and ostream operators &lt;&lt; and &gt;&gt; (with the exception
2288     of the op&lt;&lt;(integer) ones) have not been changed to use locale primitives,
2289     sentry objects, or char_traits members.
2290
2291     All these templates should be manually instantiated for char and
2292     wchar_t in a way that links only used members into user programs.
2293
2294     Streambuf is fertile ground for optimization extensions. An extended
2295     interface giving iterator access to its internal buffer would be very
2296     useful for other library components.
2297
2298     Iostream operations (primarily operators &lt;&lt; and &gt;&gt;) can take advantage
2299     of the case where user code has not specified a locale, and bypass locale
2300     operations entirely. The current implementation of op&lt;&lt;/num_put&lt;&gt;::put,
2301     for the integer types, demonstrates how they can cache encoding details
2302     from the locale on each operation. There is lots more room for
2303     optimization in this area.
2304
2305     The definition of the relationship between the standard streams
2306     cout et al. and stdout et al. requires something like a "stdiobuf".
2307     The SGI solution of using double-indirection to actually use a
2308     stdio FILE object for buffering is unsatisfactory, because it
2309     interferes with peephole loop optimizations.
2310
2311     The &lt;sstream&gt; header work has begun. stringbuf can benefit from
2312     friendship with basic_string&lt;&gt; and basic_string&lt;&gt;::_Rep to use
2313     those objects directly as buffers, and avoid allocating and making
2314     copies.
2315
2316     The basic_filebuf&lt;&gt; template is a complex beast. It is specified to
2317     use the locale facet codecvt&lt;&gt; to translate characters between native
2318     files and the locale character encoding. In general this involves
2319     two buffers, one of "char" representing the file and another of
2320     "char_type", for the stream, with codecvt&lt;&gt; translating. The process
2321     is complicated by the variable-length nature of the translation, and
2322     the need to seek to corresponding places in the two representations.
2323     For the case of basic_filebuf&lt;char&gt;, when no translation is needed,
2324     a single buffer suffices. A specialized filebuf can be used to reduce
2325     code space overhead when no locale has been imbued. Matt Austern's
2326     work at SGI will be useful, perhaps directly as a source of code, or
2327     at least as an example to draw on.
2328
2329     Filebuf, almost uniquely (cf. operator new), depends heavily on
2330     underlying environmental facilities. In current releases iostream
2331     depends fairly heavily on libio constant definitions, but it should
2332     be made independent.  It also depends on operating system primitives
2333     for file operations. There is immense room for optimizations using
2334     (e.g.) mmap for reading. The shadow/ directory wraps, besides the
2335     standard C headers, the libio.h and unistd.h headers, for use mainly
2336     by filebuf. These wrappings have not been completed, though there
2337     is scaffolding in place.
2338
2339     The encapsulation of certain C header &lt;cstdio&gt; names presents an
2340     interesting problem. It is possible to define an inline std::fprintf()
2341     implemented in terms of the 'extern "C"' vfprintf(), but there is no
2342     standard vfscanf() to use to implement std::fscanf(). It appears that
2343     vfscanf but be re-implemented in C++ for targets where no vfscanf
2344     extension has been defined. This is interesting in that it seems
2345     to be the only significant case in the C library where this kind of
2346     rewriting is necessary. (Of course Glibc provides the vfscanf()
2347     extension.)  (The functions related to exit() must be rewritten
2348     for other reasons.)
2349
2350
2351     Annex D
2352     -------
2353     Headers: &lt;strstream&gt;
2354
2355     Annex D defines many non-library features, and many minor
2356     modifications to various headers, and a complete header.
2357     It is "mostly done", except that the libstdc++-2 &lt;strstream&gt;
2358     header has not been adopted into the library, or checked to
2359     verify that it matches the draft in those details that were
2360     clarified by the committee. Certainly it must at least be
2361     moved into the std namespace.
2362
2363     We still need to wrap all the deprecated features in #if guards
2364     so that pedantic compile modes can detect their use.
2365
2366     Nonstandard Extensions
2367     ----------------------
2368     Headers: &lt;iostream.h&gt; &lt;strstream.h&gt; &lt;hash&gt; &lt;rbtree&gt;
2369     &lt;pthread_alloc&gt; &lt;stdiobuf&gt; (etc.)
2370
2371     User code has come to depend on a variety of nonstandard components
2372     that we must not omit. Much of this code can be adopted from
2373     libstdc++-v2 or from the SGI STL. This particularly includes
2374     &lt;iostream.h&gt;, &lt;strstream.h&gt;, and various SGI extensions such
2375     as &lt;hash_map.h&gt;. Many of these are already placed in the
2376     subdirectories ext/ and backward/. (Note that it is better to
2377     include them via "&lt;backward/hash_map.h&gt;" or "&lt;ext/hash_map&gt;" than
2378     to search the subdirectory itself via a "-I" directive.
2379   </literallayout>
2380 </sect1>
2381
2382 </appendix>