[gcc r17-4812] libstdc++: Fix typos and grammar in pb_ds docs
Jonathan Wakely
redi@gcc.gnu.org
Thu Oct 1 12:34:58 GMT 2026
https://gcc.gnu.org/g:59815560554ed761522075ecbbf70071c746c08a
commit r17-4812-g59815560554ed761522075ecbbf70071c746c08a
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Thu Oct 1 13:14:49 2026 +0100
libstdc++: Fix typos and grammar in pb_ds docs
libstdc++-v3/ChangeLog:
* doc/xml/manual/policy_data_structures.xml: Fix typos and
grammar.
* doc/xml/manual/test_policy_data_structures.xml: Likewise.
* include/ext/pb_ds/tree_policy.hpp: Fix comment typo.
* include/ext/pb_ds/trie_policy.hpp: Likewise.
* doc/html/*: Regenerate.
Diff:
---
libstdc++-v3/doc/html/index.html | 2 +-
libstdc++-v3/doc/html/manual/extensions.html | 2 +-
libstdc++-v3/doc/html/manual/index.html | 2 +-
.../manual/policy_based_data_structures_test.html | 60 ++++----
.../doc/html/manual/policy_data_structures.html | 32 ++---
.../html/manual/policy_data_structures_design.html | 98 +++++++------
.../html/manual/policy_data_structures_using.html | 24 ++--
.../doc/xml/manual/policy_data_structures.xml | 152 ++++++++++-----------
.../doc/xml/manual/test_policy_data_structures.xml | 60 ++++----
libstdc++-v3/include/ext/pb_ds/tree_policy.hpp | 2 +-
libstdc++-v3/include/ext/pb_ds/trie_policy.hpp | 2 +-
11 files changed, 216 insertions(+), 220 deletions(-)
diff --git a/libstdc++-v3/doc/html/index.html b/libstdc++-v3/doc/html/index.html
index 874d4a234d62..270467eb0165 100644
--- a/libstdc++-v3/doc/html/index.html
+++ b/libstdc++-v3/doc/html/index.html
@@ -68,7 +68,7 @@
Extensions
</a></span></dt><dd><dl><dt><span class="preface"><a href="manual/ext_preface.html"></a></span></dt><dt><span class="chapter"><a href="manual/ext_compile_checks.html">17. Compile Time Checks</a></span></dt><dt><span class="chapter"><a href="manual/debug_mode.html">18. Debug Mode</a></span></dt><dd><dl><dt><span class="section"><a href="manual/debug_mode.html#manual.ext.debug_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="manual/debug_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="manual/debug_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="manual/debug_mode_using.html#debug_mode.using.mode">Using the Debug Mode</a></span></dt><dt><span class="section"><a href="manual/debug_mode_using.html#debug_mode.using.specific">Using a Specific Debug Container</a></span></dt></dl></dd><dt><span class="section"><a href="manual/debug_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.goals">Goals</a></span></dt><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.methods">Methods</a></span></dt><dd><dl><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.methods.wrappers">The Wrapper Model</a></span></dt><dd><dl><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.methods.safe_iter">Safe Iterators</a></span></dt><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.methods.safe_seq">Safe Sequences (Containers)</a></span></dt></dl></dd><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.methods.precond">Precondition Checking</a></span></dt><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.methods.coexistence">Release- and debug-mode coexistence</a></span></dt><dd><dl><dt><span class="section"><a href="manual/debug_mode_design.html#methods.coexistence.compile">Compile-time coexistence of release- and debug-mode components</a></span></dt><dt><span class="section"><a href="manual/debug_mode_design.html#methods.coexistence.link">Link- and run-time coexistence of release- and
- debug-mode components</a></span></dt><dt><span class="section"><a href="manual/debug_mode_design.html#methods.coexistence.alt">Alternatives for Coexistence</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.other">Other Implementations</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="manual/parallel_mode.html">19. Parallel Mode</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode.html#manual.ext.parallel_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode_using.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_using.html#parallel_mode.using.parallel_mode">Using Parallel Mode</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_using.html#parallel_mode.using.specific">Using Specific Parallel Components</a></span></dt></dl></dd><dt><span class="section"><a href="manual/parallel_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.intro">Interface Basics</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning">Configuration and Tuning</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning.compile">Compile Time Switches</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults</a></span></dt></dl></dd><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.impl">Implementation Namespaces</a></span></dt></dl></dd><dt><span class="section"><a href="manual/parallel_mode_test.html">Testing</a></span></dt><dt><span class="bibliography"><a href="manual/parallel_mode.html#parallel_mode.biblio">Bibliography</a></span></dt></dl></dd><dt><span class="chapter"><a href="manual/mt_allocator.html">20. The mt_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="manual/mt_allocator.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_design.html">Design Issues</a></span></dt><dd><dl><dt><span class="section"><a href="manual/mt_allocator_design.html#allocator.mt.overview">Overview</a></span></dt></dl></dd><dt><span class="section"><a href="manual/mt_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="manual/mt_allocator_impl.html#allocator.mt.tune">Tunable Parameters</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_impl.html#allocator.mt.init">Initialization</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_impl.html#allocator.mt.deallocation">Deallocation Notes</a></span></dt></dl></dd><dt><span class="section"><a href="manual/mt_allocator_ex_single.html">Single Thread Example</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_ex_multi.html">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="chapter"><a href="manual/bitmap_allocator.html">21. The bitmap_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="manual/bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="manual/policy_data_structures.html">22. Policy-Based Data Structures</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="manual/policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial.configuring">
+ debug-mode components</a></span></dt><dt><span class="section"><a href="manual/debug_mode_design.html#methods.coexistence.alt">Alternatives for Coexistence</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="manual/debug_mode_design.html#debug_mode.design.other">Other Implementations</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="manual/parallel_mode.html">19. Parallel Mode</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode.html#manual.ext.parallel_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode_using.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_using.html#parallel_mode.using.parallel_mode">Using Parallel Mode</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_using.html#parallel_mode.using.specific">Using Specific Parallel Components</a></span></dt></dl></dd><dt><span class="section"><a href="manual/parallel_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.intro">Interface Basics</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning">Configuration and Tuning</a></span></dt><dd><dl><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning.compile">Compile Time Switches</a></span></dt><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults</a></span></dt></dl></dd><dt><span class="section"><a href="manual/parallel_mode_design.html#parallel_mode.design.impl">Implementation Namespaces</a></span></dt></dl></dd><dt><span class="section"><a href="manual/parallel_mode_test.html">Testing</a></span></dt><dt><span class="bibliography"><a href="manual/parallel_mode.html#parallel_mode.biblio">Bibliography</a></span></dt></dl></dd><dt><span class="chapter"><a href="manual/mt_allocator.html">20. The mt_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="manual/mt_allocator.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_design.html">Design Issues</a></span></dt><dd><dl><dt><span class="section"><a href="manual/mt_allocator_design.html#allocator.mt.overview">Overview</a></span></dt></dl></dd><dt><span class="section"><a href="manual/mt_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="manual/mt_allocator_impl.html#allocator.mt.tune">Tunable Parameters</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_impl.html#allocator.mt.init">Initialization</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_impl.html#allocator.mt.deallocation">Deallocation Notes</a></span></dt></dl></dd><dt><span class="section"><a href="manual/mt_allocator_ex_single.html">Single Thread Example</a></span></dt><dt><span class="section"><a href="manual/mt_allocator_ex_multi.html">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="chapter"><a href="manual/bitmap_allocator.html">21. The bitmap_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="manual/bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="manual/bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="manual/policy_data_structures.html">22. Policy-Based Data Structures</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Queue</a></span></dt></dl></dd><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="manual/policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="manual/policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial.configuring">
Configuring via Template Parameters
</a></span></dt><dt><span class="section"><a href="manual/policy_data_structures_using.html#pbds.using.tutorial.traits">
Querying Container Attributes
diff --git a/libstdc++-v3/doc/html/manual/extensions.html b/libstdc++-v3/doc/html/manual/extensions.html
index 01682ad8d21c..3b20c3d5ce65 100644
--- a/libstdc++-v3/doc/html/manual/extensions.html
+++ b/libstdc++-v3/doc/html/manual/extensions.html
@@ -6,7 +6,7 @@
Extensions
<a id="id-1.3.5.1.1.1" class="indexterm"></a>
</h1></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="preface"><a href="ext_preface.html"></a></span></dt><dt><span class="chapter"><a href="ext_compile_checks.html">17. Compile Time Checks</a></span></dt><dt><span class="chapter"><a href="debug_mode.html">18. Debug Mode</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode.html#manual.ext.debug_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="debug_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="debug_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_using.html#debug_mode.using.mode">Using the Debug Mode</a></span></dt><dt><span class="section"><a href="debug_mode_using.html#debug_mode.using.specific">Using a Specific Debug Container</a></span></dt></dl></dd><dt><span class="section"><a href="debug_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.goals">Goals</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods">Methods</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.wrappers">The Wrapper Model</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.safe_iter">Safe Iterators</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.safe_seq">Safe Sequences (Containers)</a></span></dt></dl></dd><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.precond">Precondition Checking</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.coexistence">Release- and debug-mode coexistence</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.compile">Compile-time coexistence of release- and debug-mode components</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.link">Link- and run-time coexistence of release- and
- debug-mode components</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.alt">Alternatives for Coexistence</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.other">Other Implementations</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="parallel_mode.html">19. Parallel Mode</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode.html#manual.ext.parallel_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="parallel_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.parallel_mode">Using Parallel Mode</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.specific">Using Specific Parallel Components</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.intro">Interface Basics</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning">Configuration and Tuning</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.compile">Compile Time Switches</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.impl">Implementation Namespaces</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_test.html">Testing</a></span></dt><dt><span class="bibliography"><a href="parallel_mode.html#parallel_mode.biblio">Bibliography</a></span></dt></dl></dd><dt><span class="chapter"><a href="mt_allocator.html">20. The mt_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="section"><a href="mt_allocator_design.html">Design Issues</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_design.html#allocator.mt.overview">Overview</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.tune">Tunable Parameters</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.init">Initialization</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.deallocation">Deallocation Notes</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_ex_single.html">Single Thread Example</a></span></dt><dt><span class="section"><a href="mt_allocator_ex_multi.html">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="chapter"><a href="bitmap_allocator.html">21. The bitmap_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="policy_data_structures.html">22. Policy-Based Data Structures</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
+ debug-mode components</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.alt">Alternatives for Coexistence</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.other">Other Implementations</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="parallel_mode.html">19. Parallel Mode</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode.html#manual.ext.parallel_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="parallel_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.parallel_mode">Using Parallel Mode</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.specific">Using Specific Parallel Components</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.intro">Interface Basics</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning">Configuration and Tuning</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.compile">Compile Time Switches</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.impl">Implementation Namespaces</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_test.html">Testing</a></span></dt><dt><span class="bibliography"><a href="parallel_mode.html#parallel_mode.biblio">Bibliography</a></span></dt></dl></dd><dt><span class="chapter"><a href="mt_allocator.html">20. The mt_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="section"><a href="mt_allocator_design.html">Design Issues</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_design.html#allocator.mt.overview">Overview</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.tune">Tunable Parameters</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.init">Initialization</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.deallocation">Deallocation Notes</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_ex_single.html">Single Thread Example</a></span></dt><dt><span class="section"><a href="mt_allocator_ex_multi.html">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="chapter"><a href="bitmap_allocator.html">21. The bitmap_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="policy_data_structures.html">22. Policy-Based Data Structures</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Queue</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
Configuring via Template Parameters
</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits">
Querying Container Attributes
diff --git a/libstdc++-v3/doc/html/manual/index.html b/libstdc++-v3/doc/html/manual/index.html
index c19ecfe7947f..ef55b9d6c6a5 100644
--- a/libstdc++-v3/doc/html/manual/index.html
+++ b/libstdc++-v3/doc/html/manual/index.html
@@ -49,7 +49,7 @@
Extensions
</a></span></dt><dd><dl><dt><span class="preface"><a href="ext_preface.html"></a></span></dt><dt><span class="chapter"><a href="ext_compile_checks.html">17. Compile Time Checks</a></span></dt><dt><span class="chapter"><a href="debug_mode.html">18. Debug Mode</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode.html#manual.ext.debug_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="debug_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="debug_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_using.html#debug_mode.using.mode">Using the Debug Mode</a></span></dt><dt><span class="section"><a href="debug_mode_using.html#debug_mode.using.specific">Using a Specific Debug Container</a></span></dt></dl></dd><dt><span class="section"><a href="debug_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.goals">Goals</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods">Methods</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.wrappers">The Wrapper Model</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.safe_iter">Safe Iterators</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.safe_seq">Safe Sequences (Containers)</a></span></dt></dl></dd><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.precond">Precondition Checking</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.methods.coexistence">Release- and debug-mode coexistence</a></span></dt><dd><dl><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.compile">Compile-time coexistence of release- and debug-mode components</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.link">Link- and run-time coexistence of release- and
- debug-mode components</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.alt">Alternatives for Coexistence</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.other">Other Implementations</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="parallel_mode.html">19. Parallel Mode</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode.html#manual.ext.parallel_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="parallel_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.parallel_mode">Using Parallel Mode</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.specific">Using Specific Parallel Components</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.intro">Interface Basics</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning">Configuration and Tuning</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.compile">Compile Time Switches</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.impl">Implementation Namespaces</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_test.html">Testing</a></span></dt><dt><span class="bibliography"><a href="parallel_mode.html#parallel_mode.biblio">Bibliography</a></span></dt></dl></dd><dt><span class="chapter"><a href="mt_allocator.html">20. The mt_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="section"><a href="mt_allocator_design.html">Design Issues</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_design.html#allocator.mt.overview">Overview</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.tune">Tunable Parameters</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.init">Initialization</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.deallocation">Deallocation Notes</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_ex_single.html">Single Thread Example</a></span></dt><dt><span class="section"><a href="mt_allocator_ex_multi.html">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="chapter"><a href="bitmap_allocator.html">21. The bitmap_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="policy_data_structures.html">22. Policy-Based Data Structures</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
+ debug-mode components</a></span></dt><dt><span class="section"><a href="debug_mode_design.html#methods.coexistence.alt">Alternatives for Coexistence</a></span></dt></dl></dd></dl></dd><dt><span class="section"><a href="debug_mode_design.html#debug_mode.design.other">Other Implementations</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="parallel_mode.html">19. Parallel Mode</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode.html#manual.ext.parallel_mode.intro">Intro</a></span></dt><dt><span class="section"><a href="parallel_mode_semantics.html">Semantics</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.parallel_mode">Using Parallel Mode</a></span></dt><dt><span class="section"><a href="parallel_mode_using.html#parallel_mode.using.specific">Using Specific Parallel Components</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html">Design</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.intro">Interface Basics</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning">Configuration and Tuning</a></span></dt><dd><dl><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.compile">Compile Time Switches</a></span></dt><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_design.html#parallel_mode.design.impl">Implementation Namespaces</a></span></dt></dl></dd><dt><span class="section"><a href="parallel_mode_test.html">Testing</a></span></dt><dt><span class="bibliography"><a href="parallel_mode.html#parallel_mode.biblio">Bibliography</a></span></dt></dl></dd><dt><span class="chapter"><a href="mt_allocator.html">20. The mt_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="section"><a href="mt_allocator_design.html">Design Issues</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_design.html#allocator.mt.overview">Overview</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.tune">Tunable Parameters</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.init">Initialization</a></span></dt><dt><span class="section"><a href="mt_allocator_impl.html#allocator.mt.deallocation">Deallocation Notes</a></span></dt></dl></dd><dt><span class="section"><a href="mt_allocator_ex_single.html">Single Thread Example</a></span></dt><dt><span class="section"><a href="mt_allocator_ex_multi.html">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="chapter"><a href="bitmap_allocator.html">21. The bitmap_allocator</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html">Implementation</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.free_list_store">Free List Store</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block">Super Block</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.super_block_data">Super Block Data Layout</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.max_wasted">Maximum Wasted Percentage</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.allocate"><code class="function">allocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.deallocate"><code class="function">deallocate</code></a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.questions">Questions</a></span></dt><dd><dl><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.1">1</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.2">2</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.locality">Locality</a></span></dt><dt><span class="section"><a href="bitmap_allocator_impl.html#bitmap.impl.grow_policy">Overhead and Grow Policy</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="policy_data_structures.html">22. Policy-Based Data Structures</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Queue</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
Configuring via Template Parameters
</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits">
Querying Container Attributes
diff --git a/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html b/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html
index 5ca2baa96043..ffc5bab9eb20 100644
--- a/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html
+++ b/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html
@@ -13,13 +13,13 @@
applicable).</p><p>Additionally, the test integrally checks exception safety
and resource leaks. This is done as follows. A special
allocator type, written for the purpose of the test, both
- randomly throws an exceptions when allocations are performed,
+ randomly throws exceptions when allocations are performed,
and tracks allocations and de-allocations. The exceptions thrown
at allocations simulate memory-allocation failures; the
tracking mechanism checks for memory-related bugs (e.g.,
resource leaks and multiple de-allocations). Both
this library's containers and the containers' value-types are
- configured to use this allocator.</p><p>For granularity, the test is split into the
+ configured to use this allocator.</p><p>For granularity, the test is split into
several sources, each checking only some containers.</p><p>For more details, consult the files in
<code class="filename">testsuite/ext/pb_ds/regression</code>.
</p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.performance"></a>Performance</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.hash"></a>Hash-Based</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.text_find"></a>
@@ -30,7 +30,7 @@
This test inserts a number of values with keys from an
arbitrary text (<a class="xref" href="policy_data_structures.html#biblio.wickland96thirty" title="Thirty Years Among the Dead">[biblio.wickland96thirty]</a>) into a container,
then performs a series of finds using
- <code class="function">find</code> . It measures the average
+ <code class="function">find</code>. It measures the average
time for <code class="function">find</code> as a function of
the number of values inserted.</p><p>
It uses the test file:
@@ -42,7 +42,7 @@
functions, trigger policies, and cache-hashing policies.
</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for the native
+ </h6></div></div></div><p>The graphic below shows the results for the native
and collision-chaining hash types the function
applied being a text find timing test using
<code class="function">find</code>.
@@ -157,8 +157,8 @@
entry affects performance only marginally, at least in this
library's implementation. (Unfortunately, it was not possible to run
the tests with <code class="classname">std::tr1::unordered_map</code> 's
- <code class="classname">cache_hash_code = true</code> , as it appeared to
- malfuntion.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_find"></a>
+ <code class="classname">cache_hash_code = true</code>, as it appeared to
+ malfunction.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_find"></a>
Integer <code class="function">find</code>
</h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.info"></a>
Description
@@ -735,7 +735,7 @@
Observations
</h6></div></div></div><p>In this setting, as in Hash-Based Text
<code class="function">find</code> Find Timing test and Hash-Based
- Integer <code class="function">find</code> Find Timing test , the choice
+ Integer <code class="function">find</code> Find Timing test, the choice
of underlying hash-table underlying hash-table affects performance
most, then the range-hashing scheme, and
finally any other policies.</p><p>There are some differences, however:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>In this setting, probing tables function sometimes more
@@ -775,7 +775,7 @@
</p><p>The test checks the effect of different range-hashing
functions and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
+ </h6></div></div></div><p>The graphic below shows the results for the native, collision-chaining, and general-probing hash types.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_zlob_int_find.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
instantiated with the types in the following table.
@@ -895,7 +895,7 @@
</p><p>The test checks how containers adjust internally as their
logical size decreases.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
+ </h6></div></div></div><p>The graphic below shows the results for the native, collision-chaining, and general-probing hash types.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_int_erase_mem.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
instantiated with the types in the following table.
@@ -990,7 +990,7 @@
Description
</h6></div></div></div><p>This test inserts a number of values with keys from an arbitrary
text ([wickland96thirty]) into a container
- using <code class="function">insert</code> . It measures the average time
+ using <code class="function">insert</code>. It measures the average time
for <code class="function">insert</code> as a function of the number of
values inserted.</p><p>The test checks the effect of different underlying
data structures.</p><p>
@@ -1449,17 +1449,17 @@
</h6></div></div></div><p>In this test, the native red-black tree can support
order-statistics queries only externally, by performing a
<code class="classname">find</code> (alternatively, <code class="classname">lower_bound</code> or
- <code class="classname">upper_bound</code> ) and then using <code class="classname">std::distance</code> .
+ <code class="classname">upper_bound</code>) and then using <code class="classname">std::distance</code>.
This is clearly linear, and it is not that surprising that the
cost is high.</p><p>This library's tree-based containers use in this test the
<code class="classname">order_of_key</code> method of <code class="classname">tree_order_statistics_node_update</code>.
This method has only linear complexity in the length of the
root-node path. Unfortunately, the average path of a splay tree
(<code class="classname">tree</code>
- with <code class="classname">Tag =</code> <code class="classname">splay_tree_tag</code> ) can
+ with <code class="classname">Tag =</code> <code class="classname">splay_tree_tag</code>) can
be higher than logarithmic; the longest path of a red-black
tree (<code class="classname">tree</code>
- with <code class="classname">Tag =</code> <code class="classname">rb_tree_tag</code> ) is
+ with <code class="classname">Tag =</code> <code class="classname">rb_tree_tag</code>) is
logarithmic in the number of elements. Consequently, the splay
tree has worse performance than the red-black tree.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.multimap"></a>Multimap</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_small"></a>
Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios
@@ -1484,7 +1484,7 @@
</p><p>The test checks the find-time scalability of different
"multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for "multimaps" which
+ </h6></div></div></div><p>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_tree.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -1546,7 +1546,7 @@
</td><td align="left">
<code class="classname">hash_load_check_resize_trigger</code> with
α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
- </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
+ </td></tr></tbody></table></div><p>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -1655,7 +1655,7 @@
</p><p>The test checks the find-time scalability of different
"multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for "multimaps" which
+ </h6></div></div></div><p>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_tree.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -1717,7 +1717,7 @@
</td><td align="left">
<code class="classname">hash_load_check_resize_trigger</code> with
α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
- </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
+ </td></tr></tbody></table></div><p>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -1829,7 +1829,7 @@
</p><p>The test checks the insert-time scalability of different
"multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for "multimaps" which
+ </h6></div></div></div><p>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_small_s2p_tree.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -1891,7 +1891,7 @@
</td><td align="left">
<code class="classname">hash_load_check_resize_trigger</code> with
α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
- </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
+ </td></tr></tbody></table></div><p>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2003,7 +2003,7 @@
</p><p>The test checks the insert-time scalability of different
"multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for "multimaps" which
+ </h6></div></div></div><p>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_large_s2p_tree.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2065,7 +2065,7 @@
</td><td align="left">
<code class="classname">hash_load_check_resize_trigger</code> with
α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
- </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
+ </td></tr></tbody></table></div><p>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2172,7 +2172,7 @@
</p><p>The test checks the memory scalability of different
"multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for "multimaps" which
+ </h6></div></div></div><p>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_mem_small_s2p_tree.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2234,7 +2234,7 @@
</td><td align="left">
<code class="classname">hash_load_check_resize_trigger</code> with
α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
- </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
+ </td></tr></tbody></table></div><p>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2341,7 +2341,7 @@
</p><p>The test checks the memory scalability of different
"multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.results"></a>
Results
- </h6></div></div></div><p>The graphic below show the results for "multimaps" which
+ </h6></div></div></div><p>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_mem_large_s2p_tree.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2403,7 +2403,7 @@
</td><td align="left">
<code class="classname">hash_load_check_resize_trigger</code> with
α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2
- </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which
+ </td></tr></tbody></table></div><p>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p>
The abbreviated names in the legend of the graphic above are
@@ -2632,8 +2632,8 @@
Description
</h6></div></div></div><p>This test inserts a number of values with keys from an
arbitrary text ([ wickland96thirty ]) into
- a container using <code class="classname">push</code> , then removes them using
- <code class="classname">pop</code> . It measures the average time for <code class="classname">push</code>
+ a container using <code class="classname">push</code>, then removes them using
+ <code class="classname">pop</code>. It measures the average time for <code class="classname">push</code>
as a function of the number of values.</p><p>
It uses the test file:
<code class="filename">performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc</code>
@@ -2879,8 +2879,8 @@
</h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.info"></a>
Description
</h6></div></div></div><p>This test inserts a number of values with integer keys
- into a container using <code class="function">push</code> , then removes them
- using <code class="function">pop</code> . It measures the average time for
+ into a container using <code class="function">push</code>, then removes them
+ using <code class="function">pop</code>. It measures the average time for
<code class="function">push</code> and <code class="function">pop</code> as a function
of the number of values.</p><p>
It uses the test file:
@@ -3422,7 +3422,7 @@
byproduct of the tree-like structure is required: either
order-preservation, or the ability to utilize node invariants. If
memory-use is the major factor, an ordered-vector tree gives
- optimal results (albeit with high modificiation costs), and a
+ optimal results (albeit with high modification costs), and a
list-based container gives reasonable results.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash"></a>
Hash-Based Containers
</h6></div></div></div><p>Hash-based containers are typically either collision
diff --git a/libstdc++-v3/doc/html/manual/policy_data_structures.html b/libstdc++-v3/doc/html/manual/policy_data_structures.html
index 9dfe9685d53a..8f772fa536ee 100644
--- a/libstdc++-v3/doc/html/manual/policy_data_structures.html
+++ b/libstdc++-v3/doc/html/manual/policy_data_structures.html
@@ -2,7 +2,7 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 22. Policy-Based Data Structures</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, policy, container, data, structure, associated, tree, trie, hash, metaprogramming" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="extensions.html" title="Part III. Extensions" /><link rel="prev" href="bitmap_allocator_impl.html" title="Implementation" /><link rel="next" href="policy_data_structures_using.html" title="Using" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 22. Policy-Based Data Structures</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bitmap_allocator_impl.html">Prev</a> </td><th width="60%" align="center">Part III.
Extensions
-</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr></table><hr /></div><div class="chapter"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.containers.pbds"></a>Chapter 22. Policy-Based Data Structures</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Que</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
+</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_using.html">Next</a></td></tr></table><hr /></div><div class="chapter"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.containers.pbds"></a>Chapter 22. Policy-Based Data Structures</h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="section"><a href="policy_data_structures.html#pbds.intro">Intro</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues">Performance Issues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.associative">Associative</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.issues.priority_queue">Priority Queue</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation">Goals</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.associative">Associative</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.iterators">Iterators</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.associative.functions">Functional</a></span></dt></dl></dd><dt><span class="section"><a href="policy_data_structures.html#pbds.intro.motivation.priority_queue">Priority Queues</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.policy">Policy Choices</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.underlying">Underlying Data Structures</a></span></dt><dt><span class="section"><a href="policy_data_structures.html#motivation.priority_queue.binary_heap">Binary Heaps</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class="section"><a href="policy_data_structures_using.html">Using</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.prereq">Prerequisites</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.organization">Organization</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial">Tutorial</a></span></dt><dd><dl><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.basic">Basic Use</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.configuring">
Configuring via Template Parameters
</a></span></dt><dt><span class="section"><a href="policy_data_structures_using.html#pbds.using.tutorial.traits">
Querying Container Attributes
@@ -87,7 +87,7 @@
be large for binary files or debuggers.
</p><p>
In many cases, the longer names allow capabilities and behaviours
- controlled by macros to also be unamibiguously emitted as distinct
+ controlled by macros to also be unambiguously emitted as distinct
generated names.
</p><p>
Specific issues found while unraveling performance factors in the
@@ -133,7 +133,7 @@
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.
- </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.priority_queue"></a>Priority Que</h4></div></div></div><p>
+ </p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.issues.priority_queue"></a>Priority Queue</h4></div></div></div><p>
Priority queues are useful when one needs to efficiently access a
minimum (or maximum) value as the set of values changes.
</p><p>
@@ -259,7 +259,7 @@
</p><div class="figure"><a id="id-1.3.5.8.2.5.3.4.4"></a><p class="title"><strong>Figure 22.2. Underlying Associative Data Structures</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_different_underlying_dss_1.png" align="middle" alt="Underlying Associative Data Structures" /></div></div></div><br class="figure-break" /><p>
A shows a collision-chaining hash-table, B shows a probing
hash-table, C shows a red-black tree, D shows a splay tree, E shows
- a tree based on an ordered vector(implicit in the order of the
+ a tree based on an ordered vector (implicit in the order of the
elements), F shows a PATRICIA trie, and G shows a list-based
container with update policies.
</p><p>
@@ -409,7 +409,7 @@
<code class="function">operator++</code>). Conversely, the little
box marked <code class="classname">iterator</code> stores both a
pointer to the element, as well as some other
- information (the bucket number of the element). the
+ information (the bucket number of the element). The
second iterator, then, is "heavier" than the first one-
it requires more time and space. If we were to use a
different container to cross-reference into this
@@ -468,7 +468,7 @@
the C++ standard. A strict public interface of methods that
comprise only operations which depend on the class's internal
structure; other operations are best designed as external
- functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>).With this
+ functions. (See <a class="xref" href="policy_data_structures.html#biblio.meyers02both" title="Class Template, Member Template - or Both?">[biblio.meyers02both]</a>). With this
rubric, the standard associative containers lack some useful
methods, and provide other methods which would be better
removed.
@@ -481,9 +481,9 @@
</pre><p>
which takes an iterator, erases the corresponding
element, and returns an iterator to the following
- element. Also standardd hash-based associative
+ element. Also standard hash-based associative
containers provide this method. This seemingly
- increasesgenericity between associative containers,
+ increases genericity between associative containers,
since it is possible to use
</p><pre class="programlisting">
typename C::iterator it = c.begin();
@@ -493,7 +493,7 @@
it = pred(*it)? c.erase(it) : ++it;
</pre><p>
in order to erase from a container object <code class="varname">
- c</code> all element which match a
+ c</code> all elements which match a
predicate <code class="classname">pred</code>. However, in a
different sense this actually decreases genericity: an
integral implication of this method is that tree-based
@@ -509,7 +509,7 @@
provide this method that they cannot downsize when
elements are erased. As a consequence, different code is
needed to manipulate different containers, assuming that
- memory should be conserved. Therefor, this library's
+ memory should be conserved. Therefore, this library's
non-order preserving associative containers omit this
method.
</p></li><li class="listitem"><p>
@@ -533,7 +533,7 @@
</pre><p>
erasing a range of elements given by a pair of
iterators. For tree-based or trie-based containers, this can
- implemented more efficiently as a (small) sequence of split
+ be implemented more efficiently as a (small) sequence of split
and join operations. For other, unordered, containers, this
method isn't much better than an external loop. Moreover,
if <code class="varname">c</code> is a hash-based container,
@@ -589,7 +589,7 @@
equivalence, or interchangeability, but the associative
container cannot check for values' equivalence, only keys'
equivalence; also, are two containers considered equivalent if
- they store the same values in different order? this is an
+ they store the same values in different order? This is an
arbitrary decision.
</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.intro.motivation.priority_queue"></a>Priority Queues</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="motivation.priority_queue.policy"></a>Policy Choices</h5></div></div></div><p>
Priority queues are containers that allow efficiently inserting
@@ -597,7 +597,7 @@
container's comparison functor). Their interface
supports <code class="function">push</code>
and <code class="function">pop</code>. The standard
- container <code class="classname">std::priorityqueue</code> indeed support
+ container <code class="classname">std::priority_queue</code> indeed supports
these methods, but little else. For algorithmic and
software-engineering purposes, other methods are needed:
</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
@@ -660,7 +660,7 @@
</p></li><li class="listitem"><p>
In standard-library-like containers, it is natural to specify the
interface of operations for modifying a value or erasing
- a value (discussed previously) in terms of a iterators.
+ a value (discussed previously) in terms of iterators.
It should be noted that the standard
containers also use iterators for accessing and
manipulating a specific value. In hash-based
@@ -730,7 +730,7 @@
operation (including <code class="function">pop</code>) can render the container
useless due to exceptions. Conversely, if one uses
<code class="classname">std::priority_queue<std::deque<int> >
- ></code>, then each operation uses incurs a logarithmic
+ ></code>, then each operation incurs a logarithmic
number of indirect accesses (through pointers) unnecessarily.
It might be better to let the container make a conservative
deduction whether to use the structure in the graphic above, labels A1 or A2.
@@ -749,7 +749,7 @@
done.
</p></li><li class="listitem"><p>
If <code class="varname">p</code> is a priority queue adapting an
- <code class="classname">std::deque</code>, then the reference return by
+ <code class="classname">std::deque</code>, then the reference returned by
</p><pre class="programlisting">
p.top()
</pre><p>
diff --git a/libstdc++-v3/doc/html/manual/policy_data_structures_design.html b/libstdc++-v3/doc/html/manual/policy_data_structures_design.html
index a84551e38dbe..48253ddcfaa3 100644
--- a/libstdc++-v3/doc/html/manual/policy_data_structures_design.html
+++ b/libstdc++-v3/doc/html/manual/policy_data_structures_design.html
@@ -58,9 +58,8 @@
by <code class="classname">null_type</code>, then
the "set" acts very similarly to the standard's sets - it does not
map each key to a distinct <code class="classname">null_type</code> object. Also,
- , the container's <span class="type">value_type</span> is essentially
- its <span class="type">key_type</span> - just as with the standard's sets
- .</p><p>
+ the container's <span class="type">value_type</span> is essentially
+ its <span class="type">key_type</span> - just as with the standard's sets.</p><p>
The standard's multimaps and multisets allow, respectively,
non-uniquely mapping keys and non-uniquely storing keys. As
discussed, the
@@ -93,7 +92,7 @@
When one uses a "multimap," one should choose with care the
type of container used for secondary keys.
</p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="concepts.associative_semantics.multi"></a>Alternatives to <code class="classname">std::multiset</code> and <code class="classname">std::multimap</code></h5></div></div></div><p>
- Brace onself: this library does not contain containers like
+ Brace oneself: this library does not contain containers like
<code class="classname">std::multimap</code> or
<code class="classname">std::multiset</code>. Instead, these data
structures can be synthesized via manipulation of the
@@ -187,13 +186,13 @@
The underlying data structure embeds the linked lists
according to its own consideration, which means that the
search path for a value might include several different
- equivalent-key values. For example, the search path for the
+ equivalent-key values. For example, the search path for
the black node in either of the first graphic, labels A or B,
includes more than a single gray node.
</p></li><li class="listitem"><p>
The links of the linked lists are the underlying data
structures' nodes, which typically are quite structured. In
- the case of tree-based containers (the grapic above, label
+ the case of tree-based containers (the graphic above, label
B), each "link" is actually a node with three pointers (one
to a parent and two to children), and a
relatively-complicated iteration algorithm. The linked
@@ -232,8 +231,8 @@
<code class="function">equal_range</code>), the underlying data
structure typically does not. This means that operations such
as erasing from a tree-based container all values whose keys
- are equivalent to a a given key can be super-linear in the
- size of the tree; this is also true also for several other
+ are equivalent to a given key can be super-linear in the
+ size of the tree; this is also true for several other
operations that target a specific list.
</p></li></ol></div><p>
In this library, all associative containers map
@@ -260,7 +259,7 @@
example, one would use an associative container mapping
each <code class="classname">int</code> to some size-type indicating the
number of times it logically occurs
- (see <code class="filename">example/basic_multiset.cc</code>.
+ (see <code class="filename">example/basic_multiset.cc</code>).
</p><p>
See the discussion in list-based container types for containers
especially suited as secondary associative-containers.
@@ -300,18 +299,18 @@
</pre><p>The relationship between these iterator types varies between
container types. The figure below
shows the most general invariant between point-type and
- range-type iterators: In <span class="emphasis"><em>A</em></span> <code class="literal">iterator</code>, can
- always be converted to <code class="literal">point_iterator</code>. In <span class="emphasis"><em>B</em></span>
+ range-type iterators: In <span class="emphasis"><em>A</em></span>, <code class="literal">iterator</code> can
+ always be converted to <code class="literal">point_iterator</code>. <span class="emphasis"><em>B</em></span>
shows invariants for order-preserving containers: point-type
iterators are synonymous with range-type iterators.
- Orthogonally, <span class="emphasis"><em>C</em></span>shows invariants for "set"
+ Orthogonally, <span class="emphasis"><em>C</em></span> shows invariants for "set"
containers: iterators are synonymous with const iterators.</p><div class="figure"><a id="id-1.3.5.8.4.3.4.3.5"></a><p class="title"><strong>Figure 22.11. Point Iterator Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_point_iterator_hierarchy.png" align="middle" alt="Point Iterator Hierarchy" /></div></div></div><br class="figure-break" /><p>Note that point-type iterators in self-organizing containers
(hash-based associative containers) lack movement
operators, such as <code class="literal">operator++</code> - in fact, this
is the reason why this library differentiates from the standard C++ librarys
design on this point.</p><p>Typically, one can determine an iterator's movement
capabilities using
- <code class="literal">std::iterator_traits<It>iterator_category</code>,
+ <code class="literal">std::iterator_traits<It>::iterator_category</code>,
which is a <code class="literal">struct</code> indicating the iterator's
movement capabilities. Unfortunately, none of the standard predefined
categories reflect a pointer's <span class="emphasis"><em>not</em></span> having any
@@ -367,7 +366,7 @@
correspondingly, its invalidation guarantee (in this case
<code class="classname">range_invalidation_guarantee</code>)
can be cast to its base class (in this case <code class="classname">point_invalidation_guarantee</code>).
- This means that this this hierarchy can be used easily using
+ This means that this hierarchy can be used easily using
standard metaprogramming techniques, by specializing on the
type of <code class="literal">invalidation_guarantee</code>.</p><p>
These types of problems were addressed, in a more general
@@ -392,7 +391,7 @@
of <code class="function">some_op_sequence</code>:
</p><div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem"><p>
Which types and methods does <code class="literal">Cntnr</code> support?
- Containers based on hash tables can be queries for the
+ Containers based on hash tables can be queried for the
hash-functor type and object; this is meaningless for tree-based
containers. Containers based on trees can be split, joined, or
can erase iterators and return the following iterator; this
@@ -516,7 +515,7 @@
mapped into a sequence of positions within a table,
e.g., in a probing table. Similar terms apply in this
case: the table requires a ranged probe function,
- mapping a key into a sequence of positions withing the table.
+ mapping a key into a sequence of positions within the table.
This is typically achieved by composing a hash function
mapping the key into a non-negative integral type, a
probe function transforming the hash value into a
@@ -544,8 +543,7 @@
m a prime far from a power of 2, g(r, m) is
affected by all the bits of r (minimizing the chance of
collision). It has the disadvantage of using the costly modulo
- operation. This method is hard-wired into SGI's implementation
- .</p><p>The & (bit-mask) implementation has the advantage of
+ operation. This method is hard-wired into SGI's implementation.</p><p>The & (bit-mask) implementation has the advantage of
relying on the fast bit-wise and operation. It has the
disadvantage that for g(r, m) is affected only by the
low order bits of r. This method is hard-wired into
@@ -556,7 +554,7 @@
suitable for hashing (in the sense used in <a class="xref" href="policy_data_structures.html#biblio.knuth98sorting" title="The Art of Computer Programming - Sorting and Searching">[biblio.knuth98sorting]</a>), since
the values of m are determined by a resize policy with
possibly orthogonal considerations.</p><p>There are two cases where a ranged-hash function can be
- superior. The firs is when using perfect hashing: the
+ superior. The first is when using perfect hashing: the
second is when the values of m can be used to estimate
the "general" number of distinct values required. This is
described in the following.</p><p>Let</p><p>
@@ -571,7 +569,7 @@
</span></div></div><br class="equation-break" /><p>where a is some non-negative integral value. This is
the standard string-hashing function used in SGI's
implementation (with a = 5). Its advantage is that
- it takes into account all of the characters of the string.</p><p>Now assume that s is the string representation of a
+ it takes into account all of the characters of the string.</p><p>Now assume that s is the string representation
of a long DNA sequence (and so S = {'A', 'C', 'G',
'T'}). In this case, scanning the entire string might be
prohibitively expensive. A possible alternative might be to use
@@ -607,7 +605,7 @@
using the hash functor (points B and C), and transforms the
result into a position using the combining functor (points D
and E).</p><div class="figure"><a id="id-1.3.5.8.4.4.2.3.2.5.3.4"></a><p class="title"><strong>Figure 22.15. Insert hash sequence diagram</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_hash_range_hashing_seq_diagram.png" align="middle" alt="Insert hash sequence diagram" /></div></div></div><br class="figure-break" /><p>If <code class="classname">cc_hash_table</code>'s
- hash-functor, <code class="classname">Hash_Fn</code> is instantiated by <code class="classname">null_type</code> , then <code class="classname">Comb_Hash_Fn</code> is taken to be
+ hash-functor, <code class="classname">Hash_Fn</code> is instantiated by <code class="classname">null_type</code>, then <code class="classname">Comb_Hash_Fn</code> is taken to be
a ranged-hash function. The graphic below shows an <code class="function">insert</code> sequence
diagram. The user inserts an element (point A), the container
transforms the key into a position using the combining functor
@@ -702,7 +700,7 @@
above in this library. It first describes resize policies and
their decomposition into trigger and size policies, then
describes pre-defined classes, and finally discusses controlled
- access the policies' internals.</p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.impl.decomposition"></a>Decomposition</h6></div></div></div><p>Each hash-based container is parametrized by a
+ access to the policies' internals.</p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.impl.decomposition"></a>Decomposition</h6></div></div></div><p>Each hash-based container is parametrized by a
<code class="classname">Resize_Policy</code> parameter; the container derives
<code class="classname">public</code>ly from <code class="classname">Resize_Policy</code>. For
example:</p><pre class="programlisting">
@@ -742,9 +740,9 @@
implements a collision check trigger policy.</p></li><li class="listitem"><p><code class="classname">hash_exponential_size_policy</code>
implements an exponential-size policy (which should be used
with mask range hashing).</p></li><li class="listitem"><p><code class="classname">hash_prime_size_policy</code>
- implementing a size policy based on a sequence of primes
+ implements a size policy based on a sequence of primes
(which should
- be used with mod range hashing</p></li></ol></div><p>The graphic below gives an overall picture of the resize-related
+ be used with mod range hashing)</p></li></ol></div><p>The graphic below gives an overall picture of the resize-related
classes. <code class="classname">basic_hash_table</code>
is parametrized by <code class="classname">Resize_Policy</code>, which it subclasses
publicly. This class is currently instantiated only by <code class="classname">hash_standard_resize_policy</code>.
@@ -754,7 +752,7 @@
instantiated by <code class="classname">hash_load_check_resize_trigger</code>,
or <code class="classname">cc_hash_max_collision_check_resize_trigger</code>;
<code class="classname">Size_Policy</code> is instantiated by <code class="classname">hash_exponential_size_policy</code>,
- or <code class="classname">hash_prime_size_policy</code>.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.impl.internals"></a>Controling Access to Internals</h6></div></div></div><p>There are cases where (controlled) access to resize
+ or <code class="classname">hash_prime_size_policy</code>.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="resize_policies.impl.internals"></a>Controlling Access to Internals</h6></div></div></div><p>There are cases where (controlled) access to resize
policies' internals is beneficial. E.g., it is sometimes
useful to query a hash-table for the table's actual size (as
opposed to its <code class="function">size()</code> - the number of values it
@@ -868,7 +866,7 @@
these trees can support the usual queries: the first can easily
search for <code class="classname">0.4</code>; the second can easily search for
<code class="classname">std::make_pair(10, 41)</code>.</p><p>Each of these trees can efficiently support other queries.
- The first can efficiently determine that the 2rd key in the
+ The first can efficiently determine that the 2nd key in the
tree is <code class="constant">0.3</code>; the second can efficiently determine
whether any of its intervals overlaps
</p><pre class="programlisting">std::make_pair(29,42)</pre><p> (useful in geometric
@@ -1014,7 +1012,7 @@
class Node_Update = null_node_update,
typename Allocator = std::allocator<char> >
class trie;
- </pre><p>The parameters have the following meaning:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p><code class="classname">Key</code> is the key type.</p></li><li class="listitem"><p><code class="classname">Mapped</code> is the mapped-policy.</p></li><li class="listitem"><p><code class="classname">E_Access_Traits</code> is described in below.</p></li><li class="listitem"><p><code class="classname">Tag</code> specifies which underlying data structure
+ </pre><p>The parameters have the following meaning:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p><code class="classname">Key</code> is the key type.</p></li><li class="listitem"><p><code class="classname">Mapped</code> is the mapped-policy.</p></li><li class="listitem"><p><code class="classname">E_Access_Traits</code> is described below.</p></li><li class="listitem"><p><code class="classname">Tag</code> specifies which underlying data structure
to use, and is described shortly.</p></li><li class="listitem"><p><code class="classname">Node_Update</code> is a policy for updating node
invariants. This is described below.</p></li><li class="listitem"><p><code class="classname">Allocator</code> is an allocator
type.</p></li></ol></div><p>The <code class="classname">Tag</code> parameter specifies which underlying
@@ -1031,7 +1029,7 @@
+ 1, where n is the number of distinct
elements.</p></li><li class="listitem"><p>It stores values only at leaf nodes.</p></li><li class="listitem"><p>Internal nodes have the properties that A) each has at
least two children, and B) each shares the same prefix with
- any of its descendant.</p></li></ol></div><p>A (PATRICIA) trie has some useful properties:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>It can be configured to use large node fan-out, giving it
+ any of its descendants.</p></li></ol></div><p>A (PATRICIA) trie has some useful properties:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>It can be configured to use large node fan-out, giving it
very efficient find performance (albeit at insertion
complexity and size).</p></li><li class="listitem"><p>It works well for common-prefix keys.</p></li><li class="listitem"><p>It can support efficiently queries such as which
keys match a certain prefix. This is sometimes useful in file
@@ -1054,7 +1052,7 @@
<code class="classname">reverse_iterator</code>. As another example, a trie mapping
UNICODE strings would have a huge fan-out if each node would
branch on a UNICODE character; instead, one can define an
- iterator iterating over 8-bit (or less) groups.</p></li></ol></div><p>trie is,
+ iterator iterating over 8-bit (or less) groups.</p></li></ol></div><p>A trie is,
consequently, parametrized by <code class="classname">E_Access_Traits</code> -
traits which instruct how to access sequences' elements.
<code class="classname">string_trie_e_access_traits</code>
@@ -1070,18 +1068,18 @@
two <code class="classname">typename E_Access_Traits::const_iterator</code>
objects, indicating the maximal common prefix of all keys in
the sub-tree. For example, the shaded internal node roots a
- sub-tree with leafs "a" and "as". The maximal common prefix is
+ sub-tree with leaves "a" and "as". The maximal common prefix is
"a". The internal node contains, consequently, to const
iterators, one pointing to <code class="varname">'a'</code>, and the other to
<code class="varname">'s'</code>.</p><div class="figure"><a id="id-1.3.5.8.4.4.4.3.2.10"></a><p class="title"><strong>Figure 22.28. A PATRICIA trie</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_pat_trie.png" align="middle" alt="A PATRICIA trie" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.trie.details.node"></a>Node Invariants</h6></div></div></div><p>Trie-based containers support node invariants, as do
tree-based containers. There are two minor
- differences, though, which, unfortunately, thwart sharing them
+ differences, though, which, unfortunately, thwart them
sharing the same node-updating policies:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>A trie's <code class="classname">Node_Update</code> template-template
parameter is parametrized by <code class="classname">E_Access_Traits</code>, while
a tree's <code class="classname">Node_Update</code> template-template parameter is
parametrized by <code class="classname">Cmp_Fn</code>.</p></li><li class="listitem"><p>Tree-based containers store values in all nodes, while
trie-based containers (at least in this implementation) store
- values in leafs.</p></li></ol></div><p>The graphic below shows the scheme, as well as some predefined
+ values in leaves.</p></li></ol></div><p>The graphic below shows the scheme, as well as some predefined
policies (which are explained below).</p><div class="figure"><a id="id-1.3.5.8.4.4.4.3.3.5"></a><p class="title"><strong>Figure 22.29. A trie and its update policy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_trie_node_updator_policy_cd.png" align="middle" alt="A trie and its update policy" /></div></div></div><br class="figure-break" /><p>This library offers the following pre-defined trie node
updating policies:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
<code class="classname">trie_order_statistics_node_update</code>
@@ -1140,7 +1138,7 @@
predetermined value, say 10, as shown in label C, the count is set
to 0 and the node is moved to the front of the list, as in label
D.
- </p><div class="figure"><a id="id-1.3.5.8.4.4.5.3.3.6"></a><p class="title"><strong>Figure 22.31. The counter algorithm</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_list_update.png" align="middle" alt="The counter algorithm" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.list.details.policies"></a>Policies</h6></div></div></div><p>this library allows instantiating lists with policies
+ </p><div class="figure"><a id="id-1.3.5.8.4.4.5.3.3.6"></a><p class="title"><strong>Figure 22.31. The counter algorithm</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_list_update.png" align="middle" alt="The counter algorithm" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.list.details.policies"></a>Policies</h6></div></div></div><p>This library allows instantiating lists with policies
implementing any algorithm moving nodes to the front of the
list (policies implementing algorithms interchanging nodes are
unsupported).</p><p>Associative containers based on lists are parametrized by a
@@ -1171,10 +1169,10 @@
is <code class="classname">lu_counter_policy</code>, which implements the
counter algorithm described above. The second is
<code class="classname">lu_move_to_front_policy</code>,
- which unconditionally move an accessed element to the front of
+ which unconditionally moves an accessed element to the front of
the list. The latter type is very useful in this library,
since there is no need to associate metadata with each element.
- (See <a class="xref" href="policy_data_structures.html#biblio.andrew04mtf" title="MTF, Bit, and COMB: A Guide to Deterministic and Randomized Algorithms for the List Update Problem">[biblio.andrew04mtf]</a>
+ (See <a class="xref" href="policy_data_structures.html#biblio.andrew04mtf" title="MTF, Bit, and COMB: A Guide to Deterministic and Randomized Algorithms for the List Update Problem">[biblio.andrew04mtf]</a>).
</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.list.details.mapped"></a>Use in Multimaps</h6></div></div></div><p>In this library, there are no equivalents for the standard's
multimaps and multisets; instead one uses an associative
container mapping primary keys to secondary keys.</p><p>List-based containers are especially useful as associative
@@ -1215,7 +1213,7 @@
</pre><p>The parameters have the following meaning:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p><code class="classname">Value_Type</code> is the value type.</p></li><li class="listitem"><p><code class="classname">Cmp_Fn</code> is a value comparison functor</p></li><li class="listitem"><p><code class="classname">Tag</code> specifies which underlying data structure
to use.</p></li><li class="listitem"><p><code class="classname">Allocator</code> is an allocator
type.</p></li></ol></div><p>The <code class="classname">Tag</code> parameter specifies which underlying
- data structure to use. Instantiating it by<code class="classname">pairing_heap_tag</code>,<code class="classname">binary_heap_tag</code>,
+ data structure to use. Instantiating it by <code class="classname">pairing_heap_tag</code>, <code class="classname">binary_heap_tag</code>,
<code class="classname">binomial_heap_tag</code>,
<code class="classname">rc_binomial_heap_tag</code>,
or <code class="classname">thin_heap_tag</code>,
@@ -1238,9 +1236,9 @@
<code class="classname">std::priority_queue</code>, however, since typically
<code class="classname">push</code> and <code class="classname">pop</code> are deemed
insufficient for manipulating priority-queues. </p><p>Different settings require different priority-queue
- implementations which are described in later; see traits
- discusses ways to differentiate between the different traits of
- different implementations.</p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="container.priority_queue.details"></a>Details</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.priority_queue.details.iterators"></a>Iterators</h6></div></div></div><p>There are many different underlying-data structures for
+ implementations which are described later; see
+ <a class="xref" href="policy_data_structures_design.html#container.priority_queue.details.traits" title="Traits">the section called “Traits”</a>, which
+ discusses ways to differentiate between implementations.</p></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="container.priority_queue.details"></a>Details</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.priority_queue.details.iterators"></a>Iterators</h6></div></div></div><p>There are many different underlying-data structures for
implementing priority queues. Unfortunately, most such
structures are oriented towards making <code class="function">push</code> and
<code class="function">top</code> efficient, and consequently don't allow efficient
@@ -1330,37 +1328,37 @@
Instantiating the <code class="classname">Tag</code> template parameter, "selects"
the implementation:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
Instantiating <code class="classname">Tag = binary_heap_tag</code> creates
- a binary heap of the form in represented in the graphic with labels A1 or A2. The former is internally
+ a binary heap of the form represented in the graphic with labels A1 or A2. The former is internally
selected by priority_queue
if <code class="classname">Value_Type</code> is instantiated by a primitive type
(e.g., an <span class="type">int</span>); the latter is
internally selected for all other types (e.g.,
- <code class="classname">std::string</code>). This implementations is relatively
+ <code class="classname">std::string</code>). This implementation is relatively
unstructured, and so has good <code class="classname">push</code> and <code class="classname">pop</code>
performance; it is the "best-in-kind" for primitive
types, e.g., <span class="type">int</span>s. Conversely, it has
high worst-case performance, and can support only linear-time
<code class="function">modify</code> and <code class="function">erase</code> operations.</p></li><li class="listitem"><p>Instantiating <code class="classname">Tag =
pairing_heap_tag</code> creates a pairing heap of the form
- in represented by label B in the graphic above. This
- implementations too is relatively unstructured, and so has good
+ represented by label B in the graphic above. This
+ implementation too is relatively unstructured, and so has good
<code class="function">push</code> and <code class="function">pop</code>
performance; it is the "best-in-kind" for non-primitive types,
- e.g., <code class="classname">std:string</code>s. It also has very good
+ e.g., <code class="classname">std::string</code>s. It also has very good
worst-case <code class="function">push</code> and
<code class="function">join</code> performance (O(1)), but has high
worst-case <code class="function">pop</code>
complexity.</p></li><li class="listitem"><p>Instantiating <code class="classname">Tag =
binomial_heap_tag</code> creates a binomial heap of the
- form repsented by label B in the graphic above. This
- implementations is more structured than a pairing heap, and so
+ form represented by label B in the graphic above. This
+ implementation is more structured than a pairing heap, and so
has worse <code class="function">push</code> and <code class="function">pop</code>
performance. Conversely, it has sub-linear worst-case bounds for
<code class="function">pop</code>, e.g., and so it might be preferred in
cases where responsiveness is important.</p></li><li class="listitem"><p>Instantiating <code class="classname">Tag =
rc_binomial_heap_tag</code> creates a binomial heap of the
form represented in label B above, accompanied by a redundant
- counter which governs the trees. This implementations is
+ counter which governs the trees. This implementation is
therefore more structured than a binomial heap, and so has worse
<code class="function">push</code> and <code class="function">pop</code>
performance. Conversely, it guarantees O(1)
@@ -1369,7 +1367,7 @@
is insufficient.</p></li><li class="listitem"><p>Instantiating <code class="classname">Tag =
thin_heap_tag</code> creates a thin heap of the form
represented by the label B in the graphic above. This
- implementations too is more structured than a pairing heap, and
+ implementation too is more structured than a pairing heap, and
so has worse <code class="function">push</code> and
<code class="function">pop</code> performance. Conversely, it has better
worst-case and identical amortized complexities than a Fibonacci
@@ -1383,8 +1381,8 @@
Most associative containers are too structured to compete with
priority queues in terms of <code class="function">push</code> and <code class="function">pop</code>
performance.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="container.priority_queue.details.traits"></a>Traits</h6></div></div></div><p>It would be nice if all priority queues could
- share exactly the same behavior regardless of implementation. Sadly, this is not possible. Just one for instance is in join operations: joining
- two binary heaps might throw an exception (not corrupt
+ share exactly the same behavior regardless of implementation. Sadly, this is not possible. Just one example is in join operations: joining
+ two binary heaps might throw an exception (but not corrupt
any of the heaps on which it operates), but joining two pairing
heaps is exception free.</p><p>Tags and traits are very useful for manipulating generic
types. <code class="classname">__gnu_pbds::priority_queue</code>
diff --git a/libstdc++-v3/doc/html/manual/policy_data_structures_using.html b/libstdc++-v3/doc/html/manual/policy_data_structures_using.html
index d11ad62198f9..47733d4d24fc 100644
--- a/libstdc++-v3/doc/html/manual/policy_data_structures_using.html
+++ b/libstdc++-v3/doc/html/manual/policy_data_structures_using.html
@@ -1,6 +1,6 @@
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Using</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, policy, container, data, structure, associated, tree, trie, hash, metaprogramming" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="policy_data_structures.html" title="Chapter 22. Policy-Based Data Structures" /><link rel="prev" href="policy_data_structures.html" title="Chapter 22. Policy-Based Data Structures" /><link rel="next" href="policy_data_structures_design.html" title="Design" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Using</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="policy_data_structures.html">Prev</a> </td><th width="60%" align="center">Chapter 22. Policy-Based Data Structures</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_design.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="containers.pbds.using"></a>Using</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.using.prereq"></a>Prerequisites</h3></div></div></div><p>The library contains only header files, and does not require any
- other libraries except the standard C++ library . All classes are
+ other libraries except the standard C++ library. All classes are
defined in namespace <code class="code">__gnu_pbds</code>. The library internally
uses macros beginning with <code class="code">PB_DS</code>, but
<code class="code">#undef</code>s anything it <code class="code">#define</code>s (except for
@@ -24,7 +24,7 @@
associative-containers
</p></li><li class="listitem"><p>
<code class="classname">trie</code>
- is a concrete base class trie-based
+ is a concrete base class for trie-based
associative-containers
</p></li></ul></div></li><li class="listitem"><p>
Hash-Based
@@ -62,7 +62,7 @@
used to report errors specific to this library's data
structures.
</p><div class="figure"><a id="id-1.3.5.8.3.3.6"></a><p class="title"><strong>Figure 22.7. Exception Hierarchy</strong></p><div class="figure-contents"><div class="mediaobject" align="center"><img src="../images/pbds_exception_hierarchy.png" align="middle" alt="Exception Hierarchy" /></div></div></div><br class="figure-break" /></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.using.tutorial"></a>Tutorial</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.basic"></a>Basic Use</h4></div></div></div><p>
- For the most part, the policy-based containers containers in
+ For the most part, the policy-based containers in
namespace <code class="literal">__gnu_pbds</code> 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,
@@ -106,10 +106,10 @@
<code class="function">clear</code>.
</p><p>
This isn't to say that things are exactly as one would expect, given
- the container requirments and interfaces in the C++ standard.
+ the container requirements and interfaces in the C++ standard.
</p><p>
The names of containers' policies and policy accessors are
- different then the usual. For example, if <span class="type">hash_type</span> is
+ different than the usual. For example, if <span class="type">hash_type</span> is
some type of hash-based container, then</p><pre class="programlisting">
hash_type::hash_fn
</pre><p>
@@ -194,13 +194,13 @@
follows:
</p><pre class="programlisting">
template<typename Key, typename Mapped, typename Hash,
- typename Pred, typename Allocator, bool Cache_Hashe_Code>
+ typename Pred, typename Allocator, bool Cache_Hash_Code>
class unordered_map;
</pre><p>
and so can be configured by key type, mapped type, a functor
that translates keys to unsigned integral types, an equivalence
predicate, an allocator, and an indicator whether to store hash
- values with each entry. this library's collision-chaining
+ values with each entry. This library's collision-chaining
hash-based container is parametrized as
</p><pre class="programlisting">
template<typename Key, typename Mapped, typename Hash_Fn,
@@ -241,11 +241,11 @@
<code class="classname">__gnu_pbds::priority_queue</code> is not a
sequence-adapter; it is a regular container.</p></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.using.tutorial.traits"></a>
Querying Container Attributes
- </h4></div></div></div><p></p><p>A containers underlying data structure
- affect their performance; Unfortunately, they can also affect
+ </h4></div></div></div><p></p><p>A container's underlying data structure
+ affects its performance; unfortunately, they can also affect
their interface. When manipulating generically associative
containers, it is often useful to be able to statically
- determine what they can support and what the cannot.
+ determine what they can support and what they cannot.
</p><p>Happily, the standard provides a good solution to a similar
problem - that of the different behavior of iterators. If
<code class="classname">It</code> is an iterator, then
@@ -346,7 +346,7 @@
point_iterator find(...);
};
</pre><p>For
- containers whose interface defines sequence order , it
+ containers whose interface defines sequence order, it
is very simple: point-type and range-type iterators are exactly
the same, which means that the above snippet will compile if it
is used for an order-preserving associative container.
@@ -362,7 +362,7 @@
</pre><p>
because a range-type iterator can always be converted to a
point-type iterator.
- </p><p>Distingushing between iterator types also
+ </p><p>Distinguishing between iterator types also
raises the point that a container's iterators might have
different invalidation rules concerning their de-referencing
abilities and movement abilities. This now corresponds exactly
diff --git a/libstdc++-v3/doc/xml/manual/policy_data_structures.xml b/libstdc++-v3/doc/xml/manual/policy_data_structures.xml
index b82a458507e7..6f3846b8acec 100644
--- a/libstdc++-v3/doc/xml/manual/policy_data_structures.xml
+++ b/libstdc++-v3/doc/xml/manual/policy_data_structures.xml
@@ -58,7 +58,7 @@
<para>
In many cases, the longer names allow capabilities and behaviours
- controlled by macros to also be unamibiguously emitted as distinct
+ controlled by macros to also be unambiguously emitted as distinct
generated names.
</para>
@@ -122,7 +122,7 @@
</section>
<section xml:id="pbds.intro.issues.priority_queue">
- <info><title>Priority Que</title></info>
+ <info><title>Priority Queue</title></info>
<para>
Priority queues are useful when one needs to efficiently access a
@@ -324,7 +324,7 @@
<para>
A shows a collision-chaining hash-table, B shows a probing
hash-table, C shows a red-black tree, D shows a splay tree, E shows
- a tree based on an ordered vector(implicit in the order of the
+ a tree based on an ordered vector (implicit in the order of the
elements), F shows a PATRICIA trie, and G shows a list-based
container with update policies.
</para>
@@ -554,7 +554,7 @@
<function>operator++</function>). Conversely, the little
box marked <classname>iterator</classname> stores both a
pointer to the element, as well as some other
- information (the bucket number of the element). the
+ information (the bucket number of the element). The
second iterator, then, is "heavier" than the first one-
it requires more time and space. If we were to use a
different container to cross-reference into this
@@ -678,7 +678,7 @@
the C++ standard. A strict public interface of methods that
comprise only operations which depend on the class's internal
structure; other operations are best designed as external
- functions. (See <xref linkend="biblio.meyers02both"/>).With this
+ functions. (See <xref linkend="biblio.meyers02both"/>). With this
rubric, the standard associative containers lack some useful
methods, and provide other methods which would be better
removed.
@@ -701,9 +701,9 @@
<para>
which takes an iterator, erases the corresponding
element, and returns an iterator to the following
- element. Also standardd hash-based associative
+ element. Also standard hash-based associative
containers provide this method. This seemingly
- increasesgenericity between associative containers,
+ increases genericity between associative containers,
since it is possible to use
</para>
<programlisting>
@@ -716,7 +716,7 @@
<para>
in order to erase from a container object <varname>
- c</varname> all element which match a
+ c</varname> all elements which match a
predicate <classname>pred</classname>. However, in a
different sense this actually decreases genericity: an
integral implication of this method is that tree-based
@@ -732,7 +732,7 @@
provide this method that they cannot downsize when
elements are erased. As a consequence, different code is
needed to manipulate different containers, assuming that
- memory should be conserved. Therefor, this library's
+ memory should be conserved. Therefore, this library's
non-order preserving associative containers omit this
method.
</para>
@@ -768,7 +768,7 @@
<para>
erasing a range of elements given by a pair of
iterators. For tree-based or trie-based containers, this can
- implemented more efficiently as a (small) sequence of split
+ be implemented more efficiently as a (small) sequence of split
and join operations. For other, unordered, containers, this
method isn't much better than an external loop. Moreover,
if <varname>c</varname> is a hash-based container,
@@ -857,7 +857,7 @@
equivalence, or interchangeability, but the associative
container cannot check for values' equivalence, only keys'
equivalence; also, are two containers considered equivalent if
- they store the same values in different order? this is an
+ they store the same values in different order? This is an
arbitrary decision.
</para>
</section> <!-- compare -->
@@ -878,7 +878,7 @@
container's comparison functor). Their interface
supports <function>push</function>
and <function>pop</function>. The standard
- container <classname>std::priorityqueue</classname> indeed support
+ container <classname>std::priority_queue</classname> indeed supports
these methods, but little else. For algorithmic and
software-engineering purposes, other methods are needed:
</para>
@@ -975,7 +975,7 @@
<para>
In standard-library-like containers, it is natural to specify the
interface of operations for modifying a value or erasing
- a value (discussed previously) in terms of a iterators.
+ a value (discussed previously) in terms of iterators.
It should be noted that the standard
containers also use iterators for accessing and
manipulating a specific value. In hash-based
@@ -1093,7 +1093,7 @@
operation (including <function>pop</function>) can render the container
useless due to exceptions. Conversely, if one uses
<classname>std::priority_queue<std::deque<int> >
- ></classname>, then each operation uses incurs a logarithmic
+ ></classname>, then each operation incurs a logarithmic
number of indirect accesses (through pointers) unnecessarily.
It might be better to let the container make a conservative
deduction whether to use the structure in the graphic above, labels A1 or A2.
@@ -1123,7 +1123,7 @@
<listitem>
<para>
If <varname>p</varname> is a priority queue adapting an
- <classname>std::deque</classname>, then the reference return by
+ <classname>std::deque</classname>, then the reference returned by
</para>
<programlisting>
p.top()
@@ -1167,7 +1167,7 @@
<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
+ 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
@@ -1215,7 +1215,7 @@
<listitem>
<para>
<classname>trie</classname>
- is a concrete base class trie-based
+ is a concrete base class for trie-based
associative-containers
</para>
</listitem>
@@ -1322,7 +1322,7 @@
<info><title>Basic Use</title></info>
<para>
- For the most part, the policy-based containers containers in
+ For the most part, the policy-based 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,
@@ -1379,12 +1379,12 @@
<para>
This isn't to say that things are exactly as one would expect, given
- the container requirments and interfaces in the C++ standard.
+ the container requirements 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
+ different than the usual. For example, if <type>hash_type</type> is
some type of hash-based container, then</para>
<programlisting>
@@ -1520,7 +1520,7 @@
</para>
<programlisting>
template<typename Key, typename Mapped, typename Hash,
- typename Pred, typename Allocator, bool Cache_Hashe_Code>
+ typename Pred, typename Allocator, bool Cache_Hash_Code>
class unordered_map;
</programlisting>
@@ -1528,7 +1528,7 @@
and so can be configured by key type, mapped type, a functor
that translates keys to unsigned integral types, an equivalence
predicate, an allocator, and an indicator whether to store hash
- values with each entry. this library's collision-chaining
+ values with each entry. This library's collision-chaining
hash-based container is parametrized as
</para>
<programlisting>
@@ -1592,11 +1592,11 @@
</info>
<para></para>
- <para>A containers underlying data structure
- affect their performance; Unfortunately, they can also affect
+ <para>A container's underlying data structure
+ affects its performance; unfortunately, they can also affect
their interface. When manipulating generically associative
containers, it is often useful to be able to statically
- determine what they can support and what the cannot.
+ determine what they can support and what they cannot.
</para>
<para>Happily, the standard provides a good solution to a similar
@@ -1738,7 +1738,7 @@
</programlisting>
<para>For
- containers whose interface defines sequence order , it
+ containers whose interface defines sequence order, it
is very simple: point-type and range-type iterators are exactly
the same, which means that the above snippet will compile if it
is used for an order-preserving associative container.
@@ -1763,7 +1763,7 @@
point-type iterator.
</para>
- <para>Distingushing between iterator types also
+ <para>Distinguishing between iterator types also
raises the point that a container's iterators might have
different invalidation rules concerning their de-referencing
abilities and movement abilities. This now corresponds exactly
@@ -2182,9 +2182,8 @@
by <classname>null_type</classname>, then
the "set" acts very similarly to the standard's sets - it does not
map each key to a distinct <classname>null_type</classname> object. Also,
- , the container's <type>value_type</type> is essentially
- its <type>key_type</type> - just as with the standard's sets
- .</para>
+ the container's <type>value_type</type> is essentially
+ its <type>key_type</type> - just as with the standard's sets.</para>
<para>
The standard's multimaps and multisets allow, respectively,
@@ -2232,7 +2231,7 @@
<info><title>Alternatives to <classname>std::multiset</classname> and <classname>std::multimap</classname></title></info>
<para>
- Brace onself: this library does not contain containers like
+ Brace oneself: this library does not contain containers like
<classname>std::multimap</classname> or
<classname>std::multiset</classname>. Instead, these data
structures can be synthesized via manipulation of the
@@ -2385,7 +2384,7 @@
The underlying data structure embeds the linked lists
according to its own consideration, which means that the
search path for a value might include several different
- equivalent-key values. For example, the search path for the
+ equivalent-key values. For example, the search path for
the black node in either of the first graphic, labels A or B,
includes more than a single gray node.
</para>
@@ -2395,7 +2394,7 @@
<para>
The links of the linked lists are the underlying data
structures' nodes, which typically are quite structured. In
- the case of tree-based containers (the grapic above, label
+ the case of tree-based containers (the graphic above, label
B), each "link" is actually a node with three pointers (one
to a parent and two to children), and a
relatively-complicated iteration algorithm. The linked
@@ -2458,8 +2457,8 @@
<function>equal_range</function>), the underlying data
structure typically does not. This means that operations such
as erasing from a tree-based container all values whose keys
- are equivalent to a a given key can be super-linear in the
- size of the tree; this is also true also for several other
+ are equivalent to a given key can be super-linear in the
+ size of the tree; this is also true for several other
operations that target a specific list.
</para>
</listitem>
@@ -2508,7 +2507,7 @@
example, one would use an associative container mapping
each <classname>int</classname> to some size-type indicating the
number of times it logically occurs
- (see <filename>example/basic_multiset.cc</filename>.
+ (see <filename>example/basic_multiset.cc</filename>).
</para>
<para>
@@ -2579,11 +2578,11 @@
<para>The relationship between these iterator types varies between
container types. The figure below
shows the most general invariant between point-type and
- range-type iterators: In <emphasis>A</emphasis> <literal>iterator</literal>, can
- always be converted to <literal>point_iterator</literal>. In <emphasis>B</emphasis>
+ range-type iterators: In <emphasis>A</emphasis>, <literal>iterator</literal> can
+ always be converted to <literal>point_iterator</literal>. <emphasis>B</emphasis>
shows invariants for order-preserving containers: point-type
iterators are synonymous with range-type iterators.
- Orthogonally, <emphasis>C</emphasis>shows invariants for "set"
+ Orthogonally, <emphasis>C</emphasis> shows invariants for "set"
containers: iterators are synonymous with const iterators.</para>
<figure>
@@ -2608,7 +2607,7 @@
<para>Typically, one can determine an iterator's movement
capabilities using
- <literal>std::iterator_traits<It>iterator_category</literal>,
+ <literal>std::iterator_traits<It>::iterator_category</literal>,
which is a <literal>struct</literal> indicating the iterator's
movement capabilities. Unfortunately, none of the standard predefined
categories reflect a pointer's <emphasis>not</emphasis> having any
@@ -2711,7 +2710,7 @@
correspondingly, its invalidation guarantee (in this case
<classname>range_invalidation_guarantee</classname>)
can be cast to its base class (in this case <classname>point_invalidation_guarantee</classname>).
- This means that this this hierarchy can be used easily using
+ This means that this hierarchy can be used easily using
standard metaprogramming techniques, by specializing on the
type of <literal>invalidation_guarantee</literal>.</para>
@@ -2753,7 +2752,7 @@
<listitem>
<para>
Which types and methods does <literal>Cntnr</literal> support?
- Containers based on hash tables can be queries for the
+ Containers based on hash tables can be queried for the
hash-functor type and object; this is meaningless for tree-based
containers. Containers based on trees can be split, joined, or
can erase iterators and return the following iterator; this
@@ -3063,7 +3062,7 @@
mapped into a sequence of positions within a table,
e.g., in a probing table. Similar terms apply in this
case: the table requires a ranged probe function,
- mapping a key into a sequence of positions withing the table.
+ mapping a key into a sequence of positions within the table.
This is typically achieved by composing a hash function
mapping the key into a non-negative integral type, a
probe function transforming the hash value into a
@@ -3132,8 +3131,7 @@
m a prime far from a power of 2, g(r, m) is
affected by all the bits of r (minimizing the chance of
collision). It has the disadvantage of using the costly modulo
- operation. This method is hard-wired into SGI's implementation
- .</para>
+ operation. This method is hard-wired into SGI's implementation.</para>
<para>The & (bit-mask) implementation has the advantage of
relying on the fast bit-wise and operation. It has the
@@ -3156,7 +3154,7 @@
possibly orthogonal considerations.</para>
<para>There are two cases where a ranged-hash function can be
- superior. The firs is when using perfect hashing: the
+ superior. The first is when using perfect hashing: the
second is when the values of m can be used to estimate
the "general" number of distinct values required. This is
described in the following.</para>
@@ -3186,7 +3184,7 @@
implementation (with a = 5). Its advantage is that
it takes into account all of the characters of the string.</para>
- <para>Now assume that s is the string representation of a
+ <para>Now assume that s is the string representation
of a long DNA sequence (and so S = {'A', 'C', 'G',
'T'}). In this case, scanning the entire string might be
prohibitively expensive. A possible alternative might be to use
@@ -3280,7 +3278,7 @@
</figure>
<para>If <classname>cc_hash_table</classname>'s
- hash-functor, <classname>Hash_Fn</classname> is instantiated by <classname>null_type</classname> , then <classname>Comb_Hash_Fn</classname> is taken to be
+ hash-functor, <classname>Hash_Fn</classname> is instantiated by <classname>null_type</classname>, then <classname>Comb_Hash_Fn</classname> is taken to be
a ranged-hash function. The graphic below shows an <function>insert</function> sequence
diagram. The user inserts an element (point A), the container
transforms the key into a position using the combining functor
@@ -3519,7 +3517,7 @@
above in this library. It first describes resize policies and
their decomposition into trigger and size policies, then
describes pre-defined classes, and finally discusses controlled
- access the policies' internals.</para>
+ access to the policies' internals.</para>
<section xml:id="resize_policies.impl.decomposition">
<info><title>Decomposition</title></info>
@@ -3632,9 +3630,9 @@
with mask range hashing).</para></listitem>
<listitem><para><classname>hash_prime_size_policy</classname>
- implementing a size policy based on a sequence of primes
+ implements a size policy based on a sequence of primes
(which should
- be used with mod range hashing</para></listitem>
+ be used with mod range hashing)</para></listitem>
</orderedlist>
<para>The graphic below gives an overall picture of the resize-related
@@ -3652,7 +3650,7 @@
</section>
<section xml:id="resize_policies.impl.internals">
- <info><title>Controling Access to Internals</title></info>
+ <info><title>Controlling Access to Internals</title></info>
<para>There are cases where (controlled) access to resize
policies' internals is beneficial. E.g., it is sometimes
@@ -3891,7 +3889,7 @@
<classname>std::make_pair(10, 41)</classname>.</para>
<para>Each of these trees can efficiently support other queries.
- The first can efficiently determine that the 2rd key in the
+ The first can efficiently determine that the 2nd key in the
tree is <constant>0.3</constant>; the second can efficiently determine
whether any of its intervals overlaps
<programlisting>std::make_pair(29,42)</programlisting> (useful in geometric
@@ -4229,7 +4227,7 @@
<listitem><para><classname>Mapped</classname> is the mapped-policy.</para></listitem>
- <listitem><para><classname>E_Access_Traits</classname> is described in below.</para></listitem>
+ <listitem><para><classname>E_Access_Traits</classname> is described below.</para></listitem>
<listitem><para><classname>Tag</classname> specifies which underlying data structure
to use, and is described shortly.</para></listitem>
@@ -4268,7 +4266,7 @@
<listitem><para>Internal nodes have the properties that A) each has at
least two children, and B) each shares the same prefix with
- any of its descendant.</para></listitem>
+ any of its descendants.</para></listitem>
</orderedlist>
<para>A (PATRICIA) trie has some useful properties:</para>
@@ -4323,7 +4321,7 @@
iterator iterating over 8-bit (or less) groups.</para></listitem>
</orderedlist>
- <para>trie is,
+ <para>A trie is,
consequently, parametrized by <classname>E_Access_Traits</classname> -
traits which instruct how to access sequences' elements.
<classname>string_trie_e_access_traits</classname>
@@ -4346,7 +4344,7 @@
two <classname>typename E_Access_Traits::const_iterator</classname>
objects, indicating the maximal common prefix of all keys in
the sub-tree. For example, the shaded internal node roots a
- sub-tree with leafs "a" and "as". The maximal common prefix is
+ sub-tree with leaves "a" and "as". The maximal common prefix is
"a". The internal node contains, consequently, to const
iterators, one pointing to <varname>'a'</varname>, and the other to
<varname>'s'</varname>.</para>
@@ -4371,7 +4369,7 @@
<para>Trie-based containers support node invariants, as do
tree-based containers. There are two minor
- differences, though, which, unfortunately, thwart sharing them
+ differences, though, which, unfortunately, thwart them
sharing the same node-updating policies:</para>
<orderedlist>
@@ -4383,7 +4381,7 @@
<listitem><para>Tree-based containers store values in all nodes, while
trie-based containers (at least in this implementation) store
- values in leafs.</para></listitem>
+ values in leaves.</para></listitem>
</orderedlist>
<para>The graphic below shows the scheme, as well as some predefined
@@ -4570,7 +4568,7 @@
<section xml:id="container.list.details.policies">
<info><title>Policies</title></info>
- <para>this library allows instantiating lists with policies
+ <para>This library allows instantiating lists with policies
implementing any algorithm moving nodes to the front of the
list (policies implementing algorithms interchanging nodes are
unsupported).</para>
@@ -4612,10 +4610,10 @@
is <classname>lu_counter_policy</classname>, which implements the
counter algorithm described above. The second is
<classname>lu_move_to_front_policy</classname>,
- which unconditionally move an accessed element to the front of
+ which unconditionally moves an accessed element to the front of
the list. The latter type is very useful in this library,
since there is no need to associate metadata with each element.
- (See <xref linkend="biblio.andrew04mtf"/>
+ (See <xref linkend="biblio.andrew04mtf"/>).
</para>
</section>
@@ -4713,7 +4711,7 @@
</orderedlist>
<para>The <classname>Tag</classname> parameter specifies which underlying
- data structure to use. Instantiating it by<classname>pairing_heap_tag</classname>,<classname>binary_heap_tag</classname>,
+ data structure to use. Instantiating it by <classname>pairing_heap_tag</classname>, <classname>binary_heap_tag</classname>,
<classname>binomial_heap_tag</classname>,
<classname>rc_binomial_heap_tag</classname>,
or <classname>thin_heap_tag</classname>,
@@ -4740,9 +4738,9 @@
insufficient for manipulating priority-queues. </para>
<para>Different settings require different priority-queue
- implementations which are described in later; see traits
- discusses ways to differentiate between the different traits of
- different implementations.</para>
+ implementations which are described later; see
+ <xref linkend="container.priority_queue.details.traits"/>, which
+ discusses ways to differentiate between implementations.</para>
</section>
@@ -4887,12 +4885,12 @@
<orderedlist>
<listitem><para>
Instantiating <classname>Tag = binary_heap_tag</classname> creates
- a binary heap of the form in represented in the graphic with labels A1 or A2. The former is internally
+ a binary heap of the form represented in the graphic with labels A1 or A2. The former is internally
selected by priority_queue
if <classname>Value_Type</classname> is instantiated by a primitive type
(e.g., an <type>int</type>); the latter is
internally selected for all other types (e.g.,
- <classname>std::string</classname>). This implementations is relatively
+ <classname>std::string</classname>). This implementation is relatively
unstructured, and so has good <classname>push</classname> and <classname>pop</classname>
performance; it is the "best-in-kind" for primitive
types, e.g., <type>int</type>s. Conversely, it has
@@ -4901,11 +4899,11 @@
<listitem><para>Instantiating <classname>Tag =
pairing_heap_tag</classname> creates a pairing heap of the form
- in represented by label B in the graphic above. This
- implementations too is relatively unstructured, and so has good
+ represented by label B in the graphic above. This
+ implementation too is relatively unstructured, and so has good
<function>push</function> and <function>pop</function>
performance; it is the "best-in-kind" for non-primitive types,
- e.g., <classname>std:string</classname>s. It also has very good
+ e.g., <classname>std::string</classname>s. It also has very good
worst-case <function>push</function> and
<function>join</function> performance (O(1)), but has high
worst-case <function>pop</function>
@@ -4913,8 +4911,8 @@
<listitem><para>Instantiating <classname>Tag =
binomial_heap_tag</classname> creates a binomial heap of the
- form repsented by label B in the graphic above. This
- implementations is more structured than a pairing heap, and so
+ form represented by label B in the graphic above. This
+ implementation is more structured than a pairing heap, and so
has worse <function>push</function> and <function>pop</function>
performance. Conversely, it has sub-linear worst-case bounds for
<function>pop</function>, e.g., and so it might be preferred in
@@ -4923,7 +4921,7 @@
<listitem><para>Instantiating <classname>Tag =
rc_binomial_heap_tag</classname> creates a binomial heap of the
form represented in label B above, accompanied by a redundant
- counter which governs the trees. This implementations is
+ counter which governs the trees. This implementation is
therefore more structured than a binomial heap, and so has worse
<function>push</function> and <function>pop</function>
performance. Conversely, it guarantees O(1)
@@ -4934,7 +4932,7 @@
<listitem><para>Instantiating <classname>Tag =
thin_heap_tag</classname> creates a thin heap of the form
represented by the label B in the graphic above. This
- implementations too is more structured than a pairing heap, and
+ implementation too is more structured than a pairing heap, and
so has worse <function>push</function> and
<function>pop</function> performance. Conversely, it has better
worst-case and identical amortized complexities than a Fibonacci
@@ -4960,8 +4958,8 @@
<info><title>Traits</title></info>
<para>It would be nice if all priority queues could
- share exactly the same behavior regardless of implementation. Sadly, this is not possible. Just one for instance is in join operations: joining
- two binary heaps might throw an exception (not corrupt
+ share exactly the same behavior regardless of implementation. Sadly, this is not possible. Just one example is in join operations: joining
+ two binary heaps might throw an exception (but not corrupt
any of the heaps on which it operates), but joining two pairing
heaps is exception free.</para>
diff --git a/libstdc++-v3/doc/xml/manual/test_policy_data_structures.xml b/libstdc++-v3/doc/xml/manual/test_policy_data_structures.xml
index cb5b016569ac..8170dfadd1cc 100644
--- a/libstdc++-v3/doc/xml/manual/test_policy_data_structures.xml
+++ b/libstdc++-v3/doc/xml/manual/test_policy_data_structures.xml
@@ -23,7 +23,7 @@
<para>Additionally, the test integrally checks exception safety
and resource leaks. This is done as follows. A special
allocator type, written for the purpose of the test, both
- randomly throws an exceptions when allocations are performed,
+ randomly throws exceptions when allocations are performed,
and tracks allocations and de-allocations. The exceptions thrown
at allocations simulate memory-allocation failures; the
tracking mechanism checks for memory-related bugs (e.g.,
@@ -31,7 +31,7 @@
this library's containers and the containers' value-types are
configured to use this allocator.</para>
- <para>For granularity, the test is split into the
+ <para>For granularity, the test is split into
several sources, each checking only some containers.</para>
<para>For more details, consult the files in
@@ -64,7 +64,7 @@
arbitrary text (<xref
linkend="biblio.wickland96thirty"/>) into a container,
then performs a series of finds using
- <function>find</function> . It measures the average
+ <function>find</function>. It measures the average
time for <function>find</function> as a function of
the number of values inserted.</para>
<para>
@@ -88,7 +88,7 @@
Results
</title></info>
- <para>The graphic below show the results for the native
+ <para>The graphic below shows the results for the native
and collision-chaining hash types the function
applied being a text find timing test using
<function>find</function>.
@@ -368,8 +368,8 @@
entry affects performance only marginally, at least in this
library's implementation. (Unfortunately, it was not possible to run
the tests with <classname>std::tr1::unordered_map</classname> 's
- <classname>cache_hash_code = true</classname> , as it appeared to
- malfuntion.)</para>
+ <classname>cache_hash_code = true</classname>, as it appeared to
+ malfunction.)</para>
</section>
@@ -1882,7 +1882,7 @@
<para>In this setting, as in Hash-Based Text
<function>find</function> Find Timing test and Hash-Based
- Integer <function>find</function> Find Timing test , the choice
+ Integer <function>find</function> Find Timing test, the choice
of underlying hash-table underlying hash-table affects performance
most, then the range-hashing scheme, and
finally any other policies.</para>
@@ -1960,7 +1960,7 @@
Results
</title></info>
- <para>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
+ <para>The graphic below shows the results for the native, collision-chaining, and general-probing hash types.
</para>
<!-- results graphic -->
@@ -2257,7 +2257,7 @@
Results
</title></info>
- <para>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
+ <para>The graphic below shows the results for the native, collision-chaining, and general-probing hash types.
</para>
<!-- results graphic -->
@@ -2514,7 +2514,7 @@
<para>This test inserts a number of values with keys from an arbitrary
text ([wickland96thirty]) into a container
- using <function>insert</function> . It measures the average time
+ using <function>insert</function>. It measures the average time
for <function>insert</function> as a function of the number of
values inserted.</para>
@@ -3808,7 +3808,7 @@
<para>In this test, the native red-black tree can support
order-statistics queries only externally, by performing a
<classname>find</classname> (alternatively, <classname>lower_bound</classname> or
- <classname>upper_bound</classname> ) and then using <classname>std::distance</classname> .
+ <classname>upper_bound</classname>) and then using <classname>std::distance</classname>.
This is clearly linear, and it is not that surprising that the
cost is high.</para>
<para>This library's tree-based containers use in this test the
@@ -3816,10 +3816,10 @@
This method has only linear complexity in the length of the
root-node path. Unfortunately, the average path of a splay tree
(<classname>tree</classname>
- with <classname>Tag =</classname> <classname>splay_tree_tag</classname> ) can
+ with <classname>Tag =</classname> <classname>splay_tree_tag</classname>) can
be higher than logarithmic; the longest path of a red-black
tree (<classname>tree</classname>
- with <classname>Tag =</classname> <classname>rb_tree_tag</classname> ) is
+ with <classname>Tag =</classname> <classname>rb_tree_tag</classname>) is
logarithmic in the number of elements. Consequently, the splay
tree has worse performance than the red-black tree.</para>
</section>
@@ -3875,7 +3875,7 @@
Results
</title></info>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</para>
@@ -4061,7 +4061,7 @@
</informaltable>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</para>
@@ -4338,7 +4338,7 @@
Results
</title></info>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</para>
@@ -4524,7 +4524,7 @@
</informaltable>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</para>
@@ -4805,7 +4805,7 @@
Results
</title></info>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</para>
@@ -4991,7 +4991,7 @@
</informaltable>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</para>
@@ -5272,7 +5272,7 @@
Results
</title></info>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</para>
@@ -5458,7 +5458,7 @@
</informaltable>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</para>
@@ -5733,7 +5733,7 @@
Results
</title></info>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</para>
@@ -5919,7 +5919,7 @@
</informaltable>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</para>
@@ -6193,7 +6193,7 @@
Results
</title></info>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a tree-based container for primary keys.
</para>
@@ -6379,7 +6379,7 @@
</informaltable>
- <para>The graphic below show the results for "multimaps" which
+ <para>The graphic below shows the results for "multimaps" which
use a hash-based container for primary keys.
</para>
@@ -7018,8 +7018,8 @@
<para>This test inserts a number of values with keys from an
arbitrary text ([ wickland96thirty ]) into
- a container using <classname>push</classname> , then removes them using
- <classname>pop</classname> . It measures the average time for <classname>push</classname>
+ a container using <classname>push</classname>, then removes them using
+ <classname>pop</classname>. It measures the average time for <classname>push</classname>
as a function of the number of values.</para>
@@ -7737,8 +7737,8 @@
</title></info>
<para>This test inserts a number of values with integer keys
- into a container using <function>push</function> , then removes them
- using <function>pop</function> . It measures the average time for
+ into a container using <function>push</function>, then removes them
+ using <function>pop</function>. It measures the average time for
<function>push</function> and <function>pop</function> as a function
of the number of values.</para>
@@ -9211,7 +9211,7 @@
byproduct of the tree-like structure is required: either
order-preservation, or the ability to utilize node invariants. If
memory-use is the major factor, an ordered-vector tree gives
- optimal results (albeit with high modificiation costs), and a
+ optimal results (albeit with high modification costs), and a
list-based container gives reasonable results.</para>
</section>
diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
index 3e399c73d433..244caad35041 100644
--- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
@@ -58,7 +58,7 @@ namespace __gnu_pbds
#define PB_DS_BRANCH_POLICY_BASE \
detail::branch_policy<Node_CItr, Node_Itr, _Alloc>
- /// Functor updating ranks of entrees.
+ /// Functor updating ranks of entries.
template<typename Node_CItr, typename Node_Itr,
typename Cmp_Fn, typename _Alloc>
class tree_order_statistics_node_update : private PB_DS_BRANCH_POLICY_BASE
diff --git a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
index a08d81251027..23d8a72ba9c5 100644
--- a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
@@ -245,7 +245,7 @@ namespace __gnu_pbds
trie_order_statistics_node_update<Node_CItr, Node_Itr, \
_ATraits, _Alloc>
- /// Functor updating ranks of entrees.
+ /// Functor updating ranks of entries.
template<typename Node_CItr,
typename Node_Itr,
typename _ATraits,
More information about the Libstdc++-cvs
mailing list