C++ Language Tutorial

Standard Template Library: Containers

A container is a holder object that stores a collection other objects (its elements). They are implemented as class templates, which allows a great flexibility in the types supported as elements.

The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference objects with similar properties to pointers).

Containers replicate structures very commonly used in programming: dynamic arrays (vector), queues (queue), stacks (stack), heaps (priority_queue), linked lists (list), trees (set), associative arrays (map)...

Many containers have several member functions in common, and share functionalities. The decision of which type of container to use for a specific need does not generally depend only on the functionality offered by the container, but also on the efficiency of some of its members (complexity). This is especially true for sequence containers, which offer different trade-offs in complexity between inserting/removing elements and accessing them.

stack, queue and priority_queue are implemented as container adaptors. Container adaptors are not full container classes, but classes that provide a specific interface relying on an object of one of the container classes (such as deque or list) to handle the elements. The underlying container is encapsulated in such a way that its elements are accessed by the members of the container class independently of the underlying container class used.

Container class templates

Sequence containers:

vector

Vector (class template)

deque

Double ended queue (class template)

list	List (class template)

Container adaptors:

stack

LIFO stack (class template)

queue

FIFO queue (class template)

priority_queue

Priority queue (class template)

Associative containers:

set	Set (class template)

multiset

Multiple-key set (class template)

map	Map (class template)

multimap

Multiple-key map (class template)

bitset

Bitset (class template)

Member map

This is a comparison chart with the different member functions present on each of the different containers:

			Sequence containers			Associative containers
Headers
Members		complex	vector	deque	list	set	multiset	map	multimap	bitset
	constructor	*	constructor	constructor	constructor	constructor	constructor	constructor	constructor	constructor
	destructor	O(n)	destructor	destructor	destructor	destructor	destructor	destructor	destructor
	operator=	O(n)	operator=	operator=	operator=	operator=	operator=	operator=	operator=	operators
iterators	begin	O(1)	begin	begin	begin	begin	begin	begin	begin
	end	O(1)	end	end	end	end	end	end	end
	rbegin	O(1)	rbegin	rbegin	rbegin	rbegin	rbegin	rbegin	rbegin
	rend	O(1)	rend	rend	rend	rend	rend	rend	rend
capacity	size	*	size	size	size	size	size	size	size	size
	max_size	*	max_size	max_size	max_size	max_size	max_size	max_size	max_size
	empty	O(1)	empty	empty	empty	empty	empty	empty	empty
	resize	O(n)	resize	resize	resize
element access	front	O(1)	front	front	front
	back	O(1)	back	back	back
	operator[]	*	operator[]	operator[]				operator[]		operator[]
	at	O(1)	at	at
modifiers	assign	O(n)	assign	assign	assign
	insert	*	insert	insert	insert	insert	insert	insert	insert
	erase	*	erase	erase	erase	erase	erase	erase	erase
	swap	O(1)	swap	swap	swap	swap	swap	swap	swap
	clear	O(n)	clear	clear	clear	clear	clear	clear	clear
	push_front	O(1)		push_front	push_front
	pop_front	O(1)		pop_front	pop_front
	push_back	O(1)	push_back	push_back	push_back
	pop_back	O(1)	pop_back	pop_back	pop_back
observers	key_comp	O(1)				key_comp	key_comp	key_comp	key_comp
	value_comp	O(1)				value_comp	value_comp	value_comp	value_comp
operations	find	O(log n)				find	find	find	find
	count	O(log n)				count	count	count	count	count
	lower_bound	O(log n)				lower_bound	lower_bound	lower_bound	lower_bound
	upper_bound	O(log n)				upper_bound	upper_bound	upper_bound	upper_bound
	equal_range	O(log n)				equal_range	equal_range	equal_range	equal_range
unique members			capacity reserve		splice remove remove_if unique merge sort reverse					set reset flip to_ulong to_string test any none

Amortized complexity shown. Legend: O(1) constant <>Container adaptors:

			Container Adaptors
Headers
Members			stack	queue	priority_queue
	constructor	*	constructor	constructor	constructor
capacity	size	O(1)	size	size	size
	empty	O(1)	empty	empty	empty
element access	front	O(1)		front
	back	O(1)		back
	top	O(1)	top		top
modifiers	push	O(1)	push	push	push
	pop	O(1)	pop	pop	pop

Strings library

C++ Strings library

The C++ strings library provides the definitions of the basic_string class, which is a class template specifically designed to manipulate strings of characters of any character type. It also include two specific instantiations: string and wstring, which respectively use char and wchar_t as character types.

string

String class (class)

The characteristics of characters taken into consideration in these classes are not only the type itself, but also a set of traits. These traits are defined by specializing the class template char_traits for the specific type. Default specifications exist for both char and wchar_t:

