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

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++ 2014
C++ 2017
Implementation Specific Behavior
C++ 202a
Implementation Specific Behavior
C++ TR1
Implementation Specific Behavior
C++ TR 24733
C++ IS 29124
Implementation Specific Behavior
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
Dual ABI
Troubleshooting
Namespaces
Available Namespaces
namespace std
Using Namespace Composition
Linking
Almost Nothing
Finding Dynamic or Shared Libraries
Experimental Library Extensions
Concurrency
Prerequisites
Thread Safety
Atomics
IO
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
Non-memory leaks in Pool and MT allocators
Data Race Hunting
Using gdb
Tracking uncaught exceptions
Debug Mode
Compile Time Checking
II. Standard Contents
4. Support
Types
Fundamental Types
Numeric Properties
NULL
Dynamic Memory
Additional Notes
Termination
Termination Handlers
Verbose Terminate Handler
5. Diagnostics
Exceptions
API Reference
Adding Data to exception
Use of errno by the library
Concept Checking
6. Utilities
Functors
Pairs
Memory
Allocators
Requirements
Design Issues
Implementation
Interface Design
Selecting Default Allocation Policy
Disabling Memory Caching
Using a Specific Allocator
Custom Allocators
Extension Allocators
auto_ptr
Limitations
Use in Containers
shared_ptr
Requirements
Design Issues
Implementation
Class Hierarchy
Thread Safety
Selecting Lock Policy
Related functions and classes
Use
Examples
Unresolved Issues
Acknowledgments
Traits
7. Strings
String Classes
Simple Transformations
Case Sensitivity
Arbitrary Character Types
Tokenizing
Shrink to Fit
CString (MFC)
8. Localization
Locales
locale
Requirements
Design
Implementation
Interacting with "C" locales
Future
Facets
ctype
Implementation
Specializations
Future
codecvt
Requirements
Design
wchar_t Size
Support for Unicode
Other Issues
Implementation
Use
Future
messages
Requirements
Design
Implementation
Models
The GNU Model
Use
Future
9. Containers
Sequences
list
list::size() is O(n)
Associative
Insertion Hints
bitset
Size Variable
Type String
Unordered Associative
Insertion Hints
Hash Code
Hash Code Caching Policy
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
17. Debug Mode
Intro
Semantics
Using
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
Testing
Bibliography
19. The mt_allocator
Intro
Design Issues
Overview
Implementation
Tunable Parameters
Initialization
Deallocation Notes
Single Thread Example
Multiple Thread Example
20. The bitmap_allocator
Design
Implementation
Free List Store
Super Block
Super Block Data Layout
Maximum Wasted Percentage
allocate
deallocate
Questions
1
2
3
Locality
Overhead and Grow Policy
21. 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
Using
Prerequisites
Organization
Tutorial
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
Testing
Regression
Performance
Hash-Based
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
22. HP/SGI Extensions
Backwards Compatibility
Deprecated
23. Utilities
24. Algorithms
25. Numerics
26. Iterators
27. Input and Output
Derived filebufs
28. Demangling
29. Concurrency
Design
Interface to Locks and Mutexes
Interface to Atomic Functions
Implementation
Using Built-in 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
General Process
What Comes from Where
Configure
Storing Information in non-AC files (like configure.host)
Coding and Commenting Conventions
The acinclude.m4 layout
GLIBCXX_ENABLE, the --enable maker
Shared Library Versioning
Make
Writing and Generating Documentation
Introduction
Generating Documentation
Doxygen
Prerequisites
Generating the Doxygen Files
Debugging Generation
Markup
Docbook
Prerequisites
Generating the DocBook Files
Debugging Generation
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
Testing
Test Organization
Directory Layout
Naming Conventions
Running the Testsuite
Basic
Variations
Permutations
Writing a new test case
Examples of Test Directives
Directives Specific to Libstdc++ Tests
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
4.6
4.7
4.8
4.9
5
5.3
6
7
7.2
7.3
8
9
10
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 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

21.1. Node Invariants
21.2. Underlying Associative Data Structures
21.3. Range Iteration in Different Data Structures
21.4. Point Iteration in Hash Data Structures
21.5. Effect of erase in different underlying data structures
21.6. Underlying Priority Queue Data Structures
21.7. Exception Hierarchy
21.8. Non-unique Mapping Standard Containers
21.9. Effect of embedded lists in std::multimap
21.10. Non-unique Mapping Containers
21.11. Point Iterator Hierarchy
21.12. Invalidation Guarantee Tags Hierarchy
21.13. Container Tag Hierarchy
21.14. Hash functions, ranged-hash functions, and range-hashing functions
21.15. Insert hash sequence diagram
21.16. Insert hash sequence diagram with a null policy
21.17. Hash policy class diagram
21.18. Balls and bins
21.19. Insert resize sequence diagram
21.20. Standard resize policy trigger sequence diagram
21.21. Standard resize policy size sequence diagram
21.22. Tree node invariants
21.23. Tree node invalidation
21.24. A tree and its update policy
21.25. Restoring node invariants
21.26. Insert update sequence
21.27. Useless update path
21.28. A PATRICIA trie
21.29. A trie and its update policy
21.30. A simple list
21.31. The counter algorithm
21.32. Underlying Priority-Queue Data-Structures.
21.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++ 2014 Implementation Status
1.4. C++ Technical Specifications Implementation Status
1.5. C++ 2017 Implementation Status
1.6. C++ Technical Specifications Implementation Status
1.7. C++ 2020 Implementation Status
1.8. C++ TR1 Implementation Status
1.9. C++ TR 24733 Implementation Status
1.10. C++ Special Functions 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++ 1998 Deprecated Library Header
3.5. C++ 2011 Library Headers
3.6. C++ 2011 Library Headers for C Library Facilities
3.7. C++ 2014 Library Header
3.8. C++ 2017 Library Headers
3.9. C++ 2020 Library Headers
3.10. C++ 2020 Obsolete Headers
3.11. File System TS Header
3.12. Library Fundamentals TS Headers
3.13. C++ TR 1 Library Headers
3.14. C++ TR 1 Library Headers for C Library Facilities
3.15. C++ TR 24733 Decimal Floating-Point Header
3.16. C++ ABI Headers
3.17. Extension Headers
3.18. Extension Debug Headers
3.19. Extension Parallel Headers
17.1. Debugging Containers
17.2. Debugging Containers C++11
18.1. Parallel Algorithms
20.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

21.1. Ranged Hash Function
21.2. Range-Hashing, Division Method
21.3. Division via Prime Modulo
21.4. Division via Bit Mask
21.5. A Standard String Hash Function
21.6. Only k String DNA Hash
21.7. Probability of Probe Sequence of Length k
21.8. Probability Probe Sequence in Some Bin