Part III. Extensions
Prev	The GNU C++ Library Manual	Next

Part III. Extensions

Table of Contents

16. Compile Time Checks

Using the Debug Mode
Using a Specific Debug Container

Design

Goals

Methods

The Wrapper Model

Safe Iterators
Safe Sequences (Containers)

Precondition Checking

Release- and debug-mode coexistence

Compile-time coexistence of release- and debug-mode components
Link- and run-time coexistence of release- and debug-mode components
Alternatives for Coexistence

Other Implementations

18. Parallel Mode

Intro

Semantics

Using

Prerequisite Compiler Flags
Using Parallel Mode
Using Specific Parallel Components

Design

Interface Basics

Configuration and Tuning

Setting up the OpenMP Environment
Compile Time Switches
Run Time Settings and Defaults

Implementation Namespaces

Using the Profile Mode
Tuning the Profile Mode

Design

Wrapper Model
Instrumentation
Run Time Behavior
Analysis and Diagnostics
Cost Model
Reports
Testing

Extensions for Custom Containers

Empirical Cost Model

Implementation Issues

Stack Traces
Symbolization of Instruction Addresses
Concurrency
Using the Standard Library in the Instrumentation Implementation
Malloc Hooks
Construction and Destruction of Global Objects

Developer Information

Big Picture
How To Add A Diagnostic

Diagnostics

Diagnostic Template

Containers

Hashtable Too Small
Hashtable Too Large
Inefficient Hash
Vector Too Small
Vector Too Large
Vector to Hashtable
Hashtable to Vector
Vector to List
List to Vector
List to Forward List (Slist)
Ordered to Unordered Associative Container

Algorithms

Sort Algorithm Performance

Data Locality

Need Software Prefetch
Linked Structure Locality

Multithreaded Data Access

Data Dependence Violations at Container Level
False Sharing

Statistics

Bibliography

20. The mt_allocator

Intro

Design Issues

Overview

Implementation

Tunable Parameters
Initialization
Deallocation Notes

Single Thread Example

Multiple Thread Example

21. The bitmap_allocator

Super Block Data Layout

Maximum Wasted Percentage

allocate

deallocate

Questions

1
2
3

Locality

Overhead and Grow Policy

22. Policy-Based Data Structures

Intro

Performance Issues

Associative
Priority Que

Goals

Associative

Policy Choices
Underlying Data Structures
Iterators
Functional

Priority Queues

Policy Choices
Underlying Data Structures
Binary Heaps

Basic Use
Configuring via Template Parameters
Querying Container Attributes
Point and Range Iteration

Examples

Intermediate Use

Querying with container_traits

By Container Method

Hash-Based
Branch-Based
Priority Queues

Design

Concepts

Null Policy Classes

Map and Set Semantics

Distinguishing Between Maps and Sets
Alternatives to std::multiset and std::multimap

Iterator Semantics

Point and Range Iterators
Distinguishing Point and Range Iterators
Invalidation Guarantees

Genericity

Tag
Traits

By Container

hash

Interface
Details

tree

Interface
Details

Trie

Interface
Details

List

Interface
Details

Priority Queue

Interface
Details

Text find
Integer find
Integer Subscript find
Integer Subscript insert
Integer find with Skewed-Distribution
Erase Memory Use

Branch-Based

Text insert
Text find
Text find with Locality-of-Reference
split and join
Order-Statistics

Multimap

Text find with Small Secondary-to-Primary Key Ratios
Text find with Large Secondary-to-Primary Key Ratios
Text insert with Small Secondary-to-Primary Key Ratios
Text insert with Small Secondary-to-Primary Key Ratios
Text insert with Small Secondary-to-Primary Key Ratios Memory Use
Text insert with Small Secondary-to-Primary Key Ratios Memory Use

Priority Queue

Text push
Text push and pop
Integer push
Integer push
Text pop Memory Use
Text join
Text modify Up
Text modify Down

Observations

Associative
Priority_Queue

Acknowledgments

Bibliography

23. HP/SGI Extensions

Backwards Compatibility
Deprecated

28. Input and Output

Derived filebufs

29. Demangling

30. Concurrency

Design

Interface to Locks and Mutexes
Interface to Atomic Functions

Implementation

Using Built-in Atomic Functions
Thread Abstraction

Use