char_traits

Character traits (class template)

This reference uses as a base the string class, even though this is only one of the possible template instantiations (we believe this provides a better readability):

A set of global functions provide some additional functionality for strings to interact either with other string objects or with objects of other types, mainly through the overloading of operators:

operator+

Add strings (function)

swap	Swap contents of two strings (function)

comparison operators

String comparison operators (function)

The header also declares some functions that extend the functionality of streams (iostream library) to string objects:

getline

Get line from stream (function)

operator<<

Insert string into stream (function)

operator>>

Extract string from istream (function)

Notice that some other operators are also overloaded as members of class string (+=, =, []).

IOstream Library

Standard Input / Output Streams Library

The iostream library is an object-oriented library that provides input and output functionality using streams.

A stream is an abstraction that represents a device on which input and ouput operations are performed. A stream can basically be represented as a source or destination of characters of indefinite length.

Streams are generally associated to a physical source or destination of characters, like a disk file, the keyboard, or the console, so the characters gotten or written to/from our abstraction called stream are physically input/output to the physical device. For example, file streams are C++ objects to manipulate and interact with files; Once a file stream is used to open a file, any input or output operation performed on that stream is physically reflected in the file.

To operate with streams, C++ provides the standard iostream library, which contains the following elements:

Basic class templates

The base of the iostream library is the hierarchy of class templates. The class templates provide most of the functionality of the library in a type-independent fashion.

This is a set of class templates, each one having two template parameters: the char type (charT) parameter, that determines the type of elements that are going to be manipulated and the traits parameter, that provides additional characteristics specific for a particular type of elements.

The class templates in this class hierarchy have the same name as their char-type instantiations but with the prefix basic_. For example, the class template which istream is instantiated from is called basic_istream, the one from which fstream is is called basic_fstream, and so on... The only exception is ios_base, which is by itself type-independent, and therefore is not based on a template, but is a regular class.

Class template instantiations

The library incorporates two standard sets of instantiations of the entire iostream class template hierarchy: one is narrow-oriented, to manipulate elements of type char and another one, wide-oriented, to manipulate elements of type wchar_t.

The narrow-oriented (char type) instantiation is probably the better known part of the iostream library. Classes like ios, istream and ofstream are narrow-oriented. The diagram on top of this page shows the names and relationships of narrow-oriented classes.

The classes of the wide-oriented (wchar_t) instatiation follow the same naming conventions as the narrow-oriented instantiation but with the name of each class and object prefixed with a w character, forming wios, wistream and wofstream, as an example.

Standard objects

As part of the iostream library, the header file declares certain objects that are used to perform input and output operations on the standard input and output.

They are divided in two sets: narrow-oriented objects, which are the popular cin, cout, cerr and clog and their wide-oriented counterparts, declared as wcin, wcout, wcerr and wclog.

Types

The iostream classes barely use fundamental types on their member's prototypes. They generally use defined types that depend on the traits used in their instantiation. For the default char and wchar_t instantiations, types streampos, streamoff and streamsize are used to represent positions, offsets and sizes, respectivelly.

Manipulators

Manipulators are global functions designed to be used together with insertion (<<) and extraction (>>) operators performed on iostream stream objects. They generally modify properties and formatting settings of the streams. endl, hex and scientific are some examples of manipulators.

Organization

The library and its hierarchy of classes is split in different files:

• , , , and aren't usually included directly in most C++ programs. They describe the base classes of the hierarchy and are automatically included by other header files of the library that contain derived classes.
• declares the objects used to communicate through the standard input and output (including cin and cout).
• defines the file stream classes (like the template basic_ifstream or the class ofstream) as well as the internal buffer objects used with these (basic_filebuf). These classes are used to manipulate files using streams.
• : The classes defined in this file are used to manipulate string objects as if they were streams.
• declares some standard manipulators with parameters to be used with extraction and insertion operators to modify internal flags and formatting options.

Compatibility notes

The names, prototypes and examples included in this reference for the iostream classes mostly describe and use the char instantiations of the class templates instead of the templates themselves, even though these classes are only one of their possible instantiations. We believe this provides a better readability and is arguably as easy to obtain the names and prototypes of the basic template from the char instantiation as the opposite.

Elements of the iostream library (char instantitation)

Classes:

ios_base

Base class with type-independent members for the standard stream classes (class)

ios	Base class with type-dependent members for the standard stream classes (class)

istream

Input stream (class)

ostream

Output Stream (class)

iostream

Input/Output Stream (class)

ifstream

Input file stream class (class)

ofstream

Output file stream (class)

fstream

Input/output file stream class (class)

istringstream

Input string stream class (class)

ostringstream

Output string stream class (class)

stringstream

Input/output string stream class (class)

streambuf

