The GNU C++ Library Manual
Prev		Next

The GNU C++ Library Manual

Paolo Carlini

Phil Edwards

Doug Gregor

Benjamin Kosnik

Dhruv Matani

Jason Merrill

Mark Mitchell

Nathan Myers

Felix Natter

Stefan Olsson

Silvius Rus

Johannes Singler

Ami Tavory

Jonathan Wakely

Table of Contents

I. Introduction

1. Status

Implementation Status

C++ 1998/2003

Implementation Status
Implementation Specific Behavior

C++ 2011

Implementation Specific Behavior

C++ TR1

Implementation Specific Behavior

C++ TR 24733

License

The Code: GPL
The Documentation: GPL, FDL

Bugs

Implementation Bugs
Standard Bugs

2. Setup

Prerequisites
Configure
Make

3. Using

Command Options

Headers

Header Files
Mixing Headers
The C Headers and namespace std
Precompiled Headers

Macros

Namespaces

Available Namespaces
namespace std
Using Namespace Composition

Linking

Almost Nothing
Finding Dynamic or Shared Libraries

Structure
Defaults
Future
Alternatives

Containers

Exceptions

Exception Safety

Exception Neutrality

Doing without

Compatibility

With C
With POSIX thread cancellation

Debugging Support

Using g++
Debug Versions of Library Binary Files
Memory Leak Hunting
Data Race Hunting
Using gdb
Tracking uncaught exceptions
Debug Mode
Compile Time Checking
Profile-based Performance Analysis

II. Standard Contents

4. Support

Types

Fundamental Types
Numeric Properties
NULL

Dynamic Memory

Termination

Termination Handlers
Verbose Terminate Handler

5. Diagnostics

Exceptions

API Reference
Adding Data to exception

Interface Design
Selecting Default Allocation Policy
Disabling Memory Caching

Using a Specific Allocator

Custom Allocators

Extension Allocators

auto_ptr

Limitations
Use in Containers

Class Hierarchy
Thread Safety
Selecting Lock Policy
Related functions and classes

Use

Examples
Unresolved Issues

Simple Transformations
Case Sensitivity
Arbitrary Character Types
Tokenizing
Shrink to Fit
CString (MFC)

Interacting with "C" locales

Specializations

wchar_t Size
Support for Unicode
Other Issues

Models
The GNU Model

list::size() is O(n)

vector

Space Overhead Management

Associative

Insertion Hints

bitset

Size Variable
Type String

Interacting with C

Containers vs. Arrays

10. Iterators

Predefined

Iterators vs. Pointers
One Past the End

11. Algorithms

Mutating

swap

Specializations

12. Numerics

Complex

complex Processing

Generalized Operations

Interacting with C

Numerics vs. Arrays
C99

13. Input and Output

Iostream Objects

Stream Buffers

Derived streambuf Classes
Buffering

Memory Based Streams

Compatibility With strstream

File Based Streams

Copying a File
Binary Input and Output

Interacting with C

Using FILE* and file descriptors
Performance

14. Atomics

API Reference

15. Concurrency

API Reference

III. Extensions

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 Builtin Atomic Functions
Thread Abstraction

Use

IV. Appendices

A. Contributing

Contributor Checklist

Reading
Assignment
Getting Sources
Submitting Patches

Directory Layout and Source Conventions

Coding Style

Bad Identifiers
By Example

Design Notes

B. Porting and Maintenance

Configure and Build Hacking

Prerequisites
Overview: What Comes from Where
Storing Information in non-AC files (like configure.host)
Coding and Commenting Conventions
The acinclude.m4 layout
GLIBCXX_ENABLE, the --enable maker

Writing and Generating Documentation

Introduction

Generating Documentation

Doxygen

Prerequisites
Generating the Doxygen Files
Markup

Docbook

Prerequisites
Generating the DocBook Files
Editing and Validation
File Organization and Basics
Markup By Example

Porting to New Hardware or Operating Systems

Operating System
CPU
Character Types
Thread Safety
Numeric Limits
Libtool

Test

Organization

Directory Layout
Naming Conventions

Running the Testsuite

Basic
Variations
Permutations

Writing a new test case

Test Harness and Utilities

Dejagnu Harness Details
Utilities

Special Topics

Qualifying Exception Safety Guarantees

Overview
Existing tests
C++11 Requirements Test Sequence Descriptions

