This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3] pb_ds docbook
- From: Benjamin Kosnik <bkoz at redhat dot com>
- To: libstdc++ at gcc dot gnu dot org
- Date: Fri, 10 Jun 2011 10:15:16 -0700
- Subject: [v3] pb_ds docbook
.... well, almost. Here's the WIP.
-benjamin
Index: doc/xml/manual/mt_allocator.xml
===================================================================
--- doc/xml/manual/mt_allocator.xml (revision 174917)
+++ doc/xml/manual/mt_allocator.xml (working copy)
@@ -1,8 +1,8 @@
-<section xmlns="http://docbook.org/ns/docbook"; version="5.0"
+<chapter xmlns="http://docbook.org/ns/docbook"; version="5.0"
xml:id="manual.ext.allocator.mt" xreflabel="mt allocator">
<?dbhtml filename="mt_allocator.html"?>
-<info><title>mt_allocator</title>
+<info><title>The mt_allocator</title>
<keywordset>
<keyword>
ISO C++
@@ -552,4 +552,4 @@
</section>
-</section>
+</chapter>
Index: doc/xml/manual/bitmap_allocator.xml
===================================================================
--- doc/xml/manual/bitmap_allocator.xml (revision 174917)
+++ doc/xml/manual/bitmap_allocator.xml (working copy)
@@ -1,8 +1,8 @@
-<section xmlns="http://docbook.org/ns/docbook"; version="5.0"
+<chapter xmlns="http://docbook.org/ns/docbook"; version="5.0"
xml:id="manual.ext.allocator.bitmap" xreflabel="bitmap_allocator">
<?dbhtml filename="bitmap_allocator.html"?>
-<info><title>bitmap_allocator</title>
+<info><title>The bitmap_allocator</title>
<keywordset>
<keyword>
ISO C++
@@ -558,4 +558,4 @@
</section>
-</section>
+</chapter>
Index: doc/xml/manual/policy_based_data_structures.xml
===================================================================
--- doc/xml/manual/policy_based_data_structures.xml (revision 0)
+++ doc/xml/manual/policy_based_data_structures.xml (revision 0)
@@ -0,0 +1,652 @@
+<chapter xmlns="http://docbook.org/ns/docbook"; version="5.0"
+ xml:id="manual.ext.containers.pbds" xreflabel="PBDS">
+<info>
+ <title>Policy-Based Data Structures</title>
+ <keywordset>
+ <keyword>
+ ISO C++
+ </keyword>
+ <keyword>
+ policy
+ </keyword>
+ <keyword>
+ container
+ </keyword>
+ <keyword>
+ associated
+ </keyword>
+ <keyword>
+ tree
+ </keyword>
+ <keyword>
+ trie
+ </keyword>
+ <keyword>
+ hash
+ </keyword>
+ <keyword>
+ metaprogramming
+ </keyword>
+ </keywordset>
+</info>
+<?dbhtml filename="policy_based_data_structures.html"?>
+
+<!-- 2006-04-01 Ami Tavory -->
+<!-- 2011-05-25 Benjamin Kosnik -->
+
+<section xml:id="pbds.intro">
+<info><title>Intro</title></info>
+
+<para>
+ This is a library of policy-based elementary data structures:
+ associative containers and priority queues. It is designed for
+ high-performance, flexibility, semantic safety, and conformance to
+ the corresponding containers in <literal>std</literal> and
+ <literal>std::tr1</literal> (except for some points where it differs
+ by design).
+</para>
+
+<para>
+ Written by Ami Tavory and Vladimir Dreizin (IBM Haifa Research
+ Laboratories), and Benjamin Kosnik (Red Hat).
+</para>
+<para>
+</para>
+
+<section xml:id="pbds.intro.issues">
+<info><title>Problems and Issues</title></info>
+<para>
+</para>
+
+<para>
+ This section describes what problems the library attempts to
+ solve.
+</para>
+
+<para>
+ An attempt is made to categorize the wide variety of possible
+ container designs in terms of performance-impacting factors. These
+ performance factors are translated into design policies and
+ incorporated into container design.
+</para>
+
+<para>
+ There is tension between unravelling factors into a coherent set of
+ policies. Every attempt is made to make a minimal set of
+ factors. However, in many cases multiple factors make for long
+ template names. Every attempt is made to alias and use typedefs in
+ the source files, but the generated names for external symbols can
+ be large for binary files or debuggers.
+</para>
+
+<para>
+ In many cases, the longer names allow capabilities and behaviours
+ controlled by macros to also be unamibiguously emitted as distinct
+ generated names.
+</para>
+
+<para>
+ Specific issues found while unraveling performance factors in the
+ design of associative containers and priority queues follow.
+</para>
+
+<section xml:id="pbds.intro.issues.associative">
+<info><title>Associative Container Performance Factors</title></info>
+
+<para>
+ Associative containers depend on their composite policies to a very
+ large extent. Implicitly hard-wiring policies can hamper their
+ performance and limit their functionality. An efficient hash-based
+ container, for example, requires policies for testing key
+ equivalence, hashing keys, translating hash values into positions
+ within the hash table, and determining when and how to resize the
+ table internally. A tree-based container can efficiently support
+ order statistics, i.e. the ability to query what is the order of
+ each key within the sequence of keys in the container, but only if
+ the container is supplied with a policy to internally update
+ meta-data. There are many other such examples.
+</para>
+
+<para>
+ Ideally, all associative containers would share the same
+ interface. Unfortunately, underlying data structures and mapping
+ semantics differentiate between different containers. For example,
+ suppose one writes a generic function manipulating an associative
+ container.
+</para>
+
+<programlisting>
+template<typename Cntnr>
+ void
+ some_op_sequence(Cntnr& r_cnt)
+ {
+ ...
+ }
+</programlisting>
+
+<para>
+ Given this, then what can one assume about the instantiating
+ container? The answer varies according to its underlying data
+ structure. If the underlying data structure of
+ <literal>Cntnr</literal> is based on a tree or trie, then the order
+ of elements is well defined; otherwise, it is not, in general. If
+ the underlying data structure of <literal>Cntnr</literal> is based
+ on a collision-chaining hash table, then modifying
+ r_<literal>Cntnr</literal> will not invalidate its iterators' order;
+ if the underlying data structure is a probing hash table, then this
+ is not the case. If the underlying data structure is based on a tree
+ or trie, then a reference to the container can efficiently be split;
+ otherwise, it cannot, in general. If the underlying data structure
+ is a red-black tree, then splitting a reference to the container is
+ exception-free; if it is an ordered-vector tree, exceptions can be
+ thrown.
+</para>
+
+</section>
+
+<section xml:id="pbds.intro.issues.priority_queue">
+<info><title>Priority Que Performance Factors</title></info>
+
+<para>
+ Priority queues are useful when one needs to efficiently access a
+ minimum (or maximum) value as the set of values changes.
+</para>
+
+<para>
+ Most useful data structures for priority queues have a relatively
+ simple structure, as they are geared toward relatively simple
+ requirements. Unfortunately, these structures do not support access
+ to an arbitrary value, which turns out to be necessary in many
+ algorithms. Say, decreasing an arbitrary value in a graph
+ algorithm. Therefore, some extra mechanism is necessary and must be
+ invented for accessing arbitrary values. There are at least two
+ alternatives: embedding an associative container in a priority
+ queue, or allowing cross-referencing through iterators. The first
+ solution adds significant overhead; the second solution requires a
+ precise definition of iterator invalidation. Which is the next
+ point...
+</para>
+
+<para>
+ Priority queues, like hash-based containers, store values in an
+ order that is meaningless and undefined externally. For example, a
+ <code>push</code> operation can internally reorganize the
+ values. Because of this characteristic, describing a priority
+ queues' iterator is difficult: on one hand, the values to which
+ iterators point can remain valid, but on the other, the logical
+ order of iterators can change unpredictably.
+</para>
+
+<para>
+ Roughly speaking, any element that is both inserted to a priority
+ queue (e.g. through <code>push</code>) and removed
+ from it (e.g., through <code>pop</code>), incurs a
+ logarithmic overhead (in the amortized sense). Different underlying
+ data structures place the actual cost differently: some are
+ optimized for amortized complexity, whereas others guarantee that
+ specific operations only have a constant cost. One underlying data
+ structure might be chosen if modifying a value is frequent
+ (Dijkstra's shortest-path algorithm), whereas a different one might
+ be chosen otherwise. Unfortunately, an array-based binary heap - an
+ underlying data structure that optimizes (in the amortized sense)
+ <code>push</code> and <code>pop</code> operations, differs from the
+ others in terms of its invalidation guarantees. Other design
+ decisions also impact the cost and placement of the overhead, at the
+ expense of more difference in the the kinds of operations that the
+ underlying data structure can support. These differences pose a
+ challenge when creating a uniform interface for priority queues.
+</para>
+</section>
+</section>
+
+<section xml:id="pbds.intro.motivation">
+<info><title>Solutions, Motivation</title></info>
+<para>
+</para>
+<!-- motivation.html -->
+</section>
+
+
+</section>
+
+
+<section xml:id="containers.pbds.using">
+<info><title>Using</title></info>
+<para></para>
+
+<section xml:id="pbds.using.prereq">
+<info><title>Prerequisites</title></info>
+
+<para>The library contains only header files, and does not require any
+other libraries except the standard C++ library . All classes are
+defined in namespace <code>__gnu_pbds</code>. The library internally
+uses macros beginning with <code>PB_DS</code>, but
+<code>#undef</code>s anything it <code>#define</code>s (except for
+header guards). Compiling the library in an environment where macros
+beginning in <code>PB_DS</code> are defined, may yield unpredictable
+results in compilation, execution, or both.</para>
+
+<para>
+Further dependencies are necessary to create the visual output for the
+performance tests. To create these graphs, two additional packages
+will be needed: <command>pychart</command> and <command>Beautiful
+Soup</command>.
+</para>
+</section>
+
+<section xml:id="pbds.using.tutorial">
+<info><title>Tutorial</title></info>
+
+<section xml:id="pbds.using.tutorial.basic">
+<info><title>Basic Use</title></info>
+
+<para>
+ For the most part, the policy-based containers containers in
+ namespace <literal>__gnu_pbds</literal> have the same interface as
+ the equivalent containers in the standard C++ library, except for
+ the names used for the container classes themselves. For example,
+ this shows basic operations on a collision-chaining hash-based
+ container:
+</para>
+<programlisting>
+#include <ext/pb_ds/assoc_container.h>
+
+int main()
+{
+ __gnu_pbds::cc_hash_table<int, char> c;
+ c[2] = 'b';
+ assert(c.find(1) == c.end());
+};
+</programlisting>
+
+<para>
+ The container is called
+ <classname>__gnu_pbds::cc_hash_table</classname> instead of
+ <classname>std::unordered_map</classname>, since <quote>unordered
+ map</quote> does not necessarily mean a hash-based map as implied by
+ the C++ library (C++0x or TR1). For example, list-based associative
+ containers, which are very useful for the construction of
+ "multimaps," are also unordered.
+</para>
+
+<!--- Associative-Container Performance Tests::Observations::Mapping-Semantics
+ Considerations
+-->
+
+<para>This snippet shows a red-black tree based container:</para>
+
+<programlisting>
+#include <ext/pb_ds/assoc_container.h>
+
+int main()
+{
+ __gnu_pbds::tree<int, char> c;
+ c[2] = 'b';
+ assert(c.find(2) != c.end());
+};
+</programlisting>
+
+ <para>The container is called <classname>tree</classname> instead of
+ <classname>map</classname> since the underlying data structures are
+ being named with specificity.
+ </para>
+
+<para>
+ The member function naming convention is to strive to be the same as
+ the equivalent member functions in other C++ standard library
+ containers. The familiar methods are unchanged:
+ <function>begin</function>, <function>end</function>,
+ <function>size</function>, <function>empty</function>, and
+ <function>clear</function>.
+</para>
+
+<para>
+ This isn't to say that things are exactly as one would expect, given
+ the container requirments and interfaces in the C++ standard.
+</para>
+
+<para>
+ The names of containers' policies and policy accessors are
+ different then the usual. For example, if <type>hash_type</type> is
+some type of hash-based container, then</para>
+
+<programlisting>
+hash_type::hash_fn
+</programlisting>
+
+<para>
+gives the type of its hash functor, and if <varname>obj</varname> is
+some hash-based container object, then
+</para>
+
+<programlisting>
+obj.get_hash_fn()
+</programlisting>
+
+<para>will return a reference to its hash-functor object.</para>
+
+
+<para>
+ Similarly, if <type>tree_type</type> is some type of tree-based
+ container, then
+</para>
+
+<programlisting>
+tree_type::cmp_fn
+</programlisting>
+
+<para>
+gives the type of its comparison functor, and if <varname>obj</varname> is
+some tree-based container object, then
+</para>
+
+<programlisting>
+obj.get_cmp_fn()
+</programlisting>
+
+<para>will return a reference to its comparison-functor object.</para>
+
+<para>
+ It would be nice to give names consistent with those in the existing
+ C++ standard (inclusive of TR1). Unfortunately, these standard
+ containers don't consistently name types and methods. For example,
+ <classname>std::tr1::unordered_map</classname> uses
+ <type>hasher</type> for the hash functor, but
+ <classname>std::map</classname> uses <type>key_compare</type> for
+ the comparison functor. Also, we could not find an accessor for
+ <classname>std::tr1::unordered_map</classname>'s hash functor, but
+ <classname>std::map</classname> uses <classname>compare</classname>
+ for accessing the comparison functor.
+</para>
+
+<para>
+ Instead, <literal>__gnu_pbds</literal> attempts to be internally
+ consistent, and uses standard-derived terminology if possible.
+</para>
+
+<para>
+ Another source of difference is in scope:
+ <literal>__gnu_pbds</literal> contains more types of associative
+ containers than the standard C++ library, and more opportunities
+ to configure these new containers, since different types of
+ associative containers are useful in different settings.
+</para>
+
+<para>
+ Namespace <literal>__gnu_pbds</literal> contains different classes for
+ hash-based containers, tree-based containers, trie-based containers,
+ and list-based containers.
+</para>
+
+<!--
+ interface.html
+-->
+
+<!--
+ Design
+ hash_based_containers.html
+ tree_based_containers.html
+ trie_based_containers.html
+ lu_based_containers.html
+-->
+<para>
+ Since associative containers share parts of their interface, they
+ are organized as a class hierarchy.
+</para>
+
+<!--
+ interface.html
+-->
+
+ <para>Each type or method is defined in the most-common ancestor
+ in which it makes sense.
+ </para>
+
+ <para>For example, all associative containers support iteration
+ expressed in the following form:
+ </para>
+
+<programlisting>
+ const_iterator
+ begin() const;
+
+ iterator
+ begin();
+
+ const_iterator
+ end() const;
+
+ iterator
+ end();
+</programlisting>
+
+ <para>
+ But not all containers contain or use hash functors. Yet, both
+ collision-chaining and (general) probing hash-based associative
+ containers have a hash functor, so
+ <classname>basic_hash_table</classname> contains the interface:
+ </para>
+
+<programlisting>
+ const hash_fn&
+ get_hash_fn() const;
+
+ hash_fn&
+ get_hash_fn();
+</programlisting>
+
+<para>
+ so all hash-based associative containers inherit the same
+ hash-functor accessor methods.
+</para>
+<!--
+ XXX ds_gen.html data structure genericity
+-->
+</section> <!--basic use -->
+
+<section xml:id="pbds.using.tutorial.configuring">
+<info><title>Configuring via template parameters</title></info>
+</section>
+
+<section xml:id="pbds.using.tutorial.traits">
+<info><title>Querying Containers' Attributes</title></info>
+</section>
+
+<section xml:id="pbds.using.tutorial.point_range_iteration">
+<info><title>Point and Range Iteration</title></info>
+</section>
+
+<section xml:id="pbds.using.tutorial.set_vs_map">
+<info><title>Distinguishing Between Maps and Sets</title></info>
+</section>
+
+
+</section>
+
+<section xml:id="pbds.using.concepts">
+<info><title>Concepts</title></info>
+
+<section xml:id="pbds.using.concepts.null_type">
+<info><title>Null Policy Classes</title></info>
+<para>
+ Associative containers are typically parametrized by various
+ policies. For example, a hash-based associative container is
+ parametrized by a hash-functor, transforming each key into an
+ non-negative numerical type. Each such value is then further mapped
+ into a position within the table. The mapping of a key into a
+ position within the table is therefore a two-step process.
+</para>
+<para>
+ In some cases, instantiations are redundant. For example, when the
+ keys are integers, it is possible to use a redundant hash policy,
+ which transforms each key into its value.
+</para>
+<para>
+ In some other cases, these policies are irrelevant. For example, a
+ hash-based associative container might transform keys into positions
+ within a table by a different method than the two-step method
+ described above. In such a case, the hash functor is simply
+ irrelevant.
+</para>
+
+<para>
+ When a policy is either redundant or irrelevant, it can be replaced
+ by <classname>null_type</classname>.
+</para>
+
+ <para>
+ For example, a <emphasis>set</emphasis> is an associative
+ container with one of its template parameters (the one for the
+ mapped type) replaced with <classname>null_type</classname>. Other
+ places simplifications are made possible with this technique
+ include node updates in tree and trie data structures, and hash
+ and probe functions for hash data structures.
+ </para>
+</section>
+
+<section xml:id="pbds.using.concepts.keys">
+<info><title>Primary and Secondary Keys and Associated Containers</title></info>
+<para>
+ There are no associative containers which
+ allow multiple values with equivalent keys (such as the standard C++
+ <classname>std::multimap</classname>, for example). Instead, one maps the
+ unique part of a key - the primary key, into an
+ associative-container of the (originally) non-unique parts of
+ the key - the secondary key. A primary associative-container is
+ an associative container of primary keys; a secondary
+ associative-container is an associative container of secondary
+ keys.
+</para>
+
+</section>
+
+<section xml:id="pbds.using.concepts.point_and_range">
+<info><title>Point and Range Iterators</title></info>
+
+ <para>
+ Iterator concepts are bifurcated in this design, and are
+ comprised of point-type and range-type iteration.
+ </para>
+
+ <para>
+ A point-type iterator is an iterator that refers to a specific
+ element as returned through an
+ associative-container's <function>find</function> method.
+ </para>
+
+ <para>
+ A range-type iterator is an iterator that is used to go over a
+ sequence of elements, as returned by a container's
+ <function>find</function> method.
+ </para>
+
+ <para>
+ A point-type method is a method that
+ returns a point-type iterator; a range-type method is a method
+ that returns a range-type iterator.
+ </para>
+
+ <para>For most containers, these types are synonymous; for
+ self-organizing containers, such as hash-based containers or
+ priority queues, these are inherently different (in any
+ implementation, including that of C++ standard library
+ components), but in this design, it is made explicit. They are
+ distinct types.
+ </para>
+
+</section>
+
+<section xml:id="pbds.using.concepts.invalidation">
+<info><title>Invalidation Guarantees</title></info>
+<para>
+If one manipulates a container object, then iterators previously
+obtained from it can be invalidated. In some cases a
+previously-obtained iterator cannot be de-referenced; in other cases,
+the iterator's next or previous element might have changed
+unpredictably. This corresponds exactly to the question whether a
+point-type or range-type iterator (see previous concept) is valid or
+not. In this design, one can query a container (in compile time) about
+its invalidation guarantees.
+</para>
+</section>
+
+</section>
+
+<section xml:id="pbds.using.associative">
+<info><title>Associative Containers Examples</title></info>
+<para></para>
+</section>
+
+<section xml:id="pbds.using.priority_queue">
+<info><title>Priority Queue Examples</title></info>
+<para></para>
+</section>
+
+
+
+</section>
+
+<section xml:id="containers.pbds.design">
+<info><title>Design</title></info>
+<para></para>
+
+<section xml:id="pbds.design.genericity_and_interface">
+<info><title>Genericity and Interface</title></info>
+<para></para>
+</section>
+
+<section xml:id="pbds.design.associative">
+<info><title>Associative</title></info>
+<para></para>
+
+<section xml:id="pbds.design.associative.tree">
+<info><title>Tree</title></info>
+<para></para>
+</section>
+
+<section xml:id="pbds.design.associative.trie">
+<info><title>Trie</title></info>
+<para></para>
+</section>
+
+<section xml:id="pbds.design.associative.hash">
+<info><title>Hash</title></info>
+<para></para>
+</section>
+
+<section xml:id="pbds.design.associative.list">
+<info><title>List</title></info>
+<para></para>
+</section>
+
+</section>
+
+<section xml:id="pbds.design.priority_queue">
+<info><title>Priority Queue</title></info>
+<para></para>
+</section>
+
+</section>
+
+<section xml:id="pbds.test">
+<info><title>Testing</title></info>
+<para></para>
+
+<section xml:id="pbds.test.regression">
+<info><title>Regression</title></info>
+<para></para>
+</section>
+
+<section xml:id="pbds.test.performance">
+<info><title>Performance</title></info>
+<para></para>
+</section>
+
+</section>
+
+<section xml:id="pbds.biblio">
+<info><title>Bibliography</title></info>
+<para></para>
+</section>
+
+</chapter>
Index: doc/xml/manual/extensions.xml
===================================================================
--- doc/xml/manual/extensions.xml (revision 174917)
+++ doc/xml/manual/extensions.xml (working copy)
@@ -19,11 +19,11 @@
<preface><info><title/></info>
-
<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.
+ Here we will make an attempt at describing the non-Standard
+ extensions to the library. Some of these are from older versions of
+ standard library components, namely SGI's STL, and some of these are
+ GNU's.
</para>
<para><emphasis>Before</emphasis> you leap in and use any of these
extensions, be aware of two things:
@@ -100,59 +100,57 @@
</chapter>
<!-- Chapter 02 : Debug Mode -->
-<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml" href="debug_mode.xml">
+<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 xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml"
+ href="parallel_mode.xml">
</xi:include>
<!-- Chapter 04 : Profile Mode -->
-<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml" href="profile_mode.xml">
+<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml"
+ href="profile_mode.xml">
</xi:include>
-<!-- Chapter 05 : Allocators -->
-<chapter xml:id="manual.ext.allocator" xreflabel="Allocators"><info><title>Allocators</title></info>
-<?dbhtml filename="ext_allocators.html"?>
-
+<!-- XXX -->
+<!-- Allocators -->
+<!-- Chapter 06 : __mt_alloc -->
+<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml"
+ href="mt_allocator.xml">
+</xi:include>
- <!-- Section 01 : __mt_alloc -->
- <xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml" href="mt_allocator.xml">
- </xi:include>
+<!-- Chapter 07 : bitmap_allocator -->
+<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml"
+ href="bitmap_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>
+<!-- Containers -->
+<!-- Chapter 08 : Policy-Based Data Structures -->
+<xi:include xmlns:xi="http://www.w3.org/2001/XInclude"; parse="xml"
+ href="policy_based_data_structures.xml">
+</xi:include>
-</chapter>
-
-<!-- Chapter 06 : Containers -->
-<chapter xml:id="manual.ext.containers" xreflabel="Containers"><info><title>Containers</title></info>
+<!-- Chapter 09 : HP/SGI -->
+<chapter xml:id="manual.ext.containers" xreflabel="Containers">
+ <info><title>HP/SGI Extensions</title></info>
<?dbhtml filename="ext_containers.html"?>
- <para>
- </para>
- <section xml:id="manual.ext.containers.pbds" xreflabel="Policy Based Data Structures"><info><title>Policy Based Data Structures</title></info>
-
- <para>
- <link xmlns:xlink="http://www.w3.org/1999/xlink"; xlink:href="http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html";>More details here</link>.
- </para>
- </section>
+ <section xml:id="manual.ext.containers.sgi" xreflabel="SGI ext">
+ <info><title>Backwards Compatibility</title></info>
- <section xml:id="manual.ext.containers.sgi" xreflabel="SGI ext"><info><title>HP/SGI</title></info>
-
- <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<bool></code> specialization.
+ </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<bool></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<N></code> is specialized for cases where N number of
@@ -197,7 +195,7 @@
</section>
- <section xml:id="manual.ext.containers.deprecated_sgi" xreflabel="SGI ext dep"><info><title>Deprecated HP/SGI</title></info>
+ <section xml:id="manual.ext.containers.deprecated_sgi" xreflabel="SGI ext dep"><info><title>Deprecated</title></info>
<para>
Index: doc/Makefile.in
===================================================================
--- doc/Makefile.in (revision 174917)
+++ doc/Makefile.in (working copy)
@@ -384,6 +384,7 @@
${xml_dir}/manual/mt_allocator.xml \
${xml_dir}/manual/numerics.xml \
${xml_dir}/manual/parallel_mode.xml \
+ ${xml_dir}/manual/policy_based_data_structures.xml \
${xml_dir}/manual/prerequisites.xml \
${xml_dir}/manual/profile_mode.xml \
${xml_dir}/manual/shared_ptr.xml \
Index: doc/Makefile.am
===================================================================
--- doc/Makefile.am (revision 174917)
+++ doc/Makefile.am (working copy)
@@ -339,6 +339,7 @@
${xml_dir}/manual/mt_allocator.xml \
${xml_dir}/manual/numerics.xml \
${xml_dir}/manual/parallel_mode.xml \
+ ${xml_dir}/manual/policy_based_data_structures.xml \
${xml_dir}/manual/prerequisites.xml \
${xml_dir}/manual/profile_mode.xml \
${xml_dir}/manual/shared_ptr.xml \