1 <html><head><meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"><title>Part III. Extensions
</title><meta name=
"generator" content=
"DocBook XSL-NS Stylesheets V1.76.1"><meta name=
"keywords" content=
"
5 "><meta name=
"keywords" content=
"
11 "><link rel=
"home" href=
"../index.html" title=
"The GNU C++ Library"><link rel=
"up" href=
"index.html" title=
"The GNU C++ Library Manual"><link rel=
"prev" href=
"io_and_c.html" title=
"Interacting with C"><link rel=
"next" href=
"bk01pt03pr01.html" title=
""></head><body bgcolor=
"white" text=
"black" link=
"#0000FF" vlink=
"#840084" alink=
"#0000FF"><div class=
"navheader"><table width=
"100%" summary=
"Navigation header"><tr><th colspan=
"3" align=
"center">Part III.
14 </th></tr><tr><td width=
"20%" align=
"left"><a accesskey=
"p" href=
"io_and_c.html">Prev
</a> </td><th width=
"60%" align=
"center">The GNU C++ Library Manual
</th><td width=
"20%" align=
"right"> <a accesskey=
"n" href=
"bk01pt03pr01.html">Next
</a></td></tr></table><hr></div><div class=
"part" title=
"Part III. Extensions"><div class=
"titlepage"><div><div><h1 class=
"title"><a name=
"manual.ext"></a>Part III.
16 <a class=
"indexterm" name=
"id630474"></a>
17 </h1></div></div></div><div class=
"toc"><p><b>Table of Contents
</b></p><dl><dt><span class=
"preface"><a href=
"bk01pt03pr01.html"></a></span></dt><dt><span class=
"chapter"><a href=
"ext_compile_checks.html">16. Compile Time Checks
</a></span></dt><dt><span class=
"chapter"><a href=
"debug_mode.html">17. 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=
"bk01pt03ch17s02.html">Semantics
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s03.html">Using
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch17s03.html#debug_mode.using.mode">Using the Debug Mode
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s03.html#debug_mode.using.specific">Using a Specific Debug Container
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html">Design
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.goals">Goals
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.methods">Methods
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.methods.wrappers">The Wrapper Model
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.methods.safe_iter">Safe Iterators
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.methods.safe_seq">Safe Sequences (Containers)
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.methods.precond">Precondition Checking
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.methods.coexistence">Release- and debug-mode coexistence
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#methods.coexistence.compile">Compile-time coexistence of release- and debug-mode components
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#methods.coexistence.link">Link- and run-time coexistence of release- and
18 debug-mode components
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#methods.coexistence.alt">Alternatives for Coexistence
</a></span></dt></dl></dd></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch17s04.html#debug_mode.design.other">Other Implementations
</a></span></dt></dl></dd></dl></dd><dt><span class=
"chapter"><a href=
"parallel_mode.html">18. 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=
"bk01pt03ch18s02.html">Semantics
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch18s03.html">Using
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch18s03.html#parallel_mode.using.prereq_flags">Prerequisite Compiler Flags
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch18s03.html#parallel_mode.using.parallel_mode">Using Parallel Mode
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch18s03.html#parallel_mode.using.specific">Using Specific Parallel Components
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html">Design
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html#parallel_mode.design.intro">Interface Basics
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html#parallel_mode.design.tuning">Configuration and Tuning
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html#parallel_mode.design.tuning.omp">Setting up the OpenMP Environment
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html#parallel_mode.design.tuning.compile">Compile Time Switches
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html#parallel_mode.design.tuning.settings">Run Time Settings and Defaults
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch18s04.html#parallel_mode.design.impl">Implementation Namespaces
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch18s05.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=
"profile_mode.html">19. Profile Mode
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"profile_mode.html#manual.ext.profile_mode.intro">Intro
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"profile_mode.html#manual.ext.profile_mode.using">Using the Profile Mode
</a></span></dt><dt><span class=
"section"><a href=
"profile_mode.html#manual.ext.profile_mode.tuning">Tuning the Profile Mode
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html">Design
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.wrapper">Wrapper Model
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.instrumentation">Instrumentation
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.rtlib">Run Time Behavior
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.analysis">Analysis and Diagnostics
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.cost-model">Cost Model
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.reports">Reports
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s02.html#manual.ext.profile_mode.design.testing">Testing
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s03.html">Extensions for Custom Containers
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s04.html">Empirical Cost Model
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html">Implementation Issues
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html#manual.ext.profile_mode.implementation.stack">Stack Traces
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html#manual.ext.profile_mode.implementation.symbols">Symbolization of Instruction Addresses
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html#manual.ext.profile_mode.implementation.concurrency">Concurrency
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html#manual.ext.profile_mode.implementation.stdlib-in-proflib">Using the Standard Library in the Instrumentation Implementation
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html#manual.ext.profile_mode.implementation.malloc-hooks">Malloc Hooks
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s05.html#manual.ext.profile_mode.implementation.construction-destruction">Construction and Destruction of Global Objects
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s06.html">Developer Information
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s06.html#manual.ext.profile_mode.developer.bigpic">Big Picture
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s06.html#manual.ext.profile_mode.developer.howto">How To Add A Diagnostic
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html">Diagnostics
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.template">Diagnostic Template
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.containers">Containers
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.hashtable_too_small">Hashtable Too Small
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.hashtable_too_large">Hashtable Too Large
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.inefficient_hash">Inefficient Hash
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_too_small">Vector Too Small
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_too_large">Vector Too Large
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_to_hashtable">Vector to Hashtable
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.hashtable_to_vector">Hashtable to Vector
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.vector_to_list">Vector to List
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.list_to_vector">List to Vector
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.list_to_slist">List to Forward List (Slist)
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.assoc_ord_to_unord">Ordered to Unordered Associative Container
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.algorithms">Algorithms
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.algorithms.sort">Sort Algorithm Performance
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.locality">Data Locality
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.locality.sw_prefetch">Need Software Prefetch
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.locality.linked">Linked Structure Locality
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.mthread">Multithreaded Data Access
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.mthread.ddtest">Data Dependence Violations at Container Level
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.mthread.false_share">False Sharing
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch19s07.html#manual.ext.profile_mode.analysis.statistics">Statistics
</a></span></dt></dl></dd><dt><span class=
"bibliography"><a href=
"profile_mode.html#profile_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=
"bk01pt03ch20s02.html">Design Issues
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch20s02.html#allocator.mt.overview">Overview
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch20s03.html">Implementation
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch20s03.html#allocator.mt.tune">Tunable Parameters
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch20s03.html#allocator.mt.init">Initialization
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch20s03.html#allocator.mt.deallocation">Deallocation Notes
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch20s04.html">Single Thread Example
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch20s05.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=
"bk01pt03ch21s02.html">Implementation
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.free_list_store">Free List Store
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.super_block">Super Block
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.super_block_data">Super Block Data Layout
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.max_wasted">Maximum Wasted Percentage
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.allocate"><code class=
"function">allocate
</code></a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.deallocate"><code class=
"function">deallocate
</code></a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.questions">Questions
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.question.1">1</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.question.2">2</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.question.3">3</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch21s02.html#bitmap.impl.locality">Locality
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch21s02.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">
19 Configuring via Template Parameters
20 </a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.tutorial.traits">
21 Querying Container Attributes
22 </a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.tutorial.point_range_iteration">
23 Point and Range Iteration
24 </a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples">Examples
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples.basic">Intermediate Use
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples.query">Querying with
<code class=
"classname">container_traits
</code> </a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples.container">By Container Method
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples.container.hash">Hash-Based
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples.container.branch">Branch-Based
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_using.html#pbds.using.examples.container.priority_queue">Priority Queues
</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html">Design
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.concepts">Concepts
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.concepts.null_type">Null Policy Classes
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.concepts.associative_semantics">Map and Set Semantics
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#concepts.associative_semantics.set_vs_map">
25 Distinguishing Between Maps and Sets
26 </a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#concepts.associative_semantics.multi">Alternatives to
<code class=
"classname">std::multiset
</code> and
<code class=
"classname">std::multimap
</code></a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.concepts.iterator_semantics">Iterator Semantics
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#concepts.iterator_semantics.point_and_range">Point and Range Iterators
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#concepts.iterator_semantics.both">Distinguishing Point and Range Iterators
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.concepts.invalidation">Invalidation Guarantees
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.concepts.genericity">Genericity
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#concepts.genericity.tag">Tag
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#concepts.genericity.traits">Traits
</a></span></dt></dl></dd></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.container">By Container
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.container.hash">hash
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.hash.interface">Interface
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.hash.details">Details
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.container.tree">tree
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.tree.interface">Interface
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.tree.details">Details
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.container.trie">Trie
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.trie.interface">Interface
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.trie.details">Details
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.container.list">List
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.list.interface">Interface
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.list.details">Details
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_design.html#pbds.design.container.priority_queue">Priority Queue
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.priority_queue.interface">Interface
</a></span></dt><dt><span class=
"section"><a href=
"policy_data_structures_design.html#container.priority_queue.details">Details
</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html">Testing
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#pbds.test.regression">Regression
</a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#pbds.test.performance">Performance
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash">Hash-Based
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash.text_find">
27 Text
<code class=
"function">find
</code>
28 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash.int_find">
29 Integer
<code class=
"function">find
</code>
30 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash.int_subscript_find">
31 Integer Subscript
<code class=
"function">find
</code>
32 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash.int_subscript_insert">
33 Integer Subscript
<code class=
"function">insert
</code>
34 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash.zlob_int_find">
35 Integer
<code class=
"function">find
</code> with Skewed-Distribution
36 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.hash.erase_mem">
38 </a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.branch">Branch-Based
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.branch.text_insert">
39 Text
<code class=
"function">insert
</code>
40 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.branch.text_find">
41 Text
<code class=
"function">find
</code>
42 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.branch.text_lor_find">
43 Text
<code class=
"function">find
</code> with Locality-of-Reference
44 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.branch.split_join">
45 <code class=
"function">split
</code> and
<code class=
"function">join
</code>
46 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.branch.order_statistics">
48 </a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap">Multimap
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap.text_find_small">
49 Text
<code class=
"function">find
</code> with Small Secondary-to-Primary Key Ratios
50 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap.text_find_large">
51 Text
<code class=
"function">find
</code> with Large Secondary-to-Primary Key Ratios
52 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap.text_insert_small">
53 Text
<code class=
"function">insert
</code> with Small
54 Secondary-to-Primary Key Ratios
55 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap.text_insert_large">
56 Text
<code class=
"function">insert
</code> with Small
57 Secondary-to-Primary Key Ratios
58 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap.text_insert_mem_small">
59 Text
<code class=
"function">insert
</code> with Small
60 Secondary-to-Primary Key Ratios Memory Use
61 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.multimap.text_insert_mem_large">
62 Text
<code class=
"function">insert
</code> with Small
63 Secondary-to-Primary Key Ratios Memory Use
64 </a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue">Priority Queue
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.text_push">
65 Text
<code class=
"function">push
</code>
66 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.text_push_pop">
67 Text
<code class=
"function">push
</code> and
<code class=
"function">pop
</code>
68 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.int_push">
69 Integer
<code class=
"function">push
</code>
70 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.int_push_pop">
71 Integer
<code class=
"function">push
</code>
72 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.text_pop">
73 Text
<code class=
"function">pop
</code> Memory Use
74 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.text_join">
75 Text
<code class=
"function">join
</code>
76 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.text_modify_up">
77 Text
<code class=
"function">modify
</code> Up
78 </a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#performance.priority_queue.text_modify_down">
79 Text
<code class=
"function">modify
</code> Down
80 </a></span></dt></dl></dd><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#pbds.test.performance.observations">Observations
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#observations.associative">Associative
</a></span></dt><dt><span class=
"section"><a href=
"policy_based_data_structures_test.html#observations.priority_queue">Priority_Queue
</a></span></dt></dl></dd></dl></dd></dl></dd><dt><span class=
"section"><a href=
"policy_data_structures_biblio.html">Acknowledgments
</a></span></dt><dt><span class=
"bibliography"><a href=
"policy_data_structures.html#pbds.biblio">
82 </a></span></dt></dl></dd><dt><span class=
"chapter"><a href=
"ext_containers.html">23. HP/SGI Extensions
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"ext_containers.html#manual.ext.containers.sgi">Backwards Compatibility
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch23s02.html">Deprecated
</a></span></dt></dl></dd><dt><span class=
"chapter"><a href=
"ext_utilities.html">24. Utilities
</a></span></dt><dt><span class=
"chapter"><a href=
"ext_algorithms.html">25. Algorithms
</a></span></dt><dt><span class=
"chapter"><a href=
"ext_numerics.html">26. Numerics
</a></span></dt><dt><span class=
"chapter"><a href=
"ext_iterators.html">27. Iterators
</a></span></dt><dt><span class=
"chapter"><a href=
"ext_io.html">28. Input and Output
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"ext_io.html#manual.ext.io.filebuf_derived">Derived filebufs
</a></span></dt></dl></dd><dt><span class=
"chapter"><a href=
"ext_demangling.html">29. Demangling
</a></span></dt><dt><span class=
"chapter"><a href=
"ext_concurrency.html">30. Concurrency
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"ext_concurrency.html#manual.ext.concurrency.design">Design
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"ext_concurrency.html#manual.ext.concurrency.design.threads">Interface to Locks and Mutexes
</a></span></dt><dt><span class=
"section"><a href=
"ext_concurrency.html#manual.ext.concurrency.design.atomics">Interface to Atomic Functions
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch30s02.html">Implementation
</a></span></dt><dd><dl><dt><span class=
"section"><a href=
"bk01pt03ch30s02.html#manual.ext.concurrency.impl.atomic_fallbacks">Using Builtin Atomic Functions
</a></span></dt><dt><span class=
"section"><a href=
"bk01pt03ch30s02.html#manual.ext.concurrency.impl.thread">Thread Abstraction
</a></span></dt></dl></dd><dt><span class=
"section"><a href=
"bk01pt03ch30s03.html">Use
</a></span></dt></dl></dd></dl></div></div><div class=
"navfooter"><hr><table width=
"100%" summary=
"Navigation footer"><tr><td width=
"40%" align=
"left"><a accesskey=
"p" href=
"io_and_c.html">Prev
</a> </td><td width=
"20%" align=
"center"><a accesskey=
"u" href=
"index.html">Up
</a></td><td width=
"40%" align=
"right"> <a accesskey=
"n" href=
"bk01pt03pr01.html">Next
</a></td></tr><tr><td width=
"40%" align=
"left" valign=
"top">Interacting with C
</td><td width=
"20%" align=
"center"><a accesskey=
"h" href=
"../index.html">Home
</a></td><td width=
"40%" align=
"right" valign=
"top"> </td></tr></table></div></body></html>