ABI Policy and Guidelines

The C++ Interface

Versioning

Goals
History
Prerequisites
Configuring
Checking Active

Allowed Changes

Prohibited Changes

Implementation

Testing

Single ABI Testing
Multiple ABI Testing

Outstanding Issues

API Evolution and Deprecation History

3.0
3.1
3.2
3.3
3.4
4.0
4.1
4.2
4.3
4.4
4.5

Backwards Compatibility

First

No ios_base
No cout in <ostream.h>, no cin in <istream.h>

Second

Namespace std:: not supported
Illegal iterator usage
isspace from <cctype> is a macro
No vector::at, deque::at, string::at
No std::char_traits<char>::eof
No string::clear
Removal of ostream::form and istream::scan extensions
No basic_stringbuf, basic_stringstream
Little or no wide character support
No templatized iostreams
Thread safety issues

Third

Pre-ISO headers moved to backwards or removed
Extension headers hash_map, hash_set moved to ext or backwards
No ios::nocreate/ios::noreplace.
No stream::attach(int fd)
Support for C++98 dialect.
Support for C++TR1 dialect.
Support for C++11 dialect.
Container::iterator_type is not necessarily Container::value_type*

C. Free Software Needs Free Documentation

D. GNU General Public License version 3

E. GNU Free Documentation License

List of Figures

22.1. Node Invariants
22.2. Underlying Associative Data Structures
22.3. Range Iteration in Different Data Structures
22.4. Point Iteration in Hash Data Structures
22.5. Effect of erase in different underlying data structures
22.6. Underlying Priority Queue Data Structures
22.7. Exception Hierarchy
22.8. Non-unique Mapping Standard Containers
22.9. Effect of embedded lists in std::multimap
22.10. Non-unique Mapping Containers
22.11. Point Iterator Hierarchy
22.12. Invalidation Guarantee Tags Hierarchy
22.13. Container Tag Hierarchy
22.14. Hash functions, ranged-hash functions, and range-hashing functions
22.15. Insert hash sequence diagram
22.16. Insert hash sequence diagram with a null policy
22.17. Hash policy class diagram
22.18. Balls and bins
22.19. Insert resize sequence diagram
22.20. Standard resize policy trigger sequence diagram
22.21. Standard resize policy size sequence diagram
22.22. Tree node invariants
22.23. Tree node invalidation
22.24. A tree and its update policy
22.25. Restoring node invariants
22.26. Insert update sequence
22.27. Useless update path
22.28. A PATRICIA trie
22.29. A trie and its update policy
22.30. A simple list
22.31. The counter algorithm
22.32. Underlying Priority-Queue Data-Structures.
22.33. Priority-Queue Data-Structure Tags.
B.1. Configure and Build File Dependencies

List of Tables

1.1. C++ 1998/2003 Implementation Status
1.2. C++ 2011 Implementation Status
1.3. C++ TR1 Implementation Status
1.4. C++ TR 24733 Implementation Status
3.1. C++ Command Options
3.2. C++ 1998 Library Headers
3.3. C++ 1998 Library Headers for C Library Facilities
3.4. C++ 2011 Library Headers
3.5. C++ 2011 Library Headers for C Library Facilities
3.6. C++ TR 1 Library Headers
3.7. C++ TR 1 Library Headers for C Library Facilities
3.8. C++ TR 24733 Decimal Floating-Point Header
3.9. C++ ABI Headers
3.10. Extension Headers
3.11. Extension Debug Headers
3.12. Extension Profile Headers
3.13. Extension Parallel Headers
17.1. Debugging Containers
17.2. Debugging Containers C++11
18.1. Parallel Algorithms
19.1. Profile Code Location
19.2. Profile Diagnostics
21.1. Bitmap Allocator Memory Map
B.1. Doxygen Prerequisites
B.2. HTML to Doxygen Markup Comparison
B.3. Docbook Prerequisites
B.4. HTML to Docbook XML Markup Comparison
B.5. Docbook XML Element Use
B.6. Extension Allocators
B.7. Extension Allocators Continued

List of Equations

22.1. Ranged Hash Function
22.2. Range-Hashing, Division Method
22.3. Division via Prime Modulo
22.4. Division via Bit Mask
22.5. A Standard String Hash Function
22.6. Only k String DNA Hash
22.7. Probability of Probe Sequence of Length k
22.8. Probability Probe Sequence in Some Bin