Base buffer class for streams (class)

filebuf

File stream buffer (class)

stringbuf

String stream buffer (class)

Objects:

cin	Standard input stream (object)

cout	Standard output stream (object)

cerr	Standard output stream for errors (object)

clog	Standard output stream for logging (object)

Types:

fpos	Stream position class template (class template)

streamoff

Stream offset type (type)

streampos

Stream position type (type)

streamsize

Stream size type (types)

Manipulators:

boolalpha

Alphanumerical bool values (manipulator function)

dec	Use decimal base (manipulator function)

endl	Insert newline and flush (manipulator function)

ends	Insert null character (manipulator function)

fixed

Use fixed-point notation (manipulator function)

flush

Flush stream buffer (manipulator function)

hex	Use hexadecimal base (manipulator function)

internal

Adjust field by inserting characters at an internal position (manipulator function)

left	Adjust output to the left (manipulator function)

noboolalpha

No alphanumerical bool values (manipulator function)

noshowbase

Do not show numerical base prefixes (manipulator function)

noshowpoint

Do not show decimal point (manipulator function)

noshowpos

Do not show positive signs (manipulator function)

noskipws

Do not skip whitespaces (manipulator function)

nounitbuf

Do not force flushes after insertions (manipulator function)

nouppercase

Do not generate upper case letters (manipulator function)

oct	Use octal base (manipulator function)

resetiosflags

Reset format flags (manipulator function)

right

Adjust output to the right (manipulator function)

scientific

Use scientific notation (manipulator function)

setbase

Set basefield flag (manipulator function)

setfill

Set fill character (manipulator function)

setiosflags

Set format flags (manipulator function)

setprecision

Set decimal precision (manipulator function)

setw	Set field width (manipulator function)

showbase

Show numerical base prefixes (manipulator function)

showpoint

Show decimal point (manipulator function)

showpos

Show positive signs (manipulator function)

skipws

Skip whitespaces (manipulator function)

unitbuf

Flush buffer after insertions (manipulator function)

uppercase

Generate upper-case letters (manipulator function)

ws	Extract whitespaces (manipulator function)

C Library

C Language Library

The C++ library includes the same definitions as the C language library organized in the same structure of header files, with the following differences:

• Each header file has the same name as the C language version but with a "c" prefix and no extension. For example, the C++ equivalent for the C language header file is .
• Every element of the library is defined within the std namespace.

Nevertheless, for compatibility with C, the traditional header names name.h (like stdlib.h) are also provided with the same definitions within the global namespace. In the examples provided in this reference, this version is used so that the examples are fully C-compatible, although its use is deprecated in C++.

The are also certain specific changes in the C++ implementation:

• wchar_t is a fundamental type in C++ and therefore does not appear as a defined type in the corresponding header files where it appears in C. The same applies to several macros introduced by ammendment 1 to ISO C in the header file , which are keywords in C++.
• The following functions have changes in their declarations related to the constness of their parameters: strchr, strpbrk, strrchr, strstr, memchr.
• The functions atexit, exit and abort, defined in <cstdlib> have additions to their behavior in C++.
• Overloaded versions of some functions are provided with additional types as parameters and the same semantics, like float and long double versions of the functions in the cmath header file, or long versions for abs and div.

Note on versions

C++ includes the C library as described by the 1990 ISO standard and its ammendment #1 (ISO/IEC 9899:1990 and ISO/IEC 9899:1990/DAM 1). Some introductions made in the 1999 ISO standard are not compatible with the C++ standard.

Headers

cassert

C Diagnostics Library (header)

cctype

Character handling functions (header)

cerrno

C Errors (header)

cfloat

Characteristics of floating-point types (header)

climits

Sizes of integral types (header)

clocale

C localization library (header)

cmath

C numerics library (header)

csetjmp

Non local jumps (header)

csignal

C library to handle signals (header)

cstdarg

Variable arguments handling (header)

cstddef

C Standard definitions (header)

cstdio

C library to perform Input/Output operations (header)

cstdlib

C Standard General Utilities Library (header)

cstring

C Strings (header)

ctime

C Time Library (header)

Ammendment 1 to ISO-C 90 added three additional headers: ciso646, cwchar and cwctype.

C++ Language Tutorial

Basics of C++:
Structure of a program
Variables. Data Types.
Constants
Operators
Basic Input/Output
Control Structures:
Control Structures
Functions (I)
Functions (II)
Compound Data Types:
Arrays
Character Sequences
Pointers
Dynamic Memory
Data Structures
Other Data Types
Object Oriented Programming:
Classes (I)
Classes (II)
Friendship and inheritance
Polymorphism
Advanced Concepts:
Templates
Namespaces
Exceptions
Type Casting
Preprocessor directives
C++ Standard Library:
Input/Output with files