[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / doc / xml / manual / extensions.xml

<?xml version='1.0'?>
<!DOCTYPE part PUBLIC "-//OASIS//DTD DocBook XML V4.5//EN" 
 "http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd" 
[ ]>

<part id="manual.ext" xreflabel="Extensions">
<?dbhtml filename="extensions.html"?>
 
<partinfo>
  <keywordset>
    <keyword>
      ISO C++
    </keyword>
    <keyword>
      library
    </keyword>
  </keywordset>
</partinfo>

<title>
  Extensions
  <indexterm><primary>Extensions</primary></indexterm>
</title>

<preface>
  <title></title>
<para>
  Here we will make an attempt at describing the non-Standard extensions to
  the library.  Some of these are from SGI's STL, some of these are GNU's,
  and some just seemed to appear on the doorstep.
</para>
<para><emphasis>Before</emphasis> you leap in and use any of these
extensions, be aware of two things:
</para>
<orderedlist>
   <listitem>
     <para>
     Non-Standard means exactly that.  
     </para>
     <para>
       The behavior, and the very
       existence, of these extensions may change with little or no
       warning.  (Ideally, the really good ones will appear in the next
       revision of C++.)  Also, other platforms, other compilers, other
       versions of g++ or libstdc++ may not recognize these names, or
       treat them differently, or... 
     </para>
   </listitem>
   <listitem>
     <para>
       You should know how to <ulink url="XXX">access
       these headers properly</ulink>. 
     </para>
   </listitem>
</orderedlist>
</preface>

<!-- Chapter 01 : Compile Time Checks -->
<chapter id="manual.ext.compile_checks" xreflabel="Compile Time Checks">
<?dbhtml filename="ext_compile_checks.html"?>
  <title>Compile Time Checks</title>
  <para>
    Also known as concept checking.
  </para>
   <para>In 1999, SGI added <emphasis>concept checkers</emphasis> to their implementation
      of the STL:  code which checked the template parameters of
      instantiated pieces of the STL, in order to insure that the parameters
      being used met the requirements of the standard.  For example,
      the Standard requires that types passed as template parameters to
      <code>vector</code> be <quote>Assignable</quote> (which means what you think
      it means).  The checking was done during compilation, and none of
      the code was executed at runtime.
   </para>
   <para>Unfortunately, the size of the compiler files grew significantly
      as a result.  The checking code itself was cumbersome.  And bugs
      were found in it on more than one occasion.
   </para>
   <para>The primary author of the checking code, Jeremy Siek, had already
      started work on a replacement implementation.  The new code has been
      formally reviewed and accepted into
      <ulink url="http://www.boost.org/libs/concept_check/concept_check.htm">the
      Boost libraries</ulink>, and we are pleased to incorporate it into the
      GNU C++ library.
   </para>
   <para>The new version imposes a much smaller space overhead on the generated
      object file.  The checks are also cleaner and easier to read and
      understand.
   </para>
   <para>They are off by default for all versions of GCC from 3.0 to 3.4 (the
      latest release at the time of writing).
      They can be enabled at configure time with
      <ulink url="../configopts.html"><literal>--enable-concept-checks</literal></ulink>.
      You can enable them on a per-translation-unit basis with
      <code>#define _GLIBCXX_CONCEPT_CHECKS</code> for GCC 3.4 and higher
      (or with <code>#define _GLIBCPP_CONCEPT_CHECKS</code> for versions
      3.1, 3.2 and 3.3).
   </para>

   <para>Please note that the upcoming C++ standard has first-class
   support for template parameter constraints based on concepts in the core
   language. This will obviate the need for the library-simulated concept
   checking described above.
   </para>

</chapter>

<!-- Chapter 02 : Debug Mode -->
<xi:include xmlns:xi="http://www.w3.org/2001/XInclude" 
            parse="xml" href="debug_mode.xml">
</xi:include>

<!-- Chapter 03 : Parallel Mode -->
<xi:include xmlns:xi="http://www.w3.org/2001/XInclude" 
            parse="xml" href="parallel_mode.xml">
</xi:include>

<!-- Chapter 04 : Allocators -->
<chapter id="manual.ext.allocator" xreflabel="Allocators">
<?dbhtml filename="ext_allocators.html"?>
  <title>Allocators</title>

  <!-- Section 01 : __mt_alloc -->
  <xi:include xmlns:xi="http://www.w3.org/2001/XInclude" 
              parse="xml" href="mt_allocator.xml">
  </xi:include>

  <!-- Section 02 : bitmap_allocator -->
  <xi:include xmlns:xi="http://www.w3.org/2001/XInclude" 
              parse="xml" href="bitmap_allocator.xml">
  </xi:include>

</chapter>

<!-- Chapter 05 : Containers -->
<chapter id="manual.ext.containers" xreflabel="Containers">
<?dbhtml filename="ext_containers.html"?>
  <title>Containers</title>
  <para>
  </para>
  <sect1 id="manual.ext.containers.pbds" xreflabel="Policy Based Data Structures">
    <title>Policy Based Data Structures</title>
    <para>
      <ulink
      url="http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html">More details here</ulink>.
    </para>
  </sect1>

  <sect1 id="manual.ext.containers.sgi" xreflabel="SGI ext">
    <title>HP/SGI</title>
    <para>
    </para>

<para>A few extensions and nods to backwards-compatibility have been made with
   containers.  Those dealing with older SGI-style allocators are dealt with
   elsewhere.  The remaining ones all deal with bits:
</para>
<para>The old pre-standard <code>bit_vector</code> class is present for
   backwards compatibility.  It is simply a typedef for the
   <code>vector&lt;bool&gt;</code> specialization.
</para>
<para>The <code>bitset</code> class has a number of extensions, described in the
   rest of this item.  First, we'll mention that this implementation of
   <code>bitset&lt;N&gt;</code> is specialized for cases where N number of
   bits will fit into a single word of storage.  If your choice of N is
   within that range (&lt;=32 on i686-pc-linux-gnu, for example), then all
   of the operations will be faster.
</para>
<para>There are
   versions of single-bit test, set, reset, and flip member functions which
   do no range-checking.  If we call them member functions of an instantiation
   of &quot;bitset&lt;N&gt;,&quot; then their names and signatures are:
</para>
   <programlisting>
   bitset&lt;N&gt;&amp;   _Unchecked_set   (size_t pos);
   bitset&lt;N&gt;&amp;   _Unchecked_set   (size_t pos, int val);
   bitset&lt;N&gt;&amp;   _Unchecked_reset (size_t pos);
   bitset&lt;N&gt;&amp;   _Unchecked_flip  (size_t pos);
   bool         _Unchecked_test  (size_t pos);
   </programlisting>
   <para>Note that these may in fact be removed in the future, although we have
   no present plans to do so (and there doesn't seem to be any immediate
   reason to).
</para>
<para>The semantics of member function <code>operator[]</code> are not specified 
   in the C++ standard.  A long-standing defect report calls for sensible
   obvious semantics, which are already implemented here:  <code>op[]</code>
   on a const bitset returns a bool, and for a non-const bitset returns a
   <code>reference</code> (a nested type).  However, this implementation does
   no range-checking on the index argument, which is in keeping with other
   containers' <code>op[]</code> requirements.  The defect report's proposed
   resolution calls for range-checking to be done.  We'll just wait and see...
</para>
<para>Finally, two additional searching functions have been added.  They return
   the index of the first &quot;on&quot; bit, and the index of the first
   &quot;on&quot; bit that is after <code>prev</code>, respectively:
</para>
   <programlisting>
   size_t _Find_first() const;
   size_t _Find_next (size_t prev) const;</programlisting>
<para>The same caveat given for the _Unchecked_* functions applies here also.
</para>
  </sect1>


  <sect1 id="manual.ext.containers.deprecated_sgi" xreflabel="SGI ext dep">
    <title>Deprecated HP/SGI</title>

   <para>
     The SGI hashing classes <classname>hash_set</classname> and
     <classname>hash_set</classname> have been deprecated by the
     unordered_set, unordered_multiset, unordered_map,
     unordered_multimap containers in TR1 and the upcoming C++0x, and
     may be removed in future releases.
   </para>

   <para>The SGI headers</para>
   <programlisting>
     &lt;hash_map&gt;
     &lt;hash_set&gt;
     &lt;rope&gt;
     &lt;slist&gt;
     &lt;rb_tree&gt;
   </programlisting>
   <para>are all here;
      <code>&lt;hash_map&gt;</code> and <code>&lt;hash_set&gt;</code>
      are deprecated but available as backwards-compatible extensions,
      as discussed further below.  <code>&lt;rope&gt;</code> is the
      SGI specialization for large strings (&quot;rope,&quot;
      &quot;large strings,&quot; get it? Love that geeky humor.)
      <code>&lt;slist&gt;</code> is a singly-linked list, for when the
      doubly-linked <code>list&lt;&gt;</code> is too much space
      overhead, and <code>&lt;rb_tree&gt;</code> exposes the red-black
      tree classes used in the implementation of the standard maps and
      sets.
   </para>
   <para>Each of the associative containers map, multimap, set, and multiset
      have a counterpart which uses a
      <ulink url="http://www.sgi.com/tech/stl/HashFunction.html">hashing
      function</ulink> to do the arranging, instead of a strict weak ordering
      function.  The classes take as one of their template parameters a
      function object that will return the hash value; by default, an
      instantiation of
      <ulink url="http://www.sgi.com/tech/stl/hash.html">hash</ulink>.
      You should specialize this functor for your class, or define your own,
      before trying to use one of the hashing classes.
   </para>
   <para>The hashing classes support all the usual associative container
      functions, as well as some extra constructors specifying the number
      of buckets, etc.
   </para>
   <para>Why would you want to use a hashing class instead of the
      <quote>normal</quote>implementations?  Matt Austern writes:
   </para>
   <blockquote>
     <para>
       <emphasis>[W]ith a well chosen hash function, hash tables
       generally provide much better average-case performance than
       binary search trees, and much worse worst-case performance.  So
       if your implementation has hash_map, if you don't mind using
       nonstandard components, and if you aren't scared about the
       possibility of pathological cases, you'll probably get better
       performance from hash_map.
     </emphasis>
     </para>
   </blockquote>

  </sect1>  
</chapter>

<!-- Chapter 06 : Utilities -->
<chapter id="manual.ext.util" xreflabel="Utilities">
<?dbhtml filename="ext_utilities.html"?>
  <title>Utilities</title>
  <para>
    The &lt;functional&gt; header contains many additional functors
    and helper functions, extending section 20.3.  They are
    implemented in the file stl_function.h:
  </para>
  <itemizedlist>
  <listitem>
  <para><code>identity_element</code> for addition and multiplication. * 
  </para>
  </listitem>
  <listitem>
    <para>The functor <code>identity</code>, whose <code>operator()</code>
      returns the argument unchanged. * 
  </para>
  </listitem>
  <listitem>
    <para>Composition functors <code>unary_function</code> and
      <code>binary_function</code>, and their helpers <code>compose1</code>
      and <code>compose2</code>. * 
    </para>
  </listitem>
  <listitem>
  <para><code>select1st</code> and <code>select2nd</code>, to strip pairs. * 
  </para>
  </listitem>
  <listitem><para><code>project1st</code> and <code>project2nd</code>. * </para></listitem>
  <listitem><para>A set of functors/functions which always return the same result.  They
      are <code>constant_void_fun</code>, <code>constant_binary_fun</code>,
      <code>constant_unary_fun</code>, <code>constant0</code>,
      <code>constant1</code>, and <code>constant2</code>. * </para></listitem>
  <listitem><para>The class <code>subtractive_rng</code>. * </para></listitem>
  <listitem><para>mem_fun adaptor helpers <code>mem_fun1</code> and
      <code>mem_fun1_ref</code> are provided for backwards compatibility. </para></listitem>
</itemizedlist>
<para>
  20.4.1 can use several different allocators; they are described on the
   main extensions page.
</para>
<para>
  20.4.3 is extended with a special version of
  <code>get_temporary_buffer</code> taking a second argument.  The
  argument is a pointer, which is ignored, but can be used to specify
  the template type (instead of using explicit function template
  arguments like the standard version does).  That is, in addition to
</para>
<programlisting>
get_temporary_buffer&lt;int&gt;(5);
</programlisting>

<para>
you can also use
</para>

<programlisting>
get_temporary_buffer(5, (int*)0);
</programlisting>
<para>
  A class <code>temporary_buffer</code> is given in stl_tempbuf.h. *
</para>
<para>
  The specialized algorithms of section 20.4.4 are extended with
  <code>uninitialized_copy_n</code>. *
</para>

</chapter>

<!-- Chapter 07 : Algorithms -->
<chapter id="manual.ext.algorithms" xreflabel="Algorithms">
<?dbhtml filename="ext_algorithms.html"?>
  <title>Algorithms</title>
<para>25.1.6 (count, count_if) is extended with two more versions of count
   and count_if.  The standard versions return their results.  The
   additional signatures return void, but take a final parameter by
   reference to which they assign their results, e.g.,
</para>
   <programlisting>
   void count (first, last, value, n);</programlisting>
<para>25.2 (mutating algorithms) is extended with two families of signatures,
   random_sample and random_sample_n.
</para>
<para>25.2.1 (copy) is extended with
</para>
   <programlisting>
   copy_n (_InputIter first, _Size count, _OutputIter result);</programlisting>
<para>which copies the first 'count' elements at 'first' into 'result'.
</para>
<para>25.3 (sorting 'n' heaps 'n' stuff) is extended with some helper
   predicates.  Look in the doxygen-generated pages for notes on these.
</para>
   <itemizedlist>
    <listitem><para><code>is_heap</code> tests whether or not a range is a heap.</para></listitem>
    <listitem><para><code>is_sorted</code> tests whether or not a range is sorted in
        nondescending order.</para></listitem>
   </itemizedlist>
<para>25.3.8 (lexicographical_compare) is extended with
</para>
   <programlisting>
   lexicographical_compare_3way(_InputIter1 first1, _InputIter1 last1,
                                 _InputIter2 first2, _InputIter2 last2)</programlisting>
<para>which does... what?
</para>

</chapter>

<!-- Chapter 08 : Numerics -->
<chapter id="manual.ext.numerics" xreflabel="Numerics">
<?dbhtml filename="ext_numerics.html"?>
  <title>Numerics</title>
<para>26.4, the generalized numeric operations such as accumulate, are extended
   with the following functions:
</para>
   <programlisting>
   power (x, n);
   power (x, n, moniod_operation);</programlisting>
<para>Returns, in FORTRAN syntax, &quot;x ** n&quot; where n&gt;=0.  In the
   case of n == 0, returns the <ulink url="#ch20">identity element</ulink> for the
   monoid operation.  The two-argument signature uses multiplication (for
   a true &quot;power&quot; implementation), but addition is supported as well.
   The operation functor must be associative.
</para>
<para>The <code>iota</code> function wins the award for Extension With the
   Coolest Name.  It &quot;assigns sequentially increasing values to a range.
   That is, it assigns value to *first, value + 1 to *(first + 1) and so
   on.&quot;  Quoted from SGI documentation.
</para>
   <programlisting>
   void iota(_ForwardIter first, _ForwardIter last, _Tp value);</programlisting>
</chapter>

<!-- Chapter 09 : Iterators -->
<chapter id="manual.ext.iterators" xreflabel="Iterators">
<?dbhtml filename="ext_iterators.html"?>
  <title>Iterators</title>
<para>24.3.2 describes <code>struct iterator</code>, which didn't exist in the
   original HP STL implementation (the language wasn't rich enough at the
   time).  For backwards compatibility, base classes are provided which
   declare the same nested typedefs:
</para>
   <itemizedlist>
    <listitem><para>input_iterator</para></listitem>
    <listitem><para>output_iterator</para></listitem>
    <listitem><para>forward_iterator</para></listitem>
    <listitem><para>bidirectional_iterator</para></listitem>
    <listitem><para>random_access_iterator</para></listitem>
   </itemizedlist>
<para>24.3.4 describes iterator operation <code>distance</code>, which takes
   two iterators and returns a result.  It is extended by another signature
   which takes two iterators and a reference to a result.  The result is
   modified, and the function returns nothing.
</para>

</chapter>

<!-- Chapter 08 : IO -->
<chapter id="manual.ext.io" xreflabel="IO">
<?dbhtml filename="ext_io.html"?>
  <title>Input and Output</title>

  <para>
    Extensions allowing <code>filebuf</code>s to be constructed from
    "C" types like  FILE*s and file descriptors.
  </para>

  <sect1 id="manual.ext.io.filebuf_derived" xreflabel="Derived filebufs">
    <title>Derived filebufs</title>

   <para>The v2 library included non-standard extensions to construct
      <code>std::filebuf</code>s from C stdio types such as
      <code>FILE*</code>s and POSIX file descriptors.
      Today the recommended way to use stdio types with libstdc++
      IOStreams is via the <code>stdio_filebuf</code> class (see below),
      but earlier releases provided slightly different mechanisms.
   </para>
   <itemizedlist>
     <listitem><para>3.0.x <code>filebuf</code>s have another ctor with this signature:
        <code>basic_filebuf(__c_file_type*, ios_base::openmode, int_type);
        </code>
         This comes in very handy in a number of places, such as
         attaching Unix sockets, pipes, and anything else which uses file
         descriptors, into the IOStream buffering classes.  The three
         arguments are as follows:
         <itemizedlist>
          <listitem><para><code>__c_file_type*      F   </code>
              // the __c_file_type typedef usually boils down to stdio's FILE
          </para></listitem>
          <listitem><para><code>ios_base::openmode  M   </code>
              // same as all the other uses of openmode
          </para></listitem>
          <listitem><para><code>int_type            B   </code>
              // buffer size, defaults to BUFSIZ if not specified
          </para></listitem>
         </itemizedlist>
         For those wanting to use file descriptors instead of FILE*'s, I
         invite you to contemplate the mysteries of C's <code>fdopen()</code>.
     </para></listitem>
     <listitem><para>In library snapshot 3.0.95 and later, <code>filebuf</code>s bring
         back an old extension:  the <code>fd()</code> member function.  The
         integer returned from this function can be used for whatever file
         descriptors can be used for on your platform.  Naturally, the
         library cannot track what you do on your own with a file descriptor,
         so if you perform any I/O directly, don't expect the library to be
         aware of it.
     </para></listitem>
     <listitem><para>Beginning with 3.1, the extra <code>filebuf</code> constructor and
         the <code>fd()</code> function were removed from the standard
         filebuf.  Instead, <code>&lt;ext/stdio_filebuf.h&gt;</code> contains
         a derived class called
         <ulink url="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00063.html"><code>__gnu_cxx::stdio_filebuf</code></ulink>.
         This class can be constructed from a C <code>FILE*</code> or a file
         descriptor, and provides the <code>fd()</code> function.
     </para></listitem>
   </itemizedlist>
   <para>If you want to access a <code>filebuf</code>'s file descriptor to
      implement file locking (e.g. using the <code>fcntl()</code> system
      call) then you might be interested in Henry Suter's
      <ulink url="http://suter.home.cern.ch/suter/RWLock.html">RWLock</ulink>
      class.
   </para>

    <para>
    </para>
  </sect1>
</chapter>

<!-- Chapter 09 : Demangling -->
<chapter id="manual.ext.demangle" xreflabel="Demangling">
<?dbhtml filename="ext_demangling.html"?>
  <title>Demangling</title>
  <para>
    Transforming C++ ABI identifiers (like RTTI symbols) into the
    original C++ source identifiers is called
    <quote>demangling.</quote>
  </para>
  <para>
    If you have read the <ulink
    url="http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/namespaceabi.html">source
    documentation for <code>namespace abi</code></ulink> then you are
    aware of the cross-vendor C++ ABI in use by GCC.  One of the
    exposed functions is used for demangling,
    <code>abi::__cxa_demangle</code>.
  </para>
  <para>
    In programs like <command>c++filt</command>, the linker, and other tools
    have the ability to decode C++ ABI names, and now so can you.
  </para>
  <para>
    (The function itself might use different demanglers, but that's the
    whole point of abstract interfaces.  If we change the implementation,
    you won't notice.)
  </para>
  <para>
    Probably the only times you'll be interested in demangling at runtime
    are when you're seeing <code>typeid</code> strings in RTTI, or when
    you're handling the runtime-support exception classes.  For example:
  </para>
   <programlisting>
#include &lt;exception&gt;
#include &lt;iostream&gt;
#include &lt;cxxabi.h&gt;

struct empty { };

template &lt;typename T, int N&gt;
  struct bar { };


int main()
{
  int     status;
  char   *realname;

  // exception classes not in &lt;stdexcept&gt;, thrown by the implementation
  // instead of the user
  std::bad_exception  e;
  realname = abi::__cxa_demangle(e.what(), 0, 0, &amp;status);
  std::cout &lt;&lt; e.what() &lt;&lt; "\t=&gt; " &lt;&lt; realname &lt;&lt; "\t: " &lt;&lt; status &lt;&lt; '\n';
  free(realname);


  // typeid
  bar&lt;empty,17&gt;          u;
  const std::type_info  &amp;ti = typeid(u);

  realname = abi::__cxa_demangle(ti.name(), 0, 0, &amp;status);
  std::cout &lt;&lt; ti.name() &lt;&lt; "\t=&gt; " &lt;&lt; realname &lt;&lt; "\t: " &lt;&lt; status &lt;&lt; '\n';
  free(realname);

  return 0;
}
   </programlisting>
   <para>
     This prints
   </para>

   <screen>
   <computeroutput>
      St13bad_exception       =&gt; std::bad_exception   : 0
      3barI5emptyLi17EE       =&gt; bar&lt;empty, 17&gt;       : 0 
   </computeroutput>
   </screen>

   <para>
     The demangler interface is described in the source documentation
     linked to above.  It is actually written in C, so you don't need to
     be writing C++ in order to demangle C++.  (That also means we have to
     use crummy memory management facilities, so don't forget to free()
     the returned char array.)
   </para>
</chapter>

<!-- Chapter 10 : Concurrency -->
<xi:include xmlns:xi="http://www.w3.org/2001/XInclude" 
            parse="xml" href="concurrency.xml">
</xi:include>

</part>