TDDD38 APiC++ Courseintroduction 1

TDDD38 Advanced Programming in C++

Aim – or, what does “advanced” stand for?

• good knowledge about constructs and mechanisms in the programming language C++ and their use

• good knowledge about the C++ standard library, both content and design principles, and how to use its components effectively

• ability to design and implement usable, correct, error-safe, non-trivial classes, including polymorphic class lattices (hierarchies)

• ability to design and implement advanced program components – template based, policy design, function objects, …

• it’s not a systems design course, or a problem solving course, or alike, but there will be problems to solve!

Prerequisite

• good knowledge and skills in programming in at least one procedural and/or object-oriented language

• knowledge about fundamentals of object-oriented programming (class, derivation/inheritance, polymorphism)

No previous experience of C++, C or Java?

• get acquainted a.s.a.p. with C++ basics

• attend lecture 2 and 3

TDDD38 APiC++ Courseintroduction 2

Organization

• basically a self-study course – good self-discipline is necessary

– study theory!

– do exercises!

– do it in time!

• lectures – the core language is covered in the first study period, standard library in the second study period

– single class design

– operator overloading

– derived classes, inheritance, polymorphism, RTTI,…

– exception handling, exception classes

– templates

– standard library – strings, streams, standard exceptions, containers, iterators, algorithms, function objects, related utilities,…

– design patterns, policy design, template meta programming, style, …

• no lessons – no compulsory labs

– optional exercises – strongly recommended!

– it is absolutely necessary to practice a lot – and enough on a Unix system (IDA’s Linux Mint system) – and using g++

• limited computer resources scheduled

– assistance by email to TDDD38@ida.liu.se (or tommy.olsson@liu.se), or by appointment

– you are also welcome to look me up in my office

TDDD38 APiC++ Courseintroduction 3

Examination

Computer exam – the only compulsory item

• four times a year – December, March/April, May/June, and August – five hours

• five theory questions – 1 points each

• four programming problems – 5 points each

– basic stuff is of course required

– class design, derivation, operator overloading, templates, exception handling

– standard library – strings, stream I/O, containers, iterator, algorithms, function objects, related utilities, etc.

– techniques and style

• marking – 25 points maximum

– 19-25 – 5/A

– 15-18 – 4/B

– 11-14 – 3/C (corresponds to correctly solving two programming problems and getting one theory question right).

– 0-10 – U/FX

• means of assistance

– cplusplus.com Reference (available in a Chromium web browser)

• important to be familiar with the exam system (Unix), some available text editor (Emacs), and the GCC compiler (g++)

– only simple file handling required

– sufficient experience in how to read, interpret and act upon compiler and linker error and warning messages

TDDD38 APiC++ Courseintroduction 4

Information, literature, etc.

• course home page: http://www.ida.liu.se/~TDDD38/

– information about examination – the three last given exams are always available

– timetable (link to LiTH timetable server)

– lecture plan and content

– lecture slides, code examples

– exercises

– C++ links

– contact information

• course literature – basically your choice – some recommendations:

C++ Primer, Fifth edition (2012). Lippman, Lajoie, Moo. (downloadable)

The C++ Programming Language, Fourth edition (2013), Stroustrup.

The C++ Standard Library, A Tutorial and Reference, 2/E (2012), Josuttis, N. M. (downloadable)

cplusplus.com (tutorial, reference, articles, etc.) – Reference part is means of assistance at exam

• Friday fun!

TDDD38 APiC++ Courseintroduction 5

Lecture plan for the forthcoming lectures

Lecture 2-3

• basic stuff – data types, variables and constants, declarations, expressions and operators, statements, functions,…

• strings, initializer lists, tuples, streams, string streams

Lecture 4–5

• single class design and operator overloading

Lecture 6–7

• derived classes, inheritance, polymorphism, RTTI

• exception handling

Lecture 8-9

• templates

• namespaces

• preprocessor

Lecture 10-12 (13)

• standard library

– containers – iterators – algorithms – function objects, lambda expression

– related utilities and such (e.g. std::pair)

– maybe some more…

And now some comments to the course content…

TDDD38 APiC++ Courseintroduction 6

C++ history and future

• one of the most popular programming languages

• development started in 1979 – originally named C with Classes

• renamed C++ in 1983

•C++98 – the first ISO standard

•C++03 – C++98 was amended by the 2003 technical corrigendum (TC)

•C++11 – current standard (formerly known as C++0x, since it was expected to be released before 2010)

– a “new” C++

– a new C++ programming style is developing

•C++14 – minor revision targeted for late 2014, but delayed

– mainly bug fixes and small improvements

– one new major feature can be expected – maybe static if (compile time if statement)

•C++1y – major revision targeted for 2017

– will not be the last…

• Each revision

– adds more power

– makes constructs more general

– increases efficiency even more

– makes C++ easier to use

TDDD38 APiC++ Courseintroduction 7

Object-oriented programming

Three main components – objects, inheritance, polymorphism

• objects

– classes are used to model objects

– in C++ we have two syntactic choices, class or struct

– only difference is related to default member and base member access – private for class – public for struct

–rule of thumb: use struct for behaviourless aggregates with public members only, class otherwise

• inheritance

– code can be reused by derivation, base class – subclass

– creates related classes/objects – a subclass object is also a base class object regarding type, an “is a” relationship

– derivation is typically a question of specialization – a subclass can have more state and more functionality

– C++ supports four ways to derive from a base class – public base, protected base, private base, and virtual base

• polymorphic behaviour

– an object reference (pointer or reference) may at different times refer to objects of different type

– the same member function call may at different times give different result, depending on the type of the related object

• polymorphic behaviour is optional in C++

– a member functions must be declared virtual to be able to behave polymorphic

– objects must be referred to by pointers or references

• dynamic type checking and dynamic type conversion, RTTI

– sometimes it’s required

TDDD38 APiC++ Courseintroduction 8

Important characteristics for class types in C++

{

string s1; // an object declaration, in some block, string is a class type

}

• classes in C++ are not reference types

–s1 stores an object of type string – it’s not a reference to such an object

–astring object is automatically created and initialized when the declaration of s1 is elaborated

– when the execution exits the declaration block, s1 goes out of scope – the object is destroyed – memory is reclaimed

• class types have the same basic semantics as fundamental types, e.g.

– require copy semantics not found in most other object-oriented languages – in C++11 move semantics is also available

string s2{s1}; // initialization string s2(s1); string s2 = s1;

s2 = s1; // assignment

• great care must be taken when designing classes in C++

– initialization – default constructor, argument passing constructors

– copying – copy constructor,copy assignment operator,move constructor,move assignment operator

– destruction – destructor

• to mimic e.g. Java we use pointers an dynamic memory allocation (memory has to be deallocated explicitly when no longer needed)

string* message{ new string{ "Hello world!"} };

…

delete message;

TDDD38 APiC++ Courseintroduction 9

Inheritance and classes derivation

• class derivation is an essential features of object-oriented design

– new classes can be defined from exciting classes

– code is reused – members are inherited

• C++ supports “all” variants

–single inheritance (single base class)

–multiple inheritance (multiple base classes), which can lead to

–repeated inheritance (DDD – the Deadly Diamond of Derivation, ♦), which is supported by

–virtual inheritance (virtual base class) – how many Base subobjects are there to be in Most_Derived?

Base

Derived_1

Most_Derived

Derived Derived_2

member

Base

member

Base_1

member

Base_2

member

Derived_1 Derived_2 ♦

TDDD38 APiC++ Courseintroduction 10

Operator overloading

ostream&operator<<(ostream& os, const T& x)

{

// write x to os

return os;

}

• important for construction of fully featured data types

– assignment

– indexing

– any other operator for which there is a natural interpretation of its use

• function objects rely on the possibility to overload the function call operator – operator()

– function objects are important components in the standard library – lambda expressions are implemented as function objects

– can act as function

– can carry state

– possible to overload for class types and for compound types (enum types, pointer types, etc.)

struct fun

{

void operator()() const { cout << "This is fun!\n"; }

};

fun()(); // not the same parentheses… fun{}()

TDDD38 APiC++ Courseintroduction 11

Templates

Extremely powerful construct in C++.

• for creating reusable program components – function templates and class templates

template <typename T> T fun(const T& a);

template <typename T, size_t N> class array;

• supports e.g. policy design

– a policy used by a type (class) can be separated into one or more policy classes, which can be supplied as a template parameter

template <typename T, class Allocator = allocator<T>> class vector;

• supports template metaprogramming

– function templates can be used to let the compiler generate source code

– recursive, purely static template functions can perform compile-time evaluation

• is an object-oriented construct – static (compile-time) polymorphism

– a function template represents a whole family of functions

– a class template represents a whole family of classes, data types are pure static (compile-time) constructs

• the standard library depend heavily on templates, in many cases in combination with derivation

– the new feature variadic templates is widely used in the implementation of the standard library

template <typename... Types> class tuple;

TDDD38 APiC++ Courseintroduction 12

Exception handling

• conceptually fairly simple, but should be used with care.

– prefer traditional, local error handling if possible

– good for reporting errors from within software components

– place error handlers with care – avoid “exception handling spaghetti”

– practice exception-safe (error-safe) programming

• C++ implements the termination model – the alternative to the resumption model

– at least one block is terminated

– exceptions are propagated backwards along the dynamic call chain

– stack objects will be destroyed implicitly and properly when blocks are exited

– heap objects must be taken responsibility for by the programmer (smart pointers is one possibility)

try

{

...

if (disaster) throw some_exception{"help!"}; // supposed subclass to std::exception

...

}

catch (const exception& e) // “polymorphic catch”

{

cout << e.what() << endl;

}

TDDD38 APiC++ Courseintroduction 13

Namespaces

A simple module construct.

• the class has module properties, but it’s not enough

– was one of the last things introduced before the first standard C++98 was published

• important in several aspects

– for handling potential name collisions

– modularisation – a type and it’s operations, e.g., should be encapsulated in the same namespace

– function name look up – ADL look up (argument-dependent look up) – is related to namespaces

namespace std

{

// namespace member declarations…

}

using namespace std; // using directive

using std::member; // using declaration

... std::member ... // qualified name

TDDD38 APiC++ Courseintroduction 14

Standard Library

Data structure and algorithm part

• String

• Streams

• String streams

• Related utilities

• Interesting implementation, e.g.

– templates

– derivation

– policy design

Containers Algorithms

Function

objects

Iterators

Streams

TDDD38 APiC++ Courseintroduction 15

And, of course, a lot of basic stuff to be mastered

The “C part”.

• Lexical conventions

• Translation model – compilation and linking

• Data types and type conversion

• Declarations and definitions

• Expression and operators

• Statements

• Functions and parameter passing

• Basic standard library components

• I/O and file handling

Topics for lecture 2 and 3.

TDDD38 APiC++ Basic C++ 1

Basic C++

• compilation model

• keywords and identifiers with special meaning

• objects, declarations, and initialization

• data types and type conversion

• pointers

• references

• pointers and dynamic memory handling

• aggregates and list initialization

• declarations and definitions

• expressions and operators

• statements

• functions and parameter passing

• strings

• tuples

• streams

• string streams

Note 1: A lot of concepts and terminology to follow…

Note 2: Much of the stuff related to streams is mainly for self study (page 33 ff.)

TDDD38 APiC++ Basic C++ 2

The classic first C++ program

* hello.cc

#include <iostream>

using namespace std;

int main()

{

cout << "Hello, world" << endl;

return 0; // this return statement is optional

}

• multi-line and single-line comments

• include directive – import stuff from the environment, in this case from the standard input/output library (streams)

• using directive – opens the standard namespace std – without require qualified names

std::cout << "Hello, world" << std::endl;

• function main() is found in all (normal) C++ programs – this is where the execution starts and normally ends

– function prototype

– function body

• statements

TDDD38 APiC++ Basic C++ 3

Compilation model (1)

source code → preprocessor → compiler → linker → executable

• source code

– include files (*.h) – declarations and definitions required by client code – “module specification”

– also standard headers, e.g. <iostream>

– implementation files (*.cc, *.cpp, …) – e.g. separate definitions for declarations in a corresponding header file

• preprocessor

– works before the actual compilation takes place

– file inclusion, macro substitution, conditional compilation, …

– avoid when possible

• compiler

– takes the preprocessor output as input

– produces, in cooperation with linker, an executable (a.out, e.g.)

– separate compilation to object code, if requested (*.o files) – stops before linking phase

• options can modify the translation process in many ways – preprocessing, compilation, linking – GCC/Linux examples:

g++ hello.cc

g++ -g -std=c++11 -Wpedantic -Wall -Wextra hello.cc

gccfilter g++ ...

TDDD38 APiC++ Basic C++ 4

Compilation model (2)

A slightly simplified picture:

g++ -c program.cc

g++ -I/home/tao/include -o program program.cc -lcurses

*.cc cpp compiler linker a.out

object code

pure

C++

iostream

*.h

*.o

*.so.*

*.a

include files (headers) link libraries

-c

-Idir -Ldir -llib

-o filename

TDDD38 APiC++ Basic C++ 5

Keywords and identifiers with special meaning

alignas continue friend register true

alignof decltype goto reinterpret_cast try

asm default if return typedef

auto delete inline short typeid

bool do int signed typename

break double long sizeof union

case dynamic_cast mutable static unsigned

catch else namespace static_assert using

char enum new static_cast virtual

char16_t explicit noexcept struct void

char32_t export nullptr switch volatile

class extern operator template wchar_t

const false private this while

const_cast float protected thread_local

constexpr for public throw

•export is removed but kept for the future use (related to compiling templates)

•register is deprecated (don’t use)

•final and override – identifiers (not keywords) with special meaning in specific contexts (classes, member functions)

TDDD38 APiC++ Basic C++ 6

Data types and type conversion

The type system design have great influence on safety, efficiency, etc.

• C++ is a strongly, statically typed language

– each object and expression has a distinct type

– in polymorphic contexts we have a distinction between static type and dynamic type

–standard type conversions relaxes strong typing

• two main type categories

– fundamental types

– compound types

• type conversions

– implicit (automatic)

– explicit (coded)

– three different syntaxes…

static_cast<T>(x) // type conversion operators – prefer these! (checked)

T(x) // functional form (unchecked!)

(T)x // C cast (unchecked!)

TDDD38 APiC++ Basic C++ 7

Fundamental types

integral types

integer types

unsigned integer typessigned integer types

char32_t

char

signed char

short int

int

long int

unsigned char

unsigned short int

unsigned int

unsigned long int

arithmetic types

floating point types

float

double

long double

void

fundamental types

bool

long long int unsigned long long int

wchar_t

char16_t

= “keeping it simple”

TDDD38 APiC++ Basic C++ 8

Compound types (1)

Compound types can be constructed in many ways – some common compound types:

•arrays are indexed data types made up of elements of the same type (prefer std::array or std::vector)

int a[100];

•pointers to objects or functions of a certain type, or to void (“anything”)

int* p{ a }; // same as int* p = a; or int* p = &a[0];

•references to objects or functions of a certain type

int& r{ a[0] }; // lvalue reference

void fun(string&& s); // rvalue reference – binds e.g. temporary objects

•class types (class,struct or union) made up of named components of possibly different type, including member functions

struct Person

{

string name;

unsigned age;

float length;

};

Note: arrays and simple class types are aggregates.

TDDD38 APiC++ Basic C++ 9

Compound types (2)

•functions have parameters of different types and return either void (nothing) or some type

int max(int x, int y); // Type: int(int,int)or int (*)(int,int)

•enumeration types

enum Alert { Red, Orange, Yellow, Blue, Green };

– the values are called enumerators

– an enumerator can be implicitly converted to and compared with int – they are effectively integers

• scoped enumeration types

enum class Colour : unsigned int { Red, Orange, Yellow, Green, Blue, Indigo, Violet };

Colour c{ Colour::Red };

c = Colour::Blue;

int i{ Colour::Red }; // error – no implicit conversion for scoped enumerations

–enum class or enum struct – semantically equivalent

– there is no implicit conversion to int or bool

– the enumerators of a scoped enumeration have enumeration scope

– the same enumerator can occur in several enumerations

– the underlying type can be can be specified – must be an integral type

TDDD38 APiC++ Basic C++ 10

Type definition

•analias declaration is used to declare a simple name for a “complicated” type

using Func = int (*)(int,int);

Func f{ max }; // max was declared on the previous slide

•typedef also (this was earlier the only possibility – regarded as less readable)

struct List_Node

{

string data;

List_Node* next;

};

typedef List_Node* List; // using List = List_Node*;

void insert(Type x, List& list); // List_Node*& list

List head{ nullptr }; // List_Node* head

•Func and List are not distinct types – only synonyms for the actual type

• an alias declaration can contain attribute specifiers – a typedef declaration can not

TDDD38 APiC++ Basic C++ 11

CV-qualification

A type like int is a cv-unqualified type:

int x;

All cv-unqualified types have three corresponding cv-qualified versions.

•const-qualified – such an object is a const object

const int MAX{ 1000 }; constexpr const int MAX{ 1000 }; constexpr int MAX{ 1000 };

– const objects must be initialized

•volatile-qualified – such an object is a volatile object

volatile int bird;

–volatile is a hint to the implementation to avoid optimization involving the object

– its value might be changed by means undetectable by the implementation

•const-volatile-qualified – such an object is a const volatile object

volatile const int x;

–const means that the code cannot change the value of the object

– does not mean that the value of the object cannot be changed by means outside the code – volatile

• cv-qualification distinguishes in function overloading – can be ignored in some contexts

TDDD38 APiC++ Basic C++ 12

Pointers

A pointer is an object storing an address (pointer) to another object.

{

T x; // variable of type T

T* p{ nullptr }; // pointer to T, initialized with a null pointer value

p = &x; // p is assigned the address of x, using the address operator &

cout << p; // the address stored in p is printed

cout << *p; // p is dereferenced with the dereferencing operator *, the value of x is printed

p = new T; // allocate a dynamic object of type T with the new operator and store a pointer to it in p

…

delete p; // deallocate the object p is pointing at

…

} // x and p goes out of scope

• objects created with operator new are allocated on the heap

•pmust not outlive x – possible if p was declared in an outer scope

• it is very important to deallocate dynamic objects properly – operator delete – memory leaks must be avoided

• smart pointers are available in the standard library – unique_ptr, shared_ptr, weak_ptr

TDDD38 APiC++ Basic C++ 13

References

{

T x; // variable of type T

T& r{ x }; // (lvalue) reference to T

cout << r; // r is implicitly dereferenced – the value of x is printed

}

• a reference can be thought of as a name of an object

– in the example above r is another name for x, an alias

– must always be initialized – there is no “null reference”

– references are quite different from pointers semantically and there need not be any value stored for a reference

• in C++11 there are two kind of references – lvalue references and rvalue references

– have much in common regarding semantics

– one of the main uses of references is as function parameters and return types – the most anticipated function overloadings are

void fun(const T& x); // matches any kind of argument (as do also plain T)

void fun(T&& x); // but this will be a better match for rvalues, e.g. temporary objects

– closely related to temporary objects, but not exclusively, and move semantics

– typical use is in move constructors and move assignment operators – does not leave the source unchanged

“Every time I think I have grasped rvalue references, they evade me again.”

TDDD38 APiC++ Basic C++ 14

Pointers and dynamic memory handling

• Dynamic memory is allocated on a global heap – pointers are used to handle such objects

• No garbage collection can be expected

– deallocating dynamic memory when no longer needed is very important – smart pointers can be a good choise

• Memory allocation and deallocation operators are available in several versions.

–ordinary versions for allocating/deallocating either an object of none-array type or an object of array type:

X* p{ new X }; delete p;

X* p{ new X[100] }; delete[] p;

–nothrow versions – a null pointer is returned when allocation fails, instead of exception bad_alloc thrown; non-array version:

X* p{ new(std::nothrow) X }; // nullptr is returned on failure

if (p != nullptr) …

–placement versions are used to construct objects in some already available memory, not necessarily heap memory; array version:

alignas(X) char place[10 * sizeof(X)]; // non-heap memory, can store 10 objects of type X

X* p{ new(place) X[10] }; // create 10 default initialized X objects in place

for (int i = 0; i < 10; ++i) p[i].~X(); // explicit destructor calls

Note: no special call syntax for nothrow and placement versions of delete.

TDDD38 APiC++ Basic C++ 15

Aggregates and initializer lists (1)

An aggregate is either

•anarray

int data[10];

• or a class with

– no user-provided constructors

– no private or protected non-static data members

– no base classes

– no virtual functions

– no brace-or-equal-initializers for non-static data members (removed in C++14)

Basically something very simple like

struct Person

{

string name;

unsigned age;

float length;

};

union int_or_double { int i; double d; };

TDDD38 APiC++ Basic C++ 16

Aggregates and initializer lists (2)

• aggregates can be initialized by an initializer list (braced-init-list) – list initialization:

int a[10]{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

Person p{ "Foo", 21, 1.82 };

int_or_double iod{ 17 };

Person* ptr = new Person{ "Foo", 21, 1.82 }; // in a new expression

• there may be fewer elements in the initializer list than members or elements in the aggregate

int a[10]{}; // empty list, all 10 elements are initialized to 0

Person p{ "Foo" }; // same as { "Foo", 0, 0.0 }

•class aggregates can also be assigned an initializer list

p = { "Fie", 17, 1.67 };

(More about aggregates and list initialization in one of the exercises).

TDDD38 APiC++ Basic C++ 17

Implicit type conversion

•implicit type conversion (in a general meaning) can be of two kinds

–conversions are potentially unsafe – e.g. from int to short int

–promotions are safe – e.g. from int to long int

• the standard defines a number of standard type conversions

– lvalue-to-rvalue conversion (1)

– array-to-pointer conversion (1)

– function-to-pointer conversion (1)

– integral promotions (2)

– floating point promotion (2)

– integral conversions (2)

– floating point conversions (2)

– floating-integral conversions (2)

– pointer conversions (2)

– pointer to member conversions (2)

– boolean conversions (2)

– qualification conversions (3)

•astandard conversion sequence is a sequence of up to three standard conversions

– zero or one from set (1), zero or one from set (2) or a user defined conversion, and zero or one from set (3)

TDDD38 APiC++ Basic C++ 18

Explicit type conversion

Explicit type conversions can be expressed using

•cast notation (comes from C) – unchecked – avoid!

x = (int)d; // suppose x is int, d is double

•functional notation (early C++) – unchecked – avoid!

x = int(d);

•type conversion operators – checked

static_cast<int>(d) between related types (e.g. different arithmetic types)

reinterpret_cast<int>(p) between types not related (e.g. integer and pointer)

dynamic_cast<Derived*>(bp) within a polymorphic class hierarchy (e.g. from base class pointer to subclass pointer)

const_cast<int>(c) removes const

The expression T() creates a (value-initialized) value of type T – especially useful if T is a template type parameter

auto x = int(); // x obtains type int, and is initialized to 0 (zero-initialized, one kind of value-initialization)

auto x{ int() }; // x may not obtain the type you expect…(to be fixed in future C++)

TDDD38 APiC++ Basic C++ 19

Declarations and definitions (1)

Declarations generally specify how names are to be interpreted.

•adeclaration may introduce a name into a translation unit, or re-declare a name introduced by a previous declaration

• a declaration is a definition if it basically results in some code

int a; // defines a

extern int a; // declares a

extern int a{0}; // defines a

int square(int x) { return x*x; } // defines square

int square(int x); // declares square

struct point { int x; int y; }; // defines point

struct point; // declares point

enum { UP, DOWN }; // defines UP and DOWN

namespace N { int m; } // defines N and N::m

using N::m; // declares m

• ODR – one definition rule

– no translation unit shall contain more than one definition of any variable, function, class type, enumeration type, or template

TDDD38 APiC++ Basic C++ 20

Declarations and definitions (2)

Declarative regions and scope rules are not trivial.

• C++ is basically a block structured language, with related scope rules

– block scope (local scope)

– namespace scope

– class scope

– function prototype scope (function parameters)

– function scope (labels)

– template parameter scope

– enumeration scope (scoped enumerators)

• raises questions about name look up, name hiding, accessibility, ambiguities, etc.

– not always obvious or simple

TDDD38 APiC++ Basic C++ 21

Storage duration and object lifetime

Storage duration is the property of an object that defines the minimum potential lifetime of the storage containing the object.

• the storage duration is determined by the construct used to create the object and is one of the following:

–static storage duration (global objects)

–automatic storage duration (local variables and parameters – the old meaning of the, until C++11, never used keyword auto)

–dynamic storage duration (programmer controlled – new,delete)

–thread local storage (every thread can have its own storage, or share)

• the lifetime of an object

–begins when storage is obtained and the object is fully initialized

–ends when the object’s destructor call starts, if the object is a class type, and the storage is reused or released

•temporary objects are created in several contexts

– binding a reference to a value (prvalue)

– returning a value from a function (prvalue)

– a type conversion that creates a value (prvalue)

– throwing an exception

– entering a exception handler

– some initializations

–rvalue reference is a kind of reference which can bind to temporary objects, and other rvalues

TDDD38 APiC++ Basic C++ 22

Expressions and operators (1)

There are may operators in C++ and extensive possibilities to compose expressions.

• the common set of operators, such as additive, multiplicative, relational, logical, etc., but also, e.g.:

– subscripting: []

– function call: ()

– class member access: .and ->

– pointer-to-member operators: .* and ->*

– eleven assignment operators: =,+=,-=,*=,/=, …

– conditional operator: ?:

– comma operator: ,

• many precedence (priority) levels

– some with left associativity, some with right associativity

– gives basically natural semantics

– parentheses can be used for specifying a required evaluation order, or for clarity

• most operators are overloadable for compound types (class types, enumeration types, pointer types, …)

TDDD38 APiC++ Basic C++ 23

Expressions and operators (2)

• an expression is a sequence of operators and operands that specifies a computation

a * b - 1

• an expression can result in a value and can cause side effects

++x x++ x = y = z = 0;

– ++ and = have side effect, but, it is usually the main purpose, to modify the value of the operand

– the resulting value of the prefix ++ expression is the value x obtain after incrementation

– the resulting value of the postfix ++ expression is the value x had before incrementation (may carry a cost)

• operators have precedence and associativity

a * b - 1 is evaluated (a * b) - 1 * have precedence over -

a + b - 1 is evaluated (a + b) - 1 + and - have same precedence, are left associative

x = y = 0 is evaluated x = (y = 0) = is right associative

• in most cases the evaluation order of operands is not specified – exceptions are &&,||,?: and , (comma operator)

if (p != nullptr && p->value == 0) …

int min{x < y ? x : y};

TDDD38 APiC++ Basic C++ 24

Expressions and operators (3)

Categorization of expressions.

x = y + 1 + fun();

•lvalue – “can be assigned to” – can be on the left hand side of an assignment

– designates an object or a function

–glvalue – general lvalue – lvalue or an xvalue – “something that can be changed”

•rvalue – “can be copied” –something that can be on the right hand side of an assignment

– an rvalue is an xvalue, a temporary object, or a value that is not associated with an object

–prvalue – pure rvalue – an rvalue that is not an xvalue – function return value, literal

•xvalue – eXpiring value – object usually near the end of its lifetime

– can be pilfered – its resources can moved

– functions returning rvalue-reference (&&) typically involved

• every expression belongs to exactly one of the fundamental classifications lvalue,xvalue, or prvalue – its value category

The name rule: if something has a name, it’s an lvalue, if not, it’s an rvalue

– an lvalue is something you can take the address of (with the address operator &)

•value is a bit misleading, these are not really values (expression categories)

expression

glvalue rvalue

lvalue xvalue prvalue

T& T&& T

const T&

TDDD38 APiC++ Basic C++ 25

Statements (1)

Mainly traditional, but some are rather “low level” constructs.

•declaration statements – int i;

•empty statement – ;

•expression statements – expression;

•compound statement, or block, to encapsulate a sequence of statements –{ … }

•labelled statement – label :statement (label is an identifier,case or default)

•selection statements

–if – with or without else

–switch – to a case label or default (labelled statements)

•iteration statements

–while – logical pretest

–do – logical posttest

–for – basically logical pretest, but can also model count pretest

–range-based for – a simple-to-use for statement to iterate over, e.g., an array or a container (C++11)

•jump statements

–break – out of a switch or an iteration

–continue – with the next step in an iteration

–return – from a function

–goto – a labelled statement

TDDD38 APiC++ Basic C++ 26

Statements (2)

The switch statement, case labelled statement, and break statement.

int main()

{

char c;

cout << "Say y = Yes, or n = No: ";

cin >> c;

switch (c)

{

case ’y’: // if selected, fall-through to next case statement

case ’Y’:

cout << "You said Yes";

break;//break fall-through, jump out of switch

case ’n’: // if selected, fall-through to next case statement

case ’N’:

cout << "You said No";

break;//break fall-through, jump out of switch

default://select if no case matched

cout << "Wrong choise!";

break;//optional, the switch statement is anyway exited soon

}

return 0;

}

TDDD38 APiC++ Basic C++ 27

Statements (3)

Iteration statements.

while (cin >> x)

{

if (x > MAX) break;

if (x == 0) continue;

// …

}

{

cout << "Give me five! ";

cin >> x;

// …

}

while (x != 5);

for (int i = 0; i < MAX; ++i)

{

if (i % 2 == 0) continue;

// …

}

for (auto it = begin(v); it != end(v); ++it)

cout << *it << ’\n’;

TDDD38 APiC++ Basic C++ 28

Statements (4)

The range-based for statement.

int a[5]{ 1, 2, 3, 4, 5 };

for (int& x : a)

x *= 2;

vector<Person> v{ 1, 2, 3, 4, 5 };

for (const auto& p : v) // const Person&

cout << p << ’\n’;

The beginning and end of the range is determined as follows:

• if an array a with dimension N

–a

– a + N

• if an object c of class type – begin() and end() return iterators

– c.begin()

– c.end()

•otherwise, for an object x – begin() and end() return iterators

– begin(x)

– end(x)

TDDD38 APiC++ Basic C++ 29

Functions and parameter passing (1)

• Functions can be overloaded

– differences in parameter lists distinguish

– return type does not participate in overload resolution

• Member functions (classes) can be overridden if virtual

– identical parameter list

– usually same return type (covariant types allowed)

• Function parameters can have default arguments

– used when no corresponding argument is given in a call

void increment(int& value, int amount = 1);

• Syntactically we have two parameter passing mechanisms

–call by value

void fun(string s);

–call by reference

void fun(string& s);

– but five “semantic” parameter passing techniques (next slide)

TDDD38 APiC++ Basic C++ 30

Functions and parameter passing (2)

Semantic parameter passing modes:

•byvalue – for in parameters of simple type (possibly const, no big deal which)

void fun(string s);

void fun(const string);

•bylvalue reference – for in/out or out parameters

void fun(string& s);

•bylvalue reference to constant – for in parameters of “complicated” type

void fun(const string& s);

•byrvalue reference – typically for catching temporaries and applying move semantics on the argument

void fun(string&& s);

•bypointer – for pointers argument, of course, but also allows for “no value present” (if nullptr argument)

void fun(string* p);

void fun(const string* p); // there are more combinations for const…

void fun(string*& p);

• function parameters are always lvalues (something that have a memory address) according to the name rule

TDDD38 APiC++ Basic C++ 31

Strings

Two possibilities to handle strings:

• null terminated character sequences, “C strings” – well known trouble maker…

char s1[72]{}; // dimension 72, all elements initialized to \0

char s2[]{ "C string" }; // dimension deduced to 9, initialized to C string\0

const char* p{ "C++" }; // character pointer, must be const here

– standard library utilities for handling such strings are found in, e.g., <cstring>, <cctype>, and <cstdlib>

strcpy(s1, s2); // equivalent to assigning (s1 = s2)

• strings are in most cases much better handled using std::string

#include <string>

string s1; // default initialized, empty string

string s2{ "C++ string" }; // initial size is 10

const string cs{ "C++" }; // constant string

– a large set of operations are supplied by member functions and other functions

– well-behaved concerning initialization, copying, comparing, etc.

– the implementation is actually a template, basic_string – string is an instance for char

– designed as a container type for storing characters, with iterators and all

TDDD38 APiC++ Basic C++ 32

Tuples

Can be instantiated with any number of arguments.

tuple<int, string, double> fragrance{ 4711, "Eau de Cologne", 39.39 };

int number;

string name;

double price;

tie(number, name, price) = fragrance;

get<2>(fragrance) = 49.95;

auto t = tuple_cat(fragrance, tuple{"SEK"}); // tuple<int, string, double, string>

tuple<int,int,int> fun(); // function returning three int

int a, b, c;

tie(a, b, c) = fun();

tie(a, ignore, ignore) = fun(); // we are only interested in the first value

tie(a, b, c) = make_tuple(b, c, a); // rotate (a, b, c) -> (b, c, a)

Not as flexible as one may expect, or wish, but still useful.

TDDD38 APiC++ Basic C++ 33

Streams

The stream library is for reading and writing streams

• a stream is a sequences of elements of a certain type, typically characters

• stream types

– in streams – istream, ifstream

– out streams – ostream, ofstream

– in- and out streams – iostream, fstream

– string-based streams – istringstream, ostringstream, stringstream

• operations provided to

– open and close streams

– read and write streams – text or binary

– check the state of a stream – e.g. end-of-stream, error conditions

– manipulate character streams – e.g. to modify input- or output format

TDDD38 APiC++ Basic C++ 34

Stream classes hierarchy

Very simplified:

Object-oriented constructs and several other advanced features are used:

• all classes except ios_base are templates (the classes above are actually instances for char; add basic_ for the primaries)

– parameterized on character type and a character traits class providing character and string manipulation utilities

•single inheritance – all except iostream

•multiple inheritance – iostream

•repeated inheritance – ios to iostream – DDD, the “Deadly Diamond of Derivation”

–virtual inheritance – there are things in ios that must not be inherited into iostream in multiple instances

•polymorphic classes (all)

ios_base

ios

istream ostream

iostream

ifstream istringstream fstream stringstream ofstream ostringstream

<ios>

TDDD38 APiC++ Basic C++ 35

Using the streams library

#include <iostream>

– the stream classes istream,ostream och iostream

– the standard streams cin,cout,cerr and clog

– manipulators without parameters, e.g. endl,noskipws,oct

#include <iomanip>

– parameterized manipulators, e.g. setw(10),setprecision(2)

#include <iosfwd>

– instead of <iostream> if only type definitions from <iostream> required

– you can, e.g., declare function parameters (ostream&,istream&) but not use cin and cout

#include <fstream>

– the stream classes ifstream,ofstream and fstream

– support for handling files as streams

–<fstream> include <iostream>

#include <sstream>

– the string stream classes istringstream, ostringstream and stringstream

TDDD38 APiC++ Basic C++ 36

Formatted I/O

For character streams, character file streams and string streams.

• the standard library provide overloadings for operator<< and operator>> for fundamental types and string types

•operator<< perform formatted output

cout << x

– the internal representation for the value of x is transformed to the corresponding text representation before printed

•operator>> perform formatted input

cin >> x

– leading whitespace is ignored (can be manipulated)

– characters are read as long as they together can represent a value for x

– reading stops if the next character is whitespace, end of stream, or cannot belong to a text representation for a value for x

– the read text is transformed to internal representation and stored in x

– if reading fail – the stream did not contain anything that could be interpreted as an x value – failbit is set

– if something disastrous occurred badbit is set

TDDD38 APiC++ Basic C++ 37

Reading and writing standard streams

#include <iostream>

using namespace std;

int main()

{

int x;

while (cin >> x)

{

cout << x << ’\n’;

}

return 0;

}

The program can read input from a text file, and write output to a text file by redirection on the command line.

a.out < input.txt // cin is redirected to input.txt

a.out > output.txt // cout is redirected to output.txt

a.out < input.txt > output.txt

TDDD38 APiC++ Basic C++ 38

Member functions for handling stream state

A stream have three state bits (flags):

•failbit – indicates that an input operation failed to read expected characters, or an output operation failed to generate desired characters

•badbit – indicates an irrecoverable error

•eofbit – indicates that an input operation reached the end of an input sequence

Member functions for handling state:

Note: using eof() to construct input loops if often a bad choice.

cin.clear(); resets all state bits for cin – possible if failbit but not if badbit

if (cin.good()) … returns true if none of the state bits are set for cin

if (cin.fail() ) … returns true if failbit or badbit is set for cin

if (cin.bad()) … returns true if badbit is set for cin

if (cin.eof()) … returns true if eofbit is set for cin

if (!cin) … returns fail(); operator!

if (cin) … returns ! fail(); type converting member operator function, operator bool()

TDDD38 APiC++ Basic C++ 39

Making stream state changes throw exception

An alternative to check state of a stream explicitly is to let stream operations throw exceptions.

• member function exceptions() is used to specify for which cases exceptions shall be thrown

input.exceptions(ios::failbit | ios::badbit); // throw if failbit or badbit is set

try

{

while (input >> x) // if read fails or stream turns bad here

{

cout << x << ’\n’;

}

catch (const ios::failure& e) // we will be thrown to here

{

if (input.bad())

{

// irreparable...

}

else if (input.fail())

{

input.clear(); // reset state to “good”

...

}

TDDD38 APiC++ Basic C++ 40

Stream manipulators for input

char word[32];

cin >> setw(32) >> word;

cin.width(32); // alternative, member function

Note: Manipulators having parameters, as setw, require inclusion of <iomanip>.

cin >> ws read whitespace until the next nonwhite character

cin >> skipws skip leading whitespace before reading a value (default)

cin >> noskipws don’t skip leading whitespace

cin >> dec integer input shall be interpreted as decimal numbers (digits are 0-9)

cin >> oct integer input shall be interpreted as octal numbers (digits are 0-7)

cin >> hex integer input shall be interpreted as hexadecimal numbers (digits are 0-9, A-F)

cin >> boolalpha bool input shall be given as false or true

cin >> noboolalpha bool input shall be given as 0 or 1 (default)

cin >> setw(32) at most 32 character can be read into the destination (typically an array)

TDDD38 APiC++ Basic C++ 41

Member functions for unformatted input

c = cin.get() extract and return one character, converted to int, from cin

while (cin.get(c)) … extract one character from cin, store in c; the return value is the stream

cin.getline(s, 256) extract (maximum) 255 characters into character array s and append a ’\0’; extraction also

stops if a ’\n’ or end-of-ﬁle is reached; if ’\n’ is found it is extracted and discarded

cin.getline(s, 256, ’;’) as above but with ’;’ instead of ’\n’ as delimiter character

cin.get(s, 256) as the corresponding getline above, but if ’\n’ is found it is not extracted

cin.get(s, 256, ’;’) as the corresponding getline above, if ’;’ s found it is not extracted

if (cin.peek() == ’\n’) read and return the next character without extracting it

cin.putback(c); c becomes the next character to extract

cin.unget(); make the last character that was read available again as the next to read

cin.read(x, sizeof(int)); reads sizeof(int) characters into x (binary mode)

n = cin.readsome(s, 30) as read but stops if the buffer runs out of characters, eve in not end-of-ﬁle

cin.ignore(100, ’;’) extracts 100 character from the input sequence and discards them; the extraction ends

when 100 characters have been extracted or when a ’;’ is found, which is also extracted

n = cin.gcount() returns the number of characters extracted by the last unformatted input operation

getline(cin, s) as getline above but for std::string

getline(cin, s, ’;’) as getline above but for std::string

TDDD38 APiC++ Basic C++ 42

Formatted output flags

left output is padded to the ﬁeld width appending ﬁll characters at the end

right output is padded to the ﬁeld width appending ﬁll characters at the beginning

internal output is padded to the ﬁeld width by inserting ﬁll characters at a speciﬁed internal point

dec / oct / hex read/write integral values using decimal/octal/hexadecimal base format

fixed write ﬂoating point values in ﬁxed-point notation (x.d)

scientific write ﬂoating-point values in scientiﬁc notation (x.dEn)

uppercase uppercase letters are used instead of lowercase for representations involving stream-generated letters, like

some hexadecimal representations and numerical base preﬁxes

boolalpha bool values are inserted/extracted as false and true instead of 0 and 1

showbase numerical values are preﬁxed with their C++ base format preﬁx, i.e. 0x for hexadecimal values, 0 for octal

values and no preﬁx for decimal values

showpoint the decimal point is always written for ﬂoating point values, even for whole numbers

showpos a plus sign (+) precedes every non-negative numerical value, including zeros

unitbuf the buffer is ﬂushed after each insertion operation

width determines the minimum number of characters to be written in some output representations, padded with ﬁll

characters if required

fill the character used to ﬁll spaces when padding results to the ﬁeld width

precision for the default ﬂoating-point notation the precision speciﬁes the maximum number of signiﬁcant digits to

display before and after the decimal point; in both the ﬁxed and scientiﬁc notations, the precision speciﬁes

how many digits to display after the decimal point

TDDD38 APiC++ Basic C++ 43

Manipulators for managing format flags

cout << left sets left, unsets right and internal

cout << right sets right, unsets left and internal

cout << internal sets internal, unsets left and right

cout << dec sets dec, unsets oct and hex

cout << oct sets oct, unsets dec and hex

cout << hex sets hex, unsets dec and oct

cout << fixed sets ﬁxed, unsets scientiﬁc

cout << scientific sets scientiﬁc, unsets ﬁxed

cout << uppercase sets uppercase

cout << nouppercase unsets uppercase

cout << boolalpha sets boolalpha

cout << noboolalpha unsets boolalpha

cout << showbase sets showbase

cout << noshowbase unsets showbase

cout << showpoint sets showpoint

cout << noshowpoint unsets showbase

cout << showpos sets showpos

cout << noshowpos unsets showbase

TDDD38 APiC++ Basic C++ 44

Manipulators for formatted output

Member functions are available for some of these:

cout.setw(32);

char old_fill{cout.fill(’#’)};

cout.precision(3);

cout << setw(32) << word sets the number of characters to be used as ﬁeld width for the next output operation to 32

cout << setfill(’#’) sets the ﬁll character to ’#’

cout << setprecision(3) sets the decimal precision to be used by output operations to 3; in ﬁxed and scientiﬁc

notations the precision speciﬁes how many digits to display after the decimal point; in the

default ﬂoating-point notation the precision speciﬁes the maximum number of signiﬁcant

digits

cout << setbase(8) sets the numerical radix to be used to 8; should be 8, 10, or 16

cout << flush unwritten characters in the buffer are written to output (“ﬂushed”), as soon as possible

cout << endl inserts a new-line character (’\n’); ﬂush the buffer, if a buffered stream

ss << ends inserts a null character (’\0’)

TDDD38 APiC++ Basic C++ 45

Member functions for unformatted output

vector<double> v;

// Populate v with doubles

// Save the doubles in v, on file in the internal binary representation

ofstream output{ "result.bin", ios::binary };

for (auto i : v)

{

output.write(reinterpret_cast<const char*>(&i), sizeof(double));

}

output.close();

ifstream input{ "result.bin", ios::binary };

double x;

while (input.read(reinterpret_cast<char*>(&x), sizeof(double)))

{

cout << x << ’\n’;

}

cout.put(c) writes the character c to the cout

cout.write(s, n) writes the block of data pointed by s, with a size of n characters, to cout

cout.flush() unwritten characters in the output buffer are written to cout as soon as possible

TDDD38 APiC++ Basic C++ 46

File streams

int main(int argc, char* argv[])

{

if (argc != 2) { // command line: program name file name

cout << "Usage: " << argv[0] << ": file\n";

return 1;

}

ifstream input{ argv[1] }; // use an input file stream to read the file

if (!input) { // file opened successfully?

cout << "Could not open file: " << argv[1] << ’\n’;

return 2;

}

int x;

while (input >> x) {

cout << x << ’\n’;

}

if (!input.eof()) { // end of file should be reached

cout << "Something when wrong...\n";

return 3;

}

...

TDDD38 APiC++ Basic C++ 47

File mode flags

Combining file mode flags:

fstream f;

f.open(name, ios::in | ios::out | ios::binary);

f.close();

in the ﬁle shall be readable and exist

out the ﬁle shall be writeable; if it does not exist create a new ﬁle, otherwise it shall be overwritten

app the ﬁle must be writeable; if it does not exist, create a new ﬁle, otherwise append new data at the end

trunc if the ﬁle exists, it shall be overwritten

ate move to the end of the ﬁle after opening

binary treat ﬁle as a binary ﬁle

in | out the ﬁle shall be both readable and writeable; it shall exist

in | out | trunc the ﬁle shall be both readable and writeable; if it does not exist, it is created; if it does exist, it shall be

overwritten

in | out | app the ﬁle shall be both readable and writeable; if it does not exist, it is created; if it does exist, all updates

shall occur at the end

out | trunc the ﬁle shall be writeable; if it does not exist, it is created, if it does exist it shall be overwritten

TDDD38 APiC++ Basic C++ 48

String streams (1)

A string is a sequence of characters – stream operations could be useful also to operate on strings.

• “serialization” – e.g. creating a text representation for a class object with data members of different types

string serialize()

{

ostringstream os;

os << ... << ... << ... ;

return os.str();

}

• reading one of two types – e.g. read integers from a stream until “STOP” occurs

vector<int> v;

string next;

int x;

while (cin >> next)

{

if (next == "STOP") break;

istringstream is{ next };

is >> x;

v.push_back(x);

}

TDDD38 APiC++ Basic C++ 49

String streams (2)

• localizing errors in input – can be easier to read one line at a time into a variable and then process that line

string line;

int x, y;

getline(cin, line);

istringstream is{ line };

is >> x;

if (is)

{

is >> y;

if (is)

cout << "x = " << x << ", y = " << y << endl;

else

cout << "Wrong input: " << is.str() << endl;

}

else

{

cout << "Wrong input: " << is.str() << endl;

}

TDDD38 APiC++ Single class design 50

Classes

A class is a type – two syntactic choices:

•struct – typically for objects with public members only (“behaviourless aggregates”)

•class – otherwise

•class type is a common notation in C++ for class,struct, and union types

The class has module properties.

• encapsulates its members

• access to members can be controlled by access specifiers and friend declarations

–public – access by anyone – default for struct

–private – access by the class’ member functions only – default for class

–protected – access by subclasses – “public” for subclasses, “private” for others

–friend – can be a global function; a specific member function of another class, or a class (i.e. all member functions of that class)

– a friend declaration is not transitive, i.e. friendship is not inherited

– beware – friendship creates a stronger coupling than derivation

Special rules describe the scope of names declared in classes – class scope

• not only the declarative region made up of the class definition itself, but also, e.g. separately defined member function bodies

Class objects in C++ can be either statically declared objects, or allocated dynamically and referred by pointers.

• makes the C++ object model quite different from many other object-oriented languages

TDDD38 APiC++ Single class design 51

Class members

Class members can be of four kinds:

• data members

• member functions

•nested types – e.g. a nested class, a nested alias declaration (using), or a nested typedef

•enumerators – acts as static, constant data members – enum { Up, Down, Left, Right };

A data member or member function can be

•non-static – “instance member” – each object have its own copy

•static – “class member”

A member function can be

•non-const – allowed to modify the state of objects

•const – can not modify the state of objects

– important to declare member functions const if they are not to modify object state

– some const functions may need to alter a data member – declare the data member mutable

– be “const correct”, sooner or later you will otherwise get into trouble…

TDDD38 APiC++ Single class design 52

Class String definition, selected parts (1)

class String

{

public:

using size_type = std::size_t; // nested type (alias declaration)

String() = default;//default constructor, compiler generated

String(const String&); // copy constructor

String(String&&) noexcept;//move constructor

String(const char*); // type converting constructor, from C string

String(size_type, char);

String(std::initializer_list<char>);

~String(); // destructor

String& operator=(const String&) &; // copy assignment operator, ref-qualifier (lvalues only)

String& operator=(String&&) & noexcept;//move assignment operator

String& operator=(const char*) &; // type converting assignment operator

size_type length() const;//const member function – accessor function

bool empty() const;

void clear(); // non-const member function – mutator function

const char* c_str() const;//type conversion to C string

explicit operator const char*() const;

void swap(String&) noexcept;//swap content with other String

TDDD38 APiC++ Single class design 53

Class String definition, selected parts (2)

private:

static char empty_rep_[1]; // static, null-terminated C string to represent empty string

size_type size_{ 0 }; // NSDMI

char* p_{ empty_rep_ };

// Internal helper functions

void construct_(const char*, size_type);

void construct_(size_type, char);

void construct_(std::initializer_list<char>);

void append_(const char*);

void append_(char);

};

empty_rep_ is defined in the implementation file:

char String::empty_rep_[1]; // initialized to ’\0’

A non-empty String has its own, dynamically allocated memory – a null terminated character array (“C string”).

’\0’

size_:

p_:

’C’ ’+’ ’+’

’\0’

size_:

p_:

TDDD38 APiC++ Single class design 54

Creating and operating on class objects

Class objects – variables and constants – can be either automatically och dynamically created/destroyed.

int main()

{

String s; // variable String

const String cs{ s }; // constant String – only const member functions can be applied

cout << cs.c_str() << " has length " << cs.length() << ’\n’; // the dot operator

String* ps{ new String }; // dynamically created String object, pointed to by ps

const char* p{ ps->c_str() }; // the arrow operator to access member in pointed-to object

String& rs{ s }; // reference to String – alternative name for s

cout << rs << endl; // a reference is automatically dereferenced when used

}

• another implicitly defined operator is the important scope resolution operator ::

class::member // qualified name

• there are quite a few more implicitly defined operators

TDDD38 APiC++ Single class design 55

Definition of member functions

• separately, outside the class definition, e.g on an accompanying implementation file String.cc

#include "String.h"

…

String::size_type String::length() const

{

return size_;

}

–String:: must precede the name of any separately defined member – a qualified name

– also when from outside class scope referring to a member, such as size_type

– the parameter list and the function body is within class scope of String

• within the class definition (inclass definition)

class String

{

…

size_type length() const { return size_; }

…

};

• member functions defined inclass are automatically inline functions

• separately defined member functions can explicitly be declared inline

TDDD38 APiC++ Single class design 56

Special member functions

•default constructor – initializes a new object without any arguments

•copy constructor – initializes a new object from an existing object of the same type

•move constructor – typically used if the source is a temporary object of the same type

•copy assignment – assigns from an object of the same type

•move assignment – typically used if the right hand side is a temporary object of the same type

•destructor – cleans up when an object cease to exist, typically releasing resources

Compiler generated (implicitly declared/defined) if not declared by programmer (there are detailed rules), with the following semantics:

• default constructor

– data members with default initialization (class type members) are default initialized, in declaration order

– data members without default initialization are not initialized, e.g. fundamental type members (int,double,pointers, etc.)

• copy constructor,

– member-by-member copy construction from source to destination, in declaration order

• copy assignment

– member-by-member assignment from source to destination, in declaration order

• move constructor, move assignment

– instead of copying content, it is moved from the source to the destination

• destructor

– data members with destruction (class type members) are destroyed, in reverse declaration order

TDDD38 APiC++ Single class design 57

Constructors

• one is always invoked automatically when class objects are created

• shall initialize the objects to a well-defined state

• cannot be declared to return anything, not even void

• can have parameters – these can have default arguments – can be overloaded – a class can have several constructors

String(const char*);

String(const String&);

String(String&&) noexcept;

String(std::initializer_list<char>);

•default constructor – a constructor which can be used without any arguments

String(const char* s = ""); // if no explicit argument, "" will be used – “two-in-one”

•copy constructor – a constructor with a (first) parameter of the class type – to create a new object as a copy of another

String(const String& other); // creates the new object as a copy of other

•move constructor – a constructor with a (first) parameter of type rvalue reference – to create a new object by emptying another

String(String&& other) noexcept;//creates the new object by pilfering the content of other

•type converting constructor – a constructor which can be invoked with one argument of another type

String(const char* s); // converts C string to String

TDDD38 APiC++ Single class design 58

Using constructors

Selected by overload resolution.

{

String s1; // default constructor called – empty String created

String s2{ "C++" }; // initializing with string literal – type conversion

String s3{ s2 }; // initializing with another String object – copy

String* p{ new String{"C++"} }; // constructor taking a C string called

vector<String> v(10); // 10 container elements – default constructor used for each

String a[10]; // array element – default constructor is used for each element

String s5{ ’C’, ’+’, ’+’, ’1’, ’1’ }; // constructor taking initializer list

}

Note – the following declaration does not create a default constructed String s

String s();

but this expression does, a temporary object

return String();

TDDD38 APiC++ Single class design 59

Member initializers

Amember initializer list can be used in constructors to initialize data members before the constructor body is executed.

Alternative implementation for String(const char* str), possible if we could be sure the parameter str in never nullptr:

String(const char* s)

: size_{ strlen(s) }, p_{ strcpy(new char[size_ + 1], s) }

{}

• if both an initilizer in the data member declaration, and a member initializer as above, only the member initializer will be executed

• a member initializer list is inserted between the constructor parameter list and the constructor body

– starts with a colon

– initializers are separated with comma, if more than one

• the data members are initialized in declaration order, not in the order initializers are written

–size_ must be declared before p_ , since the value of size_ is used in the initializer for p_

– always write member initializers in the same order as the members are declared

• a member with default initialization will always be default initialized before the execution enters the constructor body

– use initializer, if possible, instead of assignment in constructor body, to avoid “double” initialization

•const and reference members cannot be assigned in the constructor body

– follows from ordinary semantic rules – such types must always be initialized when they are created

• member initializer is the only way to invoke a base class constructor from a subclass constructors

Derived(parameters) : Base(arguments), … {}

TDDD38 APiC++ Single class design 60

Destructor

• called automatically when an object is on its way to disappear

– for a dynamically created object (new) when deleted (delete)

• typically used to release resources, e.g. deallocate memory, or closing a file

~String() { if (!empty()) delete[] p_; }

• cannot be declared to return anything – not even void

• have no name – special declaration syntax

• cannot have parameters – cannot be overloaded – a class can only have one destructor

• explicitly called only in special cases

{

String s; // s created automatically – constructor invoked

String* p{ new String }; // Object created dynamically – constructor invoked

…

delete p; // Dynamic object deallocated – destructor implicitly invoked

p = nullptr;

…

}//declaration block for s is terminated – s disappears –the destructor is implicitly invoked

TDDD38 APiC++ Single class design 61

The this pointer

One problem with the calling syntax for member functions is that the object don’t belong to the parameter list

s.at(7);

as in a traditional function call

at(s, 7);

where the object s is accessible in the function through the corresponding parameter.

• what if you need to refer to the object in question in a member function – use the this pointer

– in a non-static member function this points to the object for which the function is called

– in a non-const member function this have type String*

– in a const member function this have type const String*

–volatile can also appear, e.g. const volatile String*

–move semantics can also be applied to *this (comes later)

•this is usually used implicitly to access members – an explicit reference is written, e.g.

size_type String::length() const

{

return this->size_;

}

– length() is const – the this pointer have type const String* – the object is const in this context – size_ cannot be modified

TDDD38 APiC++ Single class design 62

Default constructor

Since there are other constructors declared, a default constructor would not be generated, according to rule.

• a naïve, straight-forward way to define the default constructor would be

String() {}

– the data members will be initialized according to the initializers in their declarations

•bydefaulting, we ask the compiler to generate

String() = default;

– a defaulted function can be more efficient than a hand-written one

TDDD38 APiC++ Single class design 63

Type converting constructor

A constructor taking one argument of another type defines a type conversion, possibly implicit.

• declaring explicit means that it cannot be invoked to make implicit type conversions

class String

{

public:

String(const char*); // not explicit

…

};

•Ifoperator=(const char*) had not been declared for String, the assignment below would still be allowed

s = "This is a literal of type const char*";

– semantically equivalent to

s = String("This is a literal of type const char*");

– the literal of type const char* is converted to a temporary object of type String this constructor

–operator=(String&&) can then be applied to s and the temporary object

TDDD38 APiC++ Single class design 64

Copy constructor

Deep copy.

• the compiler generated constructor would just copy size_ and p_ – the character array would be shared by several object

• a new object is to be created – no history to take into account if something goes wrong

• the helper function construct_ takes care of the greedy details – memory allocation and copying value from other

String::String(const String& other)

{

construct_(other.p_, other.size_);

}

void String::construct_(const char* cstr, size_type size)

{

if (cstr != nullptr && size > 0)

{

p_ = strcpy(new char[size + 1], cstr);

size_ = size;

}

String s2{ s1 }; // direct initialization syntax

String s2 = s1; // copy initialization syntax

– allocating memory for the character array is the critical part – if new throws (bad_alloc), just bail out – no cleanup required

– copying size is safe – memory for the String object itself (size_ and p_) is already there, assigning int will not fail

’C’ ’+’ ’+’ ’\0’

TDDD38 APiC++ Single class design 65

Copy assignment operator

Deep assignment.

s1 = s2;

• left hand side has a history

– dispose of old content

– copy new value from right hand side

• important to do things in the right order

– no object should end up in an undefined state

– make sure to get new memory first

– then make changes

’C’ ’+’ ’+’

’\0’

s2:

s1: ’S’ ’c’ ’e’

’\0’

’m’ ’e’’h’

’C’ ’+’ ’+’

’\0’

s1:

’S’ ’c’ ’e’

’\0’

’m’ ’e’’h’

’C’ ’+’ ’+’

’\0’

s2:

TDDD38 APiC++ Single class design 66

Copy assignment operator – straightforward implementation

• the default copy assignment would just assign size_ and p_ – the character array from source object would be shared

• the destination is an existing object – old content to take care of – otherwise the same copy semantics as for the copy constructor

String& String::operator=(const String& rhs) & // ref qualifier – assign to lvalue only

{

if (this != &rhs)

{

char* p{ empty_rep_ }; // in case rhs is an empty String

if (!rhs.empty())

p = strcpy(new char[rhs.size_ + 1], rhs.p_); // if we survive this we’re fine

size_ = rhs.size_;

if (!empty()) delete[] p_;

p_ = p;

}

return *this;

}

• checks if the left and right hand side operands are the same object – self-test

s = s

• performs a deep copy in a strongly exception-safe way – allocates memory before anything is changed – if new throws

– no memory will leak

– none of the objects will be corrupted

• semantics corresponds to built-in assignment – returns a non-const reference (lvalue) to the left-hand side argument

TDDD38 APiC++ Single class design 67

Copy assignment operator – elegant version

• uses the idiom “create a temporary and swap”

• need a function that can exchange the contents of two objects in a safe way, preferably a nothrow swap

String& String::operator=(const String& rhs) &

{

String{ rhs }.swap(*this); // create a temporary and swap

return *this;

}

• a temporary is created and initialized by the copy construct – deep copy of rhs

• the contents of this and the temporary is swapped

–this now becomes a copy of rhs

– the temporary takes over of the old content of this – especially the character array

• the temporary is destroyed after the swap

– the old dynamic memory for this is deallocated

• if an exception is thrown, it will happen when the temporary is initialized

– strongly exception-safe – no memory will leak – no object will end up in an undefined state

– exception neutral – any exception thrown is propagated further as is

Note. If the elements had been of class type, exceptions could also be thrown when copying the elements,

TDDD38 APiC++ Single class design 68

Move semantics

One of the big news in C++11 – alternative to classic copy semantics.

•temporary objects are created in different situations – often implicitly

• if such an object is used to initialize or assign another object it is unnecessary to make a copy

– copying can be costly – time and space

– instead move the content of the temporary to the destination object

• how find such objects – they are not visible?

– the compiler knows!

–rvalue-references catches them automatically!

– we just need to be aware of the possibility and have it in mind when we construct classes

String(const String&); // this can catch all kind of objects but

String(String&&) noexcept;//this one is a better match for temporary objects (rvalues)

String& operator=(const String&) &;

String& operator=(String&&) & noexcept;

• implementing move semantics

– an object which resources have been moved must be destructible

– sometimes we want to apply move semantics also to ordinary objects (lvalues)

– an object which have been moved from must be assignable (and copyable)

– the principle should be that an object moved from should be comparable to a default initialized object

TDDD38 APiC++ Single class design 69

Move constructor

Our implementation use the member functions swap():

String::String(String&& other) noexcept // size_ and p_ are initialized by their NSDMI –empty string

{

swap(other); // swap content with other

}

String s1 = String{ "C++" }; // temporary object (rvalue)

String s2{ std::move(s1) }; // utility function move() converts s1 (lvalue) to String&& (rvalue)

when entering constructor body after move

’C’ ’+’ ’+’

’\0’

’C’ ’+’ ’+’

’\0’

s2:

s1:

TDDD38 APiC++ Single class design 70

Move assignment operator

Our implementation uses clear() and swap():

String& String::operator=(String&& rhs) & noexcept

{

clear(); // the left hand side operand is cleared – set to ”empty string”

swap(rhs); // move by swapping content with the right hand side operand

return *this;

}

s1 = std::move(s2);

start state s1 cleared after move

An alternative is to just swap contents for the two objects (there is no precise definition of move semantics).

’C’ ’+’ ’+’

’\0’

’C’ ’+’ ’+’

’\0’

’C’ ’+’ ’+’

’\0’

’C’

’\0’

s1:

s2:

TDDD38 APiC++ Single class design 71

Rules for move constructor and move assignment operator generation

• The move constructor is only generated if, the class does

–not have a user declared copy constructor

–not have a user declared copy assignment operator

–not have a user declared move assignment operator

–not have a user declared destructor

• The move assignment operator is only generated if, the class does

–not have a user declared copy constructor

–not have a user declared move constructor

–not have a user declared copy assignment operator

–not have a user declared destructor

Style recommendations for declaring special member functions

• if a special member function is desired, and the compiler can generate it – default it

• if a special member function is not desired, and the compiler will generate it – delete it

• if a special member function is not desired, and the compiler will not generate it – don’t declare it

TDDD38 APiC++ Single class design 72

The name rule

Things that are declared as rvalue reference can be either an rvalue or an lvalue. The name rule says:

• if it has a name it’s an lvalue

•otherwise, it’s an rvalue

void foo(T&& x) // rvalue reference having a name, x

{

T y{ x }; // x is an lvalue, T::T(const T&) is called

… // x still in scope – it would be dangerous to allow move semantics to be allowed tacitly

}

T&& fie(); // rvalue reference having no name

T x{ fie() }; // T::T(T&&) is called

T fum(); // rvalue having no name (temporary)

T y{ fum() }; // T::T(T&&) is called

TDDD38 APiC++ Single class design 73

Utility function std::move()

The traditional way to exchange values for two String variables:

void swap(String& x, String& y)

{

String tmp{ x }; // x is copied to tmp by the copy constructor

x = y; // y is copied to x by the copy assignment operator

y = tmp; // tmp is copied to y by the copy assignment operator

}

Both x and y shall receive new values – their old values is not required to be kept when they are copied – move instead

#include <utility>

void swap(String& x, String& y)

{

String tmp{ std::move(x) }; // x is moved to tmp by the move constructor

x = std::move(y); // y is moved to x by the move assignment operator

y = std::move(tmp); // tmp is moved to y by the move assignment operator

}

• std::move() doesn’t really do more than type convert to an rvalue reference – String&& in this case

• this will make the move versions to be chosen instead of the copy versions

Note: move() basically applies static_cast<String&&>(arg)

TDDD38 APiC++ Single class design 74

Ref-qualifiers for non-static member functions

Extends move semantics to *this – thee options:

• no ref-qualifier

•& ref-qualifier, same as no ref-qualifier

•&& ref-qualifier

struct X

{

void fun() &; // OK, *this will be X& – lvalue reference

void fun() &&; // OK, *this will be X&& – rvalue reference

void fun() const &; // OK, *this will be const X& – lvalue reference to const

};

•& and && can be overloaded, in combination with the cv-qualifers

struct X

{

X* operator&() &; // selected for lvalues only

X& operator=(const X&) &; // selected for lvalues only

};

X* p = &X(); // error: takes the address of something temporary (rvalue)

X x;

X() = x; // error: no known conversion for implicit this parameter from X to X&

TDDD38 APiC++ Single class design 75

Situations where special member functions are used

String g1{ ”Global” }; // g1 is initialized by the type converting constructor for C string

String g2{ g1 }; // g2 is initialized by the copy constructor – direct initialization syntax

String fun(String s) // s is initialized by the copy constructor, unless the argument is a temporary, then move

{

String loc{ s }; // loc is initialized by the copy constructor

loc = s; // loc is assigned by the copy assignment operator

return loc; // a temporary object is created and initialized by the move constructor

}//the local objects s and l are destroyed by the destructor

int main()

{

String g3 = g1; // g3 is initialized by the copy constructor – copy initialization syntax

g2 = fun(g1); // g2 is assigned from a temporary – invokes the move assignment operator

}

Sometimes the temporary used for passing a return value from a function can be elided.

• in such case the value of loc would be directly copied or moved into a destination object

• a common optimization called RVO – Return Value Optimization

TDDD38 APiC++ Single class design 76

Delegating constructors

A constructor can delegate to another constructor of the same class.

• if empty Strings had been represented in the same way as non-empty Strings, the default constructor could have been written:

String() : String{ "" } {} // delegate to the constructor below

String(const char*);

• an alternative is to let the type converting constructor also represent the default constructor (as we have chosen)

String(const char* = "");

TDDD38 APiC++ Single class design 77

Ways to restrict and control object creation (1)

Some objects, e.g. stream objects, are not suitable to copy.

• copy construction and copy assignment can be disallowed

• declare delete to remove a special member functions,

•default if you want the compiler to generate

public:

X() = default;//default initialization allowed

X(const X&) = delete;//no copy construction

X& operator=(const X&) = delete;//no copy assignment

• if, e.g., the compiler generated copy constructor is fine, but you want to restrict it for internal use only, default it as protected

protected:

X(const X&) = default;

• if at least one of the destructor, copy constructor or copy assignment operator is declared, the move constructor or move assignment

operator are not generated

– the move constructor and move assignment operator should never be deleted – either declare, if desired, or ignore, if not

• eliminating public constructors does not make a class abstract (derived classes)

Note: a defaulted function must be a member function, a deleted function need not be.

TDDD38 APiC++ Single class design 78

Ways to restrict and control object creation (2)

Dynamic memory allocation can be disallowed by hiding the predefined global allocation functions.

private:

static void*operator new(size_t) = delete;//plain versions

static void operator delete(void*, size_t) = delete;

static void*operator new[](size_t) = delete;//array versions

static void operator delete[](void*, size_t) = delete;

• these are always static members, even if not explicitly declared so

• there are also nothrow and placement versions of global new/new[] and delete/delete[]

In the context of derived classes there is also the concept of abstract class, for which no objects can be created, except as subobjects of objects

of a derived concrete class.

For a new expression, such as ’new String’, one of these new functions will be called, resulting in a two-step procedure:

• memory is acquired, and, if successful, then

• the constructor is executed to create the object in that memory

For a delete expression, such as ’delete p’, one of these delete functions will be called, also resulting in a two-step procedure:

• the destructor is executed to destroy the object in the memory

• the memory is released

TDDD38 APiC++ Single class design 79

Type conversion functions

Type conversion from a class to some other type is defined as a conversion function.

• can be declared explicit to disallow implicit use

class String

{

public:

…

operator const char*() const { return p_; } // not explicit

…

};

// If not present: ostream& operator<<(ostream&, const String&);

String s{ "Hello World!" };

cout << s << endl; // Implicit type conversion to const char*

• this type conversion function makes it possible to use predefined operator<< for const char*, if not declared explicit

– such conversion can cause much more problems than it solves

– be aware of possible type conversion sequences for arithmetic types

–explicit solves such problems but allows explicit use, e.g.

cout << static_cast<const char*>(s) << endl;

• an ordinary member function doing the same can be an alternative, or a complement – c_str()

TDDD38 APiC++ Single class design 80

Static members

String have a static data member to represent the empty string value.

• member functions and data members declared static are common for all object belonging to a class – class members.

class C

{

static int s; // static data member declaration

static int get_s(); // static member function declaration

};

int C::s{}; // static data member definition, explicitly initialized

int C::get_s() { return s; } // static member function definition

• Static members can be accessed in two ways:

– class name and the scope operator (qualified name)

C::get_s()

– an object and the dot operator, or a pointer to an object and the arrow operator

object.member

pointer-to-object->member

TDDD38 APiC++ Single class design 81

A class, its operations, namespaces, and name lookup

A nonmember function belonging to a class is an operation of that class, no less than a member function.

• natural to declare such non-member functions in the same namespace as the class

•argument dependent lookup (ADL) is applied to unqualified function names and depend upon the arguments given in the call

– if a member function turns up, ADL does not occur

– the set of namespaces searched during ADL depends upon the types of the function parameters

– at least namespaces containing the parameter types belong to the set of searched namespaces

• there are known problems – ADL may lead to unpleasant “surprises”

A namespace is a simple module construct.

• encapsulates the declarations within it – access controlled by using directives and using declarations

using namespace std; // opens the entire standard namespace – all names becomes directly visible

using std::string; // introduces the name string, as if it was declared at this point

• can be added to, successively

• have influence on name lookup

TDDD38 APiC++ Single class design 82

String and namespace

String is encapsulated in a namespace named IDA_String.

• first introduced in String.h (original namespace definition)

namespace IDA_String

{

class String { … };

…

}

#endif

• added to in String.cc (extension namespace definition)

#include "String.h"

namespace IDA_String

{

Separate definitions for String member functions

}

•aqualified name including the namespace name can alternatively be used:

IDA_String::String::size_type IDA_String::String::length() const { … }

TDDD38 APiC++ Single class design 83

String iterators

String is a container storing elements of type char, and should as such have iterators.

for (auto it = begin(s); s != end(s); ++i) …

• String iterators can be defined as character pointers and implemented as random access iterators

using iterator = char*;

using const_iterator = const char*;

using reverse_iterator = std::reverse_iterator<iterator>;

using const_reverse_iterator = std::reverse_iterator<const_iterator>;

– iterator operators are given by the ordinary pointer operators: *, ->, ++, --, etc.

– std::reverse_iterator is a standard template utility class to define reverse iterators, given the forward iterators iterator and

const_iterator

– usually iterator and const_iterator must be defined as classes

• the full set of iterator member functions are defined, some examples

iterator begin() { return iterator(p_); }

const_iterator begin() const { return const_iterator(p_); }

iterator end() { return iterator(p_ + size_); }

const_iterator end() const { return const_iterator(p_ + size_); }

Iterators will be covered in the standard library lectures.

TDDD38 APiC++ Single class design 84

Some recommendations for single class design (1)

• a class should do one thing, and do it well

• members not to be accessed directly should be private (or protected)

• member functions that does not modifying the state of the objects shall be const

• can the constructors initialize the object in all desired ways?

• declare and initialize data members in the same order.

– the declaration order determines the initialization order, so be consistent with that

• prefer initialization to assignment in constructors

– often more readable

– avoids “double initialization” of default initialized members

• does the compiler generated copy constructor, copy assignment operator, and destructor work, or must they be defined?

• copy and destroy consistently

– if you write/disable the copy constructor or the copy assignment operator, you probably need to do the same for the other

– if you write copy functions, you probably need to write a destructor, and vice-versa

• explicitly enable or disable copying (copy constructor and copy assignment)

– if desired and compiler versions works fine – default both

– if not desired – delete both

– if desired but the compiler generated versions does not work correctly – write both

– deleting a function declares it private – don’t delete move constructor or move assignment operator if their copy versions are allowed

TDDD38 APiC++ Single class design 85

Some recommendations for single class design (2)

• make data members private, except in behaviourless aggregates (C-style structs)

–std::pair is defined as a struct with only public members

• don’t give away your internals

– let e.g. member access functions return reference to const or pointer to const

• avoid providing implicit conversions

– eliminates or minimizes creation of temporary objects by type converting constructors and function

– prefer to declare converting constructors and conversion functions explicit

– define optimized operator overloadings for the mixed type operation to be allowed

• whenever it makes sense, provide a no-fail swap

– nice things can be done using swaps

• design and write error-safe code

• don’t optimize prematurely – don’t inline by default, it leads to higher coupling

– profilers are good at telling you which functions you should mark inline

– profilers are bad at telling you which functions you should not have marked inline

–inline may not even matter for your compiler…

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 96

Derived classes

C++ has a relatively complete and complicated derivation mechanism.

• supports several inheritance models

–single inheritance – only one direct base class

–multiple inheritance – two or more direct base classes

–repeated inheritance – an indirect base class is inherited several times through multiple inheritance

– multiple and repeated inheritance can lead to ambiguities and other problems – need for ways to solve such – virtual inheritance

–static members,nested types and enumerators are class members – can always be found unambiguously

• several ways to specify access to base class members in a derived class

–public – public members of the base class are accessible as public in the derived class, protected members as protected

–protected – public members of the base class are accessible as protected in the derived class, protected members as protected

–private – public and protected members of the base class are accessible as private in the derived class

– default access is public if a base class is a struct,private if it is a class

• in case of repeated inheritance the number of subobjects of a repeatedly inherited base class can (must) be controlled

–virtual base class – in combination with one of the three above, e.g. virtual public

• polymorphic behaviour is controlled by the programmer

– only virtual functions can be bound dynamically and have polymorphic behaviour

– objects must be referred to by pointers or references, if virtual function calls are to be bound dynamically

– the overhead of polymorphism can be avoided if not desired – don’t declare any virtual functions unless required

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 97

Person-Employee-Manager-Consultant – a polymorphic class hierarchy

Design of a simple polymorphic class hierarchy for different categories of employees

• class representing persons in general – Person

– have name and civic registration number

– all employees shall share the properties of this class

– no Persons are to be created – shall be an abstract class

• class for employees in general – Employee

– have employment date, employment number and salary, works at a department

– Employees are to be created – shall be a concrete class

• class for employees that also are department managers – Manager

– manages a department and its employees

• class for (temporary) employees that are consultants – Consultant

– no actual difference to employees in general but need to be distinguishable

• objects are supposed to be referred to by pointers and created dynamically

– otherwise no polymorphic behaviour, and the way objects are copied require dynamic allocation

– other polymorphic type objects may be declared statically and polymorhism obtained to by reference passing

Person

Employee

Manager Consultant

(abstract)

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 98

Class Person

class Person

{

public:

virtual ~Person() = default;

virtual Person* clone() const = 0;

virtual std::string str() const;

std::string get_name() const;

void set_name(const std::string&);

CRN get_crn() const;

void set_crn(const CRN&);

protected:

Person(const std::string& name, const CRN& crn);

Person(const Person&) = default;
Person(Person &&) = default;

private:

Person& operator=(const Person&) = delete;

std::string name_;

CRN crn_;

};

Person

(abstract)

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 99

Comments on Person

• basically a trivial class

– well-behaved data members regarding initialization, copying/moving, and destruction

– generated copy constructor and move constructor are fine, but allowed only for internal use – protected and default

– no obvious use of move constructor, but since the copy constructor is allowed…

•defaulted and deleted member functions

– the default constructor is not generated when another constructor is declared – could be defaulted if required

–copy assignment shall not be allowed – deleted – access specification does not matter, it will be private regardless

–move assignment is not generated because of other declared special member functions (more about this later)

– only special member functions can be defaulted – any function can be deleted

•virtual functions – virtual

– virtual functions can be overridden by subclasses

– happens if a function with the same signature is declared in a subclass – virtual is then optional

– a function in a subclass with the same name but with different signature will instead hide

– makes the class polymorphic

•pure virtual function

–apure specifier = 0 makes a virtual function publicly non-callable

–can have a separate definition – must, if a destructor – callable by other member functions, and from subclass member functions

– pure virtual functions are inherited – a subclass becomes abstract unless all inherited pure virtual functions are overridden

– makes the class abstract

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 100

Comments on Person, cont.

•polymorphic class

– have virtual functions, own or inherited

– must have a virtual destructor to ensure correct destruction of subobjects

– objects will contain type information – used when calling virtual functions and by dynamic_cast

– objects will contain a virtual table (e.g. __vtable) – implementation technique for calling virtual functions (generated by compiler)

• abstract class

– no free-standing objects can be created

• protected constructors

– since Person is abstract there is no need for any public constructor

–protected constructors can be used to emphasizes abstractness

•static type and dynamic type

Person* p{ new Employee{ … } }; // p has static type “pointer to Person”

p->clone(); // the dynamic type of the expression *p is Employee

– the static type is used during compilation to check if clone() is valid for the kind og object that p kan point to

– the dynamic type is used during execution to bind the overriding of clone() corresponding to the object p actually points to

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 101

Constructor taking name and civic registration number

Person::Person(const std::string& name, const CRN& crn)

: name_{ name }, crn_{ crn }

{}

Ensures that a new Person always have a name an a civic registration number.

• default constructor is eliminated

• no other constructor is available that can initialize an object in some other way, except the copy and move constructor

• only to be used by corresponding direct subclass constructors – declared protected

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 102

Member function str()

virtual string Person::str() const;

Definition:

string Person::str() const

{

return name_ + ’ ’ + crn_.str();

}

A call will be bound dynamically, if the object in question is referred to by a pointer or a reference

• the dynamic type decides which overriding to be called

Person* p = new Manager{ name, crn, date, employment_number, salary, dept };

cout << p->str() << endl;

– pointer p has static type Person*

– expression *p has dynamic type Manager

(*p).str()

–Manager::str() is called – we prefer the arrow operator in this case

p->str()

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 103

Member function clone()

virtual Person* clone() const = 0;

A polymorphic class needs a polymorphic copy function.

• the copy constructor could be used, but it would be very cumbersome

• polymorphic class objects are often allocated dynamically and handled with polymorphic pointers

Person* p = new Manager{ name, crn, date, employment_number, salary, dept };

Person* copy = p->clone();

• every concrete subclass must have its own, specific, overriding of clone()

– it’s the programmer’s responsibility to ensure this

– it’s possible to code so the compiler can check this

• suitable candidate for making Person abstract

– we have decided to not allow Person objects a such

– made pure virtual by the pure specifier (= 0)

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 104

Subclass Employee

class Employee : public Person

{

public:

Employee(const std::string& name,

const CRN& crn,

const Date& e_date,

const int e_number,

const double salary,

const int dept = 0);

~Employee() = default;

Employee* clone() const override; // note return type!

std::string str() const override;

int get_department() const;

Date get_employment_date() const;

int get_employment_number() const;

double get_salary() const;

protected:

Employee(const Employee&) = default;

Person

Employee

(abstract)

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 105

private:

Employee& operator=(const Employee&) = delete;

friend class Manager;

void set_department(const int dept);

void set_salary(const double salary);

Date e_date_;

int e_number_;

double salary_;

int dept_;

};

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 106

Comments on Employee

• trivial class

– same considerations as for Person

• an Employee object consists of a subobject of type Person and the specific Employee data members

– the Person subobject is by definition initialized before the other members of Employee

– the Person subobject is by definition destroyed after the other members of Employee

– the only way to pass arguments to a base class constructor is by a member initializer

• both virtual functions are overridden

– Employee is to be a concrete class

– require a specific version of str()

– clone() must be overridden for every concrete class

– marking a virtual function with override makes the compiler check there is such a virtual function to be overridden

Employee* clone() const override;

– recommended style is to not declare virtual when using override

• Manager is declared friend

– all member functions of Manager is given unrestricted access to all Employee members, including private members

–friendship creates stronger coupling than derivation – derivation does not give access to private members

– why Employee declares Manager a friend we leave to later …

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 107

Employee’s public constructor

Employee::Employee(const string& name,

const CRN& crn,

const Date& e_date,

const int e_nbr,

const double salary,

const int dept)

: Person{name, crn}, e_date_{e_date}, e_number_{e_nbr}, salary_{salary}, dept_{dept}

{}

• Person subobject is by definition initialized first

– write the Person initializer first in the member initializer list

– avoids unnecessary warnings

• Employee data members are then initialized in declaration order

– write the member initializers in that order

– avoids unnecessary warnings

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 108

Member function str() overridden

string Employee::str() const override

{

return Person::str() + " (Employee) " + e_date_.str() + ' ' + std::to_string(dept_);

}

• calls str() for the Person subobject to produce part of the string to return

•std::to_string() is overloaded for all fundamental types

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 109

Member function clone() overridden

Employee* clone() const override

{

return new Employee{ *this };

}

• shall create a dynamically allocated copy of the object for which clone() is called, and return a pointer to that object

• the copy constructor is the natural choice to make a copy

• since the return type belongs to a polymorphic class hierarchy we are allowed to adapt it

Employee* p1= new Employee{ name, crn, date, employment_nbr, salary };

Employee* p2 = p1->clone(); // no cast needed if clone() returns Employee*

Person* p3 = p1->clone(); // implicit upcast – Employee* to Person*

• the types are said to be covariant

– adapting the return type for clone() is allowed because of their close relation to each other

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 110

Subclass Manager

class Manager : public Employee

{

public:

Manager(const std::string& name,

const CRN& crn,

const Date& e_date,

const int e_number,

const double salary,

const int dept);

~Manager() = default;

Manager* clone() const override;

std::string str() const override;

void add_department_member(Employee* ep) const;

void remove_department_member(const int e_number) const;

void print_department_list(std::ostream&) const;

void raise_salary(const double percent) const;

protected:

Manager(const Manager&) = default;

Person

Employee

Manager

(abstract)

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 111

private:

Manager& operator=(const Manager&) = delete;

// Manager& operator=(Manager&&); is not generated

// Manager does not own the group members objects, no clean-up required

// Employment number is key

mutable std::map<int, Employee*> dept_members_;

};

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 112

Comments on Manager

• trivial class

– well-behaved std::map member dept_members_ – default initialized to an empty map

– otherwise same considerations and measures taken as for Employee and Person

• a Manager object consists of a subobject of type Employee, which in turn consists of a subobject of type Person, and a std::map object

– base members are initialized top-down – Person subobject first, then Employee subobject, thereafter dept_members_

– destruction is performed in the opposite order – dept_members_ – Employee members – Person members

• dept_members_ is declared mutable

– add_department_member() och remove_department_member() modifies the object

– we prefer to regard them as non-modifying operations from a public point of view – const

–mutable allow dept_members_ to be modified by const member functions

• Manager was declared friend by Employee

– Manager does not access any private members of Employee – so why?

– we will soon find out…

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 113

Manager’s public constructor

Manager(const std::string& name,

const CRN& crn,

const Date& e_date,

const int e_number,

const double salary,

const int dept)

: Employee{ name, crn, e_date, e_number, salary, dept }

{}

• all parameters are passed as arguments to direct base class Employee’s constructor

• dept_members_ have default construction – an empty employee list is created for a new Manager

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 114

Member function clone() overridden

Manager* clone() const override

{

return new Manager{ *this };

}

Suppose we forget to override clone() in Manager.

• the final overrider is then Employee::clone()

• instead of a Manager clone() would return an Employee

– copied from the Employee subobject of the Manager which was to be copied

– Employee copy constructor creates the copy – member by member copy of the Employee data members

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 115

Adding and removing department employees is done by Manager

void Manager::add_department_member(Employee* ep) const

{

// Set employee's department to same as manager's department

ep->set_department(get_department()); // require friendship

// Add employee to department members

dept_members_.insert(make_pair(ep->get_employment_number(), ep));

}

• Manager must be friend of Employee, to be allowed to call Employee::set_department() in this context

– function parameter ep is a pointer to an Employee

– only public operations are then allowed (unless Manager is a friend of Employee)

• it makes no difference if set_department() had been protected, Manager must still be friend

–protected access is only allowed when the accessed object is a subobject of the accessing object

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 116

Consultant

class Consultant final : public Employee // no subclassing

{

public:

using Employee::Employee; // inheriting constructors

~Consultant() = default;

Consultant* clone() const override;

std::string str() const override;

protected:

Consultant(const Consultant&) = default;

private:

Consultant& operator=(const Consultant&) = delete;

};

Person

Employee

Consultant

(abstract)

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 117

Comments on Consultant

• no real difference compared to Employee

– same data members, same set of operations

• we want to be able distinguish consultants from ordinary employees

– subtyping is a way to allow for that by dynamic type checks

• marking a class final

class Consultant final : public Employee

– not allowed to derive from Consultant

• marking a virtual function final

string str() const override final;

– such a function is not allowed to override in subclasses

•inheriting constructors

using Employee::Employee;

– naming a constructor in a nested using declaration opens for inheriting constructors from a base class

– the public constructor for Manager and Consultant is inheried from Employee

– our special member functions must still be declared

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 118

The using declaration in class scope

•ausing-declaration introduces a name in the declarative region in which it appears

using name; // an alias for the name of some entity declared elsewhere

• can be used in class scope to introduce names from a base class

using Base::hidden;

– inheriting constructors

using Base::Base;

• the alias created has the usual accessibility for a member declaration

– an alias can be a public alias for a protected member

–ausing-declaration can not make a private member of a base class (more) accessible

• member functions in the derived class override and/or hide member functions with the same name and

parameter types in the base class

• can not be used to resolve inherited member ambiguities

Note: Ausing-directive can not appear in class scope, so the following is not allowed in class scope:

using namespace std;

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 119

Using the using declaration in class scope

class A

{

public:

void f();

void h(); // h can be named in a using declaration, since no private h

protected:

void h(int);

void g(); // g can be named in a using declaration, since no private g

void g(int);

void p();

private:

void f(int); // using A::f not possible (access control)

void p(int); // using A::p not possible (access control)

};

class B : public A

{

public:

using A::h; // OK

using A::g; // OK

using A::p; // error: void A::p(int)is private within this context

private:

using A::f; // error: void A::f(int)is private within this context

};

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 120

Inheritance and special member functions

• The default constructor and the copy/move constructors are not inherited,

– implicitly-declared in a derived class, if not user declared

• The destructor is not inherited,

– implicitly-declared, if not user declared

•Operator functions are inherited, but

– inherited copy/move assignment operators are always hidden, either by implicitly-declared or user declared copy/move assignment

operators of the derived class

•Ausing-declaration that brings in a copy/move constructor or a copy/move assignment operator from the base class is not concidered an

explicit declaration and does not supress the implicit declaration of these functions in the derived class. Such special member functions

introduced by a using-declaration is therefore hidden by the implicit declaration.

• A using-declaration cannot refer to a destructor for a base class.

• Other constructors brought in from a base class by a using-declaration are inherited.

For Consultant this gives that

• the default constructor is not inherited (never is), and is not implicitly-declared since other constructors are declared

• the copy/move constructors are not inherited (never is) – are user declared (defaulted)

• the destructor is not inherited (never is) – is user declared (defaulted)

• the copy assignment operator is inherited but hidden, as always, in this case by a user-declared (deleted) copy assignment operator

• the move assignment operator is not implicitly-declared since, e.g., the copy assignment operator is explicitly declared

• the user-declared public contructor of Employee is inherited, because of the using-declaration using Employee::Employee;

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 121

The NVI pattern – Non-Virtual Interface

class Person

{

public:

…

std::string str() const;

Person* clone() const;

…

private:

…

virtual std::string to_str() const;

virtual Person* make_clone() const = 0;

};

– public str() and clone() are declared non-virtual

– implemented by call-through to a corresponding private virtual function to_str() and make_clone(), respectively

– subclasses override to_str() and make_clone()

The Non-Virtual Interface pattern eliminates the problem that a public virtual function really do two things:

• specifies interface

• specifies implementation – namely internal customizable behaviour

NVI keeps public interface apart from implementation – makes it easier to modify implementation without affecting clients.

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 122

NVI str() and to_str()

• the non-virtual public member str() is inherited by subclasses

std::string Person::str() const

{

return to_str(); // explicitly this->to_str()

}

– a call to str() will be bound statically

– a call to to_str() will be bound dynamically

– the type of the this pointer reflects the type of the object that have called the function

• definition of to_str() for Person

string Person::to_str() const

{

return name_ + ' ' + crn_.str();

}

– to be overridden by subclasses, might be used by subclass implementation

Note: It is allowed to override a virtual function, even if it is declared private in the base class.

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 123

NVI clone() and make_clone()

Person* Person::clone() const

{

Person* p = make_clone(); // explicitly: this->make_clone()

// assert will fail if the copy *p doesn’t have same type as the original, *this

assert(typeid(*p) == typeid(*this) && "make_clone() incorrectly overridden");

return p;

}

• the non-virtual public member clone() is inherited by subclasses

– the string literal "make_clone() incorrectly overridden" is converted to true in this context

– assert will not fail if the copied object (*p) and the original (*this) have same type – true && true is true

– the purpose of the right hand side of && is that this text is to appear in the error message when the actual assertion fails

• make_clone() for Person is pure virtual

virtual Person* make_clone() const = 0;

– every concrete subclass must override make_clone()

– the assert will check this, but unfortunately not until runtime

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 124

Initialization and destruction of objects of derived type

• an object of derived type is made up of parts, subobjects.

– base class subobjects and the data members of the class in question

– the “most derived type”

• initialization order is top-down (and left-to-right if multiple inheritance)

– base class subobjects are initialized before subclass subobjects

– the first constructor to be called is that of the most derived class

– direct base class constructors are called recursively

– data members are initialized in the same order as they are declared within the class

• destruction order is reverse to initialization order – bottom-up (and right-to-left if multiple inheritance)

– data members are destroyed in the reverse order to how they are declared within the class

– direct base class destructors are then called, recursively

• if virtual inheritance

– all virtual base class subobjects are initialized first of all – top-down, left-to-right

– the non-virtual subobjects are initialized/destroyed as described above

– all virtual base class objects are destroyed last of all – bottom-up, right-to-left

• important that the top-most polymorphic base class have a virtual destructor

Person* p = new Consultant{ … };

…

delete p; // ~Person() or ~Consultant() ?

Person

Employee

Manager

Person

Employee

Consultant

Person

Employee

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 125

Using Person-Employee-Manager-Consultant

Person* pp; // can point to an Employee or a Manager or a Consultant object

Employee* pe; // can point to an Employee or a Manager or a Consultant object

Manager* pm; // can only point to an Manager object (since no subclasses to Manager)

Consultant* pc; // can only point to a Consultant object (ditto)

pm = new Manager{ name, crn, date, employment_nbr, salary, 17 };

pp = pm; // upcast is automatic – Manager* -> Person*

pm = dynamic_cast<Manager*>(pp); // downcast must be explicit – Person* -> Manager*

if (pm != nullptr)//do we have a Manager?

{

pm->print_department_list(cout);

}

• polymorphic pointers – can point to objects of the pointee type and subtypes

•upcast is an automatic and safe type conversion

•downcast must be explicit and possibly checked before use

– print_department_list() is specific for Manager and can only be invoked using a pointer of type Manager* (or reference Manager&)

• the object is not affected – once a Manager is always a Manager

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 126

Dynamic type check and dynamic type conversion

• sometimes you need to find out type information for a polymorphic object during execution

– what kind of object does a polymorphic pointer point to?

– what kind of object does a polymorphic reference refer to?

• sometimes you need to do dynamic type conversion, e.g.

– if a subclass have a member function which is not inherited, as e.g. Manager::print_department_list()

–and an object of the subclass is referred by a base class pointer or a base class reference

–and you want to call the member function

•typeid expressions can be used to

– check if an object have a specific type

– check the type of an expression

– can be applied to all types

– include <typeinfo>

•dynamic_cast can be used

– only for polymorphic types – require the type information such objects keep

– to check if an object have a specific type or is a subtype to some type

– to convert a polymorphic pointer or a polymorphic reference

•static_cast is possible to use also when converting polymorphic pointers and references, but without dynamic type checks

– you need to be absolutely sure it’s correct to do

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 127

Dynamic type control using typeid expressions

One way to find out the type of an object is to use typeid

if (typeid(*p) == typeid(Manager)) …

• can be used for type names, all kind of objects, and all kind of expressions

•atypeid expression returns a type_info object (a class type)

• type checking is done by comparing two type_info objects

typeid expressions:

typeid(*p) // p is a pointer to an object of some type

typeid(r) // r is a reference to an object of some type

typeid(T) // T is a type

typeid(p) // is usually a mistake if p is a pointer

type_info operations:

== check if two type_info objects are equal –typeid(*p) == typeid(T)

!= check if two type_info objects are not equal –typeid(*p) != typeid(T)

name() returns the type name as a string – may be an internal name used by the compiler, a “mangled name”

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 128

Dynamic type conversion using dynamic_cast

dynamic_cast can be used to type convert polymorphic pointers and references.

dynamic_cast<T*>(p) // convert p to “pointer to T”

dynamic_cast<T&>(r) // convert r till “reference to T”

• typically used to “downcast”

– from a base type pointer to subtype pointer

– from base type reference to subtype reference

• if conversion fails

– in the pointer case, 0 is returned

– in the reference case, exception bad_cast is thrown

•“upcast” is automatic and safe

• in case of multiple inheritance “crosscast” can be of interest

class Derived : public Base, public Interface { … };

Base* pb{ new Derived };

Interface* pi = dynamic_cast<Interface*>(pb);

if (pi != nullptr) ...

Base

Derived

Interface

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 129

Virtual base classes – class lattice – subobject lattice

class B {

public:

int i;

static int s;

enum { e };

};

class X : virtual public B { … };

class Y : virtual public B { … };

class Z : public B { … };

class A : public X, public Y, public Z { … };

void F(A* p)

{

p->i++; // Ambiguous: two i in A

p->X::i++ // OK: qualification specifies

p->s++; // OK: only one s (static)

p->s = p->e // OK: only one e (enumerator)

}

XYZ

virtual virtual

XYZ

class lattice:

subobject lattice:

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 130

Initialization and destruction of derived class objects with virtual base classes

When an object of type A is created the following takes place.

• first the constructor for the most derived class – A – is called

– constructors for all virtual subobjects are called top-down, left-to-right (B1)

– a member initializer for B is required in A, unless default initialized

• then the direct non-virtual base subobjects to A are constructed in declaration

order – X,Y,Z – recursively

– any non-virtual base subobjects are constructed

– any non-static data member subobjects are constructed in declaration order

– the constructor body is executed

Initialization order: B1 –> X –> Y –> B2 –> Z –> A

• an object comes into existence first after its constructor body has succeded

– if construction fails, already constructed subobjects are destroyed in reverse

construction order

– the subobject that construction failed for never existed

• all non-abstract classes in a class lattice must have initializers for virtual base

classes, unless virtual bases have default construction

– initializers for virtual bases are ignored in all constructors except in the

constructor for the most derived class

X,Y and A (if non-abstract) must all have an member initializer for B, or rely on a default constructor.

XYZ

subobject lattice:

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 131

An example of real use of virtual base classes

The standard stream classes:

basic_ios

basic_istringstream

basic_iostream

basic_fstream basic_ofstreambasic_ifstream basic_stringstream basic_ostringstream

ios_base

basic_ostream

basic_istream

virtual

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 132

Comments on derived class design

• prevent subclassing by marking a class final

• make compiler check overridings by marking virtual function declarations override

• prevent further overriding by marking a virtual function final

• make a base class destructor

–public and virtual, if deletion through a base class pointer should be allowed (typically for polymorphic types)

–protected and non-virtual otherwise, if class is abstract

– a compiler generated destructor is public and non-virtual (unless there is a base class having a virtual destructor)

– if a base class has a virtual destructor, generated subclass destructors will also be virtual

•default and delete special member functions properly

– if the copy/move constructors are desired and can be generated – default with proper access (public,protected)

– if copying is not allowed, delete the copy constructor – the move constructor is not generated

– if the copy constructor is declared but the move constructor is not desired – do not delete the move constructor!

– an explicitly deleted member function will implicitly be private – compile error if chosen in overload resolution

– analogous for copy assignment and move assignment operators

• avoid calling virtual functions in constructors and destructors

– virtual functions don’t behave virtual in constructors and destructors

– a Manager object have dynamic type Person when the Person constructor/destructor is executing

– use som “post-construction” technique if virtual dispatch into a derived class is needed from a base constructor

TDDD38 APiC++ Derived Classes, Inheritance, Polymorphism and RTTI 133

Comments on derived class design, cont.

• avoid slicing

– slicing is automatic, invisible and likely to create problems

– typically occur when a function has a value parameter of base type (& forgotten?)

– to allow for explicit slicing the copy constructor can be declared explicit, to avoid unexpected use

explicit C::C(const C);

• consider a virtual copy function for copying polymorphic types – clone()

– prevents slicing

– other ways to copy should be restricted to internal use only – make copy/move constructors protected, e.g.

• consider making virtual functions non-public and public functions non-virtual

– separates the public interface from the customization interface – the NVI pattern

– especially interesting for base classes with a high cost of change (libraries, frameworks, etc.)

• consider containment instead of inheritance

– prefer containment if no real gain using derivation

TDDD38 APiC++ Namespaces 147

Namespaces

namespace Outer

{

int i;

namespace Inner // nested namespace

{

void f() { ++i; } // Outer::i

int i;

void g() { ++i; } // Inner::i

}

• a namespace is an optionally-named declarative region – can be unnamed

– the entities declared in a namespace are called the namespace’s members

• the name of a namespace can be used to access entities declared in that namespace

Outer::i

• a namespace can be split over several parts of one or more translation units

– members can be added successively

– one can add members to the standard namespace std

•anamespace alias declares an alternative name for a namespace, typically a shorthand

namespace A_Very_Long_Namespace_Name { … }

namespace AVLNN = A_Very_Long_Namespace_Name;

TDDD38 APiC++ Namespaces 148

Namespace member definitions

The original namespace definition (e.g. in a header file)

namespace N

{

class C

{

void memfun();

};

}

• members can be added later (e.g. in an accompanying implementation file) in two ways

–extension namespace definition

namespace N

{

void C::memfun() { … }

}

–explicit qualification

void N::C::memfun() { … }

TDDD38 APiC++ Namespaces 149

Using directive

• a using directive specifies that the names in the nominated namespace can be used in the scope in which the using directive appears

#include <iosfwd>

#include <string>

…

using namespace std; // from here names in std can be used without the prefix std::

• a using directive does not add any members to the declarative region in which it appears

• the using directive is transitive

namespace N { int i; }

namespace M

{

int i;

using namespace N;

}

void f()

{

using namespace M;

i = 17; // error: both N::i and M::i are visible

}

TDDD38 APiC++ Namespaces 150

Using declaration

•ausing-declaration introduces a name in the declarative region in which it appears

using N::x;

–xis an alias (synonym) for the name of some entity declared elsewhere, in this case in the namespace N

TDDD38 APiC++ Namespaces 151

Unnamed namespaces

An unnamed namespace definition such as

namespace

{

int i{ 4711 };

}

Behaves as if it was replaced by

namespace unique { } // empty body

using namespace unique;

namespace unique

{

int i{ 4711 };

}

where all occurrences of unique are replaced by the same identifier and this identifier differs from all other identifiers in the entire program

• members of an anonymous namespace is only accessible in the file in question

• the use of the static keyword for that purpose is deprecated

TDDD38 APiC++ Namespaces 152

Inline namespaces

namespace Outer

{

inline namespace Inner

{

int fun(bool) { return 1; }

}

int fun(int) { return 2; }

}

int main()

{

return Outer::fun(true);

}

• when an inline namespace is defined, a using directive is implicitly inserted into its enclosing namespace

– without inline, 2 will be printed

– with inline, 1 will be printed

• an unnamed namespace can be declared as an inline namespace

Version handling, e.g., can be managed with inline namespaces (one for each version) in combination with conditional compilation.

TDDD38 APiC++ Namespaces 153

The Interface Principle and Argument Dependent Lookup (ADL)

The Interface Principle:

For a class type X, all functions (including non-member functions) that both “mention” X and are “supplied with” X

in the same namespace are logically part of X, because they form part of X’s interface.

• C++ is explicitly designed to enforce the Interface Principle by argument-dependent lookup (ADL)

• ADL ensures that code that uses an object x of type X can use its nonmember function interface, e.g.

cout << x;

which invokes the nonmember operator<< for X, as easily as it can use member functions, e.g.

x.fun();

which needs no special lookup, since f is clearly to be looked up in the scope of X.

TDDD38 APiC++ Namespaces 154

Namespace recommendations

• keep a type and its nonmember function interface in the same namespace – The Interface Principle

– otherwise nonmember functions may not be called correctly

• keep types and functions in separate namespaces unless they are specifically intended to work together

– the C++ standard library puts everything in the same namespace…

• don’t write namespace using directives in header files or before #include

– using directives is for your convenience – don’t inflict with others

TDDD38 APiC++ Preprocessor 155

Preprocessor

Source code is preprocessed before the actual compilation begins.

• source file inclusion

#include <iosfwd>

#include "Hash.h"

• simple macros – prefer const and/or constexpr instead

#define MAX 1000

constexpr int max{ 1000 }; // implicitly const

• function macros

#define Square(x) ((x)*(x))

– textual substitution – x is evaluated twice

int a{ 2 };

cout << Square(++a) << endl; // 12

– prefer inline functions (or non-inline and rely on the compiler…)

template<typename T> inline T square(const T& x) { return x*x; }

cout << square(++a) << endl; // 9

TDDD38 APiC++ Preprocessor 156

• conditional compilation

– inclusion guards in header files – very important

#ifndef ZOO_H

#define ZOO_H

…

#endif

– conditional inclusion

#if VERSION == 1

inline namespace Version_1 { … }

#elif VERSION == 2

inline namespace Version_2 { … }

#elif …

…

#endif

– large “comments” – creates no conflict with ordinary C++ comments within

#if 0

#endif

TDDD38 APiC++ Preprocessor 157

• trace output, the # operator

#if DEBUG

#define TRACE(s) cerr << #s << " = " << (s) << endl;

#else

#define TRACE(s)

#endif

– compile with option -DDEBUG to activate TRACE

int i{ 4711 };

TRACE(i+1) // Output: i+1 = 4712

• and some more …

TDDD38 APiC++ Templates 158

Templates

• a template can be either a class or a function

–aclass template defines a family of classes

–afunction template defines a family of functions

•object-oriented construct

– static polymorphism, a.k.a. compile-time polymorphism

• powerful and useful in many ways

– traditional generic data structure design – element type parameterization

– an alternative to function overloading – can also be combined with function overloading

– policy design – parametrizing e.g. storage policy, ordering policy, etc., for containers

– template meta programming – compile time type classification, type property inspection, type translation, code selection, …

• pre-runtime

– static type checking

– highly optimizable

– flexibility combined with safety and efficiency

• we will on the way see

– programming techniques related to template programming

– use of rvalue references, move semantics, perfect forwarding – all very important features of C++

– core language features used in connection with templates – auto,decltype,noexcept,constexpr

– examples of standard library components

TDDD38 APiC++ Templates 159

Function templates

template<typename T>

const T& max(const T& x, const T& y)

{

return x < y ? y : x;

}

•template parameter list – a comma separated list of template parameters within angle brackets

template< template parameters >

•template type parameter – two alternatives, no semantic difference

typename T class T

• other kind of template parameters – non-type parameter, template template parameter,template parameter pack,...

• note – max is designed and implemented with care

– the only requirement on T is operator<

– there should also be an overloading with a second template parameter for a comparison predicate

– pass by reference – T need not be copyable

– pass by reference to const – in semantics enforced and arguments can be constants or literals

• be aware of special cases

– wrong semantics if T is, e.g., a pointer type

TDDD38 APiC++ Templates 160

Function template instantiation

•template instantiation – the act of instantiating a template

int a{ 1 };

int b{ 2 };

int c = max(a, b); // name lookup…

• if no other, better candidate is found by name look up

– the function call will create an int instance for our template max ()

– such an instance is an implicit specialization for int

– template argument for T is deduced from the type of the function call arguments, i.e. the type(s) for a and b

– x and y have the same template type T – a and b must have same type (int)

– no implicit type conversion of arguments is allowed in this context

•explicit instantiation is a declaration using the keyword template only in front of a declaration or definition

template const int& std::max<int>(const int&, const int&);

– this will force the compiler to create one instance for the entire program

– used to make, e.g., compilation more efficient

– this is not an explicit specialization (next slide)

• how instances are managed is implementation dependent

– the standard does not specify

TDDD38 APiC++ Templates 161

Explicit function template specialization (1)

• the original declaration of a template is called primary template

template<typename T> const T& max(const T& x, const T& y) { … }

– the name for a primary is a simple identifier – max

•anexplicit specialization is typically defined to handle a special case, e.g.

– when the template primary does not work for a specific type

– when a more efficient solution can be found for a specific type

• an explicit specialization is introduced by template<…>

template<> max<const char*>(const char*&, const char*&) { … }

– specialization for const char*

– the name is a template-id – max<const char*>

– is a full specialization if no template parameters are declared – template<>

– otherwise it’s a partial specialization (examples will follow)

• a primary and its specializations are separate definitions

– no code sharing

TDDD38 APiC++ Templates 162

Explicit function template specialization (2)

•anexplicit specialization for std::max for const char* would be

template<> const char*& max<const char*&>(const char*& x, const char*& y)

{

return (strcmp(x, y) < 0) ? y : x;

}

– T is replaced with char* (& must remain)

• don’t specialize a function template unless needed

– specializations never participate in overload resolution

– but, an existing specialization will be used, if its primary is chosen by overload resolution

• prefer to overload with an ordinary function

const char* max(const char* x, const char* y)

{

return (strcmp(x, y) < 0) ? y : x;

}

– obviously no point in specializing in this case

– this function will participate in overload resolution, and will be chosen before any template is considered

TDDD38 APiC++ Templates 163

Function templates and overload resolution

Function templates can be overloaded with both template functions and normal functions.

Overload resolution basically goes through the following steps to find a function to match a call:

1. if there is a normal function that exactly matches the call, that function is selected, else

2. if a function template can be instantiated to exactly match the call, that specialization is selected, else

3. if type conversion can be applied to the arguments, allowing a normal function to be used as a unique best match,

that function is selected, else

4. overload resolution fails – either no function matches the call, or the call is ambiguous

template<typename T> const T& max(const T& x, const T& y);

int a, b;

double x, y;

…

a = max(a, b); // OK, a and b have same type, int

x = max(x, y); // OK, x and y have same type, double

x = max(a, x); // ERROR, a and x has different types

x = max<double>(a, x); // explicit instantiation allows for implicit type conversion, ais converted to double

TDDD38 APiC++ Templates 164

Non-type template parameters

template<typename T, std::size_t N>

T* begin(T (&a)[N])

{

return a;

}

template<typename T, std::size_t N>

T* end(T (&a)[N])

{

return a + N;

}

int a[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // type is int[9]

for (auto it = begin(a), it != end(a); ++it)

cout << *it << endl;

• N is a non-type template parameter

– acts as a constant within the template

– the dimension of the array will be deduced from the function call argument

• it is recommended to pass arrays to functions by reference, instead as by pointer

Examples taken from the standard library, range access.

TDDD38 APiC++ Templates 165

Function templates, auto and decltype

template<class Container>

auto begin(Container& c) -> decltype(c.begin()) // also for const Container&

{

return c.begin();

}

template<class Container>

auto end(Container& c) -> decltype(c.end())) // also for const Container&

{

return c.end();

}

vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

for (auto it = begin(v), it != end(v); ++it)

cout << *it << endl;

• return type is not possible to determine from the template parameter

– the actual type for Container must be known, and then what the member functions begin() and end() returns

•decltype is an unevaluated context – c.begin() and c.end() are not invoked

• In C++14 auto will be sufficient in cases where the return type can be deduced from the code in the body (as in these examples)

Note: This syntax is a reminiscent of the lambda syntax – [capture] ( parameter-list ) -> return-type { statements }

TDDD38 APiC++ Templates 166

Class templates

template<class T1, class T2> struct pair

{

typedef T1 first_type;

typedef T2 second_type;

T1 first;

T2 second;

pair(const pair&) = default;

pair(pair&&) = default;

constexpr pair() : first(), second() {}

pair(const T1& x, const T2& y) : first(x), second(y) {}

// more constructors

pair& operator=(const pair& p);

pair& operator=(pair&& p);

// more assignment operators

void swap(pair& p)

noexcept(noexcept(swap(first, p.first)) && noexcept(swap(second, p.second))) { … }

};

template<class T1, class T2>

void

swap(pair<T1, T2>& x, pair<T1, T2>& y) noexcept(noexcept(x.swap(y))) { x.swap(y); }

TDDD38 APiC++ Templates 167

Comments on std::pair

pair<int, string> p{ 4711, "Eau de Cologne" };

pair<int, string>::first_type x = p.first;

• two template type parameters,T1 and T2

•member types first_type and second_type

–T1 and T2 – but with better names – are made available to code using pair

– common practice for class templates

• data members first and second

– direct access causes no problem – public

•pair means pair<T1, T2>, when used within the template

•constexpr pair() means that a call to the constructor is a constant expression

– can be evaluated during compile time

– default initialized pair objects can be used in static contexts

• the noexcept specification for member swap specifies that it will not throw

–if swapping T1 objects will not throw, and

–if swapping T2 objects will not throw

• the noexcept specification for non-member swap specifies that it’s no-throw, if member swap is no-throw

Note: noexcept is an operator – noexcept(expression )

TDDD38 APiC++ Templates 168

Helper function make_pair()

template<class T1, class T2>

pair<T1, T2>

make_pair(T1&& x, T2&& y)

{

return pair<T1, T2>(std::forward(x), std::forward(y));

}

auto p = make_pair(4711, string{"Eau de Cologne"}); // pair<int, string>

• common practice to have a helper function to create an instances of a class template for given arguments

– creating a pair object becomes easy

– the types of the template arguments T1 and T2 are deduced from the given call arguments

– reference collapsing is applied to T1&& and T2&& (more about that later)

•std::forward() is a utility function for perfect forwarding

– makes it work as if the call to the pair constructor was made in the client code

– preserves the actual type category of the arguments – lvalue or rvalue

• if the first argument is an lvalue of type L and the second argument is an rvalue of type R, the signature will effectively be

pair<L, R> make_pair(L& x, R&& y);

– why cannot std::move() be used in this context?

TDDD38 APiC++ Templates 169

Class template instantiation and specialization

•implicit instantiation occurs when the context requires an instance of a class template

– class template arguments are never deduced, but default arguments can be used

template<class T, class Allocator = allocator<T>> class vector;

vector<int> v; // definition of v require instance of std::vector for int

– class template member functions are instantiated when called

v.push_back(x);

•anexplicit instantiation is a declaration using the keyword template

template class vector<int>;

• a class template specialization is introduced by template<…> – the name is a template-id

template<typename Allocator> class vector<bool, Allocator> { … };

– specialization for vector<bool>

– this is a partial specialization, since there is (at least) one template parameter left (Allocator)

–afull specialization is introduced by template<>

template<> class vector<bool, std::allocator<bool>> { … };

– primary and specialization have separate definitions – no code sharing

TDDD38 APiC++ Templates 170

Default template parameter arguments

template<typename T = int,//for demonstration only

typename U = std::allocator<T>,

template<typename = T, typename = U> class Container = std::vector>

ostream& operator<<(ostream& os, const Container<T, U>& c);

template<size_t N = 32> bitset;

– Note: only std::allocator<T> is in practice realistic to have as a default argument

• if all template parameters have a default argument, the template argument list can be empty

template<typename T = int>class X { … };

X<> x1; // OK, same as X<int>

X x2; // Syntax error

• ambiguity between a type identifier (type-id) and an expression is resolved to a type identifier

template<typename T> void fun(); // function template with a type parameter

template<int I> void fun(); // function template with a non-type parameter

void g() { fun<int()>(); } // int() is resolved as a type-id – first fun() is called

– what type?

TDDD38 APiC++ Templates 171

Separate definitions for members of a class template

template<typename T>

struct S

{

T t_{ T() }; // non-static data member definition

T get_t(); // non-static member function declaration

static T c_; // static data member declaration

static T get_c(); // static member function declaration

};

template<typename T> // non-static member function definition

T S<T>::get_t() { return t_; }

template<typename T> // static data member definition

T S<T>::c_{ T() };

template<typename T> // static member function definition

T S<T>::get_c() { return c_; }

•instantiation argument used in qualified names – S<T>::name

• expression T() to initialize data members of a generic type T

TDDD38 APiC++ Templates 172

Variadic templates

•atemplate parameter pack is a template parameter that accepts zero or more template arguments.

template<class... Types>

class tuple { … };

– Types is a template parameter pack

tuple<> t0; // Types contains no arguments

tuple<int> t1{ 17 }; // Types contains one arguments, int

tuple<int,double> t2{ 17, 3.14 }; // Types contains two arguments, int and double

•afunction parameter pack is a function parameter that accepts zero or more arguments

template<class... Types>

void fun(Types... args); // function parameter pack

–args is a function parameter pack

fun(); // args contains no arguments

fun(1); // args contains one argument, type int

fun(2, 3.14); // args contains two arguments, type int and double

TDDD38 APiC++ Templates 173

Variadic print function

template<typename T> void print(const &T x)

{

cout << x;

}

template<typename First, typename... Rest>

void print(First first, Rest... rest) // Rest is expanded

{

cout << first << ’ ’;

print(rest...); // rest is expanded

}

•Rest is a template parameter pack

•rest is a function parameter pack

•rest... is a pack expansion – consists of a pattern and an ellipsis – rest is the pattern

– beside expanding, the only thing one can do with a parameter pack is to take its size with sizeof...

print(); // error: no function matches call print()

print(17); // 17

print(17, "Hello"); // 17 Hello

print(17, "Hello", 3.14); // 17 Hello 3.14

print(17, "Hello", 3.14, ’X’); // 17 Hello 3.14 X

TDDD38 APiC++ Templates 174

Variadic emplace functions

• the purpose is to avoid copies – for example when inserting into a container and we have suitable constructor arguments at hand

• pass constructor arguments instead of ready-made objects – by rvalue reference or by lvalue reference

• objects are created in-place by a matching constructor – move or copy

template<typename T> class Container

{

public:

void insert(const T& x) { … }

template<typename... Args>

void emplace(Args&&... args) { construct(&storage_, std::forward<Args>(args)...); }

private:

template<typename... Args>

void construct(T* p, Args&&... args) { new(p) T{ std::forward<Args>(args)... }; }

T storage_; // very, very simplified storage…

};

Container<pair<int, string>> c;

string s{ "foobar" };

c.emplace(4711, s); // note: first argument is an rvalue, second is an lvalue

c.insert(make_pair(4711, s)); // this is what we avoided, first creating a pair and then insert it

TDDD38 APiC++ Templates 175

Template parameter overview (1)

•template type parameter (typename or class)

template<typename T> class X;

– actual T can be any type (fulfilling the requirements the implementation of X puts on T)

•template non-type parameter – shall have one of the following types:

–integral or enumeration type

template<int n, Colour c> …

–pointer to object, or to function

template<double* p, void (*pf)()> …

–lvalue reference to object or to function

template<X& r, void (&rf)()> …

–pointer to data member, or member function

template<int X::*pm, void (X::*pmf)()> …

–std::nullptr_t – hard to find examples…

TDDD38 APiC++ Templates 176

Template parameter overview (2)

•template template parameter

template<typename T, typename U, template<typename,typename>class Container>

ostream& operator<<(ostream& os, const Container<T, U>& c)

{

copy(begin(c), end(c), ostream_iterator<T>(os, " "));

return os;

}

vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

cout << v << endl;

–Container can be instantiated by any class type having two type parameters

template<typename,typename>class Container;

–vector, and all other sequence containers, except array, have two template type parameters

template <class T, class Allocator = allocator<T>> vector;

– default arguments for template parameters are not considered in this context

TDDD38 APiC++ Templates 177

Template parameter overview (3)

•template type parameter pack

template<typename... Types> class tuple;

–tuple can be instantiated with zero or more type arguments

tuple<int, string, double> fragrance{ 4711, "Eau de Cologne", 39.39 };

– the sizeof... operator yields the number of arguments provided for a parameter pack

static const std::size_t number = sizeof...(Types);

•template non-type parameter pack

template<typename T, int... Dims> class Multi_Array;

–Multi_Array can be instantiated with a type and zero or more int values

Multi_Array<string, 3, 4> m34;

TDDD38 APiC++ Templates 178

Template parameter overview (4)

• a template parameter (T) can be used in declaration of subsequent template parameters and their default arguments

template<class T, T* p, class U = T> class X;

• a template parameter of type array of T is adjusted to pointer to T by the compiler

template<int a[10]> is adjusted to template<int* a>

– as for an ordinary function parameter of array type

• a template parameter of type function is adjusted to pointer to function by the compiler

template<int f()> is adjusted to template<int (*f)()>

– as for an ordinary function parameter of function type

The two, in practice, dominant kinds of template parameters are

•type parameters

•integral non-type parameters

TDDD38 APiC++ Templates 179

Type equivalence

Two template identifiers refer to the same class or function, if their

• names are identical

• type arguments are the same types

• non-type arguments of integral or enumeration type have identical values

• non-type arguments of pointer or reference type points/refer to the same object or function

• template arguments refer to the same template

template<typename T, T t, T* p, template<typename>class C> class X;

template<typename T> class Y;

template<typename T> class Z;

int a;

int b;

X<int, 100, &a, Y> x1;

X<int, 2*50, &a, Y> x2; // x1 and x2 have same type

X<int, 10, &b, Z> x3; // x3 have not same type as x1 and x2

TDDD38 APiC++ Templates 180

Member templates

template<class T1, class T2>

struct pair

{

…

template<class U, class V> pair(U&& x, V&& y);

…

};

• a class template or function template can be declared as member of a class

– such a template is called a member template

– a member function template cannot be virtual and never override a virtual function

– allowing for type conversions is one use – if U is convertible to T1, and V is convertible to T2, the constructor above is fine

• copy/move constructors and copy/move assignment operators are not templates

• separate member template declaration syntax

template<class T1, class T1> // class template parameters

template<class U, class V> // member template parameters

pair<T1, T2>::pair(U&& x, V&& y)

: first{ std::forward<U>(x) }, second{ std::forward<V>(y) }

{}

TDDD38 APiC++ Templates 181

Alias templates

The declaration for std::vector is:

template<class T, class Allocator = std::allocator<T>> class vector;

•analias template for vector could be

template<typename T>

using default_alloc_vector = std::vector<T, std::allocator<T>>;

– template version of the alias declaration

– implicit partial instantiation of Allocator

– can be used as

default_alloc_vector<int> v;

– which is the same as

vector<int, std::allocator<int>> v;

•default_alloc_vector can be used as an argument for a template template type parameter with one parameter

template<typename T, template<typename>class C = default_alloc_vector> class X {};

X<int> x;

– vector cannot, since it has two template parameters

TDDD38 APiC++ Templates 182

Dependent names

Inside a template, constructs have semantics which may differ for different instances.

• such constructs depends on the template parameters

• in particular types and expressions may depend on the type and/or the value of template parameters, which are determined by the template

arguments

Some examples:

template <typename T>

struct Derived : public Base<T> // Base<T> depend on T

{

typename T::X* x_ptr; // T::X depend on T

int value = Base<T>::value; // Base<T>::value depend on T

void memfun()

{

typename vector<T>::iterator it; // vector<T>::iterator depend on T

…

}

};

• dependent names are by definition not assumed to name a type, unless qualified by typename

–T::X could be the name of a data member, e.g.

TDDD38 APiC++ Templates 183

SFINAE – Substitution Failure Is Not An Error

Invalid substitution of template parameters is not in itself an error.

When the compiler is deducing the template parameters for a function template from a function call

• if the deduced parameters would make the signature invalid, that function template is not considered for overload resolution

– it does not stop the compilation with a compile error

Example – the std::enable_if template, from <type_traits>

• primary template have no members

template<bool,typename T = void>struct enable_if {};

• partial specialization for true have a member typedef for T , named type

template<typename T> struct enable_if<true, T> { typedef T type; };

• typically used in combination with some type traits component from the standard library

template<typename T>

typename std::enable_if< std::is_pod<T>, void >::type

fun( … )

{

…

}

–if T is not a POD there is no member type and this overload of fun is then discarded – it is not an error

TDDD38 APiC++ Templates 184

SFINAE – example of practical use

• if T is POD, use std::memcpy to copy T objects – efficient byte-by-byte copy

template<typename T>

typename std::enable_if< std::is_pod<T>::value, void >::type

copy(const T* source, T* destination, unsigned count)

{

std::memcpy(destination, source, count * sizeof(T));

}

– if T is POD, std::is_pod<T>::value will be true

–std::enable_if<std::is_pod<T>::value, void>::type will be defined (void), otherwise not (failure)

–if type is defined the overload above will be enabled (and the one below will be disabled)

• if T is non-POD, use object-by-object copy assignment for T

template<typename T>

typename std::enable_if< !std::is_pod<T>::value, void >::type

copy(const T* source, T* destination, unsigned count)

{

for (unsigned i = 0; i < count; ++i)

{

*destination++ = *source++;

}

TDDD38 APiC++ Templates 185

Utility function std::move() (1)

Typically used to allow for move semantics on lvalues – example from the standard library:

template<class T>

void swap(T& x, T& y)

noexcept(is_nothrow_move_constructible<T>::value &&

is_nothrow_move_assignable<T>::value)

{

T tmp{ std::move(x) };

x = std::move(y);

y = std::move(tmp);

}

• x and y are lvalues

• in this context move semantics is appropriate to exchange the values of x and y

• std::move() converts its argument to a nameless rvalue reference (T&&)

– if T have move constructor and move assignment operator they will be used

– if not, the copy constructor and copy assignment operator will be used

• whether or not swap may throw an exception is specified by two type property traits

–value will be true if T objects can be move copied and move assigned without throwing

TDDD38 APiC++ Templates 186

Utility function std::move() (2)

template<typename T>

typename std::remove_reference<T>::type&&

move(T&& t)

{

return static_cast<typename std::remove_reference<T>::type&&>(t);

}

Much to learn from this simple function template…

• move() uses type modifier traits class std::remove_reference:

template<typename T> struct remove_reference { typedef T type; }; // primary

template<typename T> struct remove_reference<T&> { typedef T type; }; // spec 1

template<typename T> struct remove_reference<T&&> { typedef T type; }; // spec 2

– the primary template matches any type – used for non-reference types

– the first specialization matches lvalue references (T&)

– the second specialization matches rvalue references (T&&)

–std::remove_reference<T>::type will always be T

• the return type of move() will always be rvalue reference (T&&)

• the type conversion will effectively be static_cast<T&&>(t)

•std::remove_reference<T>::type is a dependent name – typename required

TDDD38 APiC++ Templates 187

Utility function std::move() (3)

Reference collapsing rules

A& & becomes A& (1)

A& && becomes A& (2)

A&& & becomes A& (3)

A&& && becomes A&& (4)

Special template argument deduction rules for function templates

template<typename T>

void foo(T&& arg); // deduced parameter type – type deduction takes place – && = universal reference

If foo() is called with an

•lvalue of type A, T resolves to A&, and by reference collapsing rule 2 the type of arg effectively becomes A&

•rvalue of type A, T resolves to A and the type of arg becomes A&& (no reference collapsing involved)

So, if std::move() is called with an

•lvalue of type A, T resolves to A& and the parameter type (A& &&) becomes A& – move(A& t)

–spec 1 of std::remove_reference is used – std::remove_reference<A&>

•rvalue of type A, T resolves to A and parameter type becomes A&& – move(A&& t)

–primary of std::remove_reference is used – std::remove_reference<A>

• cast is always to rvalue reference, A&&

Note: Reference collapsing rule 1 has always been in effect since C++98.

TDDD38 APiC++ Templates 188

Perfect forwarding

Rvalue references was also designed to solve the perfect forwarding problem.

template<typename T, typename Arg>

shared_ptr<T> factory(Arg&& arg)

{

return shared_ptr<T>{ new T{ arg } }; // arg is an lvalue (the name rule)

}

• we want this to work as if the argument passed to factory() was passed directly to the T constructor

– lvalue as lvalue

– rvalue as rvalue

• std::forward() does this

template<typename T, typename Arg>

shared_ptr<T> factory(Arg&& arg)

{

return shared_ptr<T>{ new T{ std::forward<Arg>(arg) } };

}

• if factory() is called with an lvalue of type X, Arg resolves to X& and the type for parameter arg will be X& (X& &&)

– forward will be instantiated std::forward<X&>(arg)

• in factory() is called with an rvalue of type X, Arg resolves to X and the type for parameter arg will be X&&

– forward will be instantiated std::forward<X>(arg)

TDDD38 APiC++ Templates 189

Utility function std::forward()

Lvalue version:

template<typename T>

constexpr T&& forward(typename std::remove_reference<T>::type& t)

{

return static_cast<T&&>(t);

}

• T&& effectively becomes T& (template argument deduction rule and reference collapsing rule)

• return type will be T& – conversion will be static_cast<T&> – parameter is always T&

Rvalue version:

template<typename T>

constexpr T&& forward(typename std::remove_reference<T>::type&& t)

{

static_assert(!std::is_lvalue_reference<T>::value,

"template argument substituting T is an lvalue reference type");

return static_cast<T&&>(t);

}

• T&& will be T&& (template argument deduction rule, no reference collapsing involved)

• if instantiated with an lvalue reference type the program is ill-formed – prevent strange things like

std::forward<string&>( string{} ) // string{} creates a prvalue

TDDD38 APiC++ Templates 190

Policy design (1)

Policy design is about letting a feature, a policy, of a type, the host, be a template type parameter.

• Two copy policies for objects of type T:

– deep copy

template<typename T>

struct deep_copy

{

static void copy(T*& destination, T*& source)

{

destination = new T{ *source };

}

};

– destructive copy (move semantics)

template<typename T>

struct destructive_copy

{

static void copy(T*& destination, T*& source)

{

destination = source;

source = nullptr;

}

};

Note: Alternatively the functions could be templates, instead of the policy classes – actually a better choice!

TDDD38 APiC++ Templates 191

Policy design (2)

A smart pointer class with a copy policy – deep_copy as default

template<typename T, template<typename T> class copier = deep_copy>

class smart_ptr : private copier<T>

{

public:

smart_ptr(T* p) : ptr_{ p } {}

~smart_ptr() { delete ptr_; }

smart_ptr(smart_ptr& value) { this->copy(ptr_, value.ptr_); } // this-> required

smart_ptr& operator=(smart_ptr& rhs)

{

T* tmp_ptr;

copier<T>::copy(tmp_ptr, rhs.ptr_); // or, alternatively

delete ptr_;

ptr_ = tmp_ptr;

return *this;

}

…

private:

T* ptr_;

};

Note: Names are not looked up in dependent base classes – call to copy() require qualification of some kind.

TDDD38 APiC++ Templates 192

Policy design (3)

A better alternative, in this case, would be to make member functions templates, instead of policy classes.

struct deep_copy

{

template<typename T>

static void copy(T*& destination, T*& source)

{

destination = new T{ *source };

}

};

struct destructive_copy

{

template<typename T>

static void copy(T*& destination, T*& source)

{

destination = source;

source = nullptr;

}

};

• by this we can take advantage of template function argument deduction

• we will also see some other simplifications and also generalizations

TDDD38 APiC++ Templates 193

Policy design (4)

template<typename T, class copier = deep_copy> // note!

class smart_ptr // note!

{

public:

smart_ptr(T* p) : ptr_{ p }{}

~smart_ptr() { delete ptr_; }

smart_ptr(smart_ptr& value) { copier::copy(ptr_, value.ptr_); } // note!

smart_ptr& operator=(smart_ptr& rhs)

{

T* tmp_ptr;

copier::copy(tmp_ptr, rhs.ptr_); // note!

delete ptr_;

ptr_ = tmp_ptr;

return *this;

}

…

private:

T* ptr_;

};

TDDD38 APiC++ Templates 194

Meta programming and type traits

Meta programming is about programs that create or modifies programs.

• the template instantiation process in C++ can be used as a computational engine – template meta programming

• parametrized types and (compile-time) constants can be used to record state

• template specializations can be used to implement conditions

• C++ is both the metalanguage and the object language

The standard library define components to be used by C++ programs, particularly in templates, to

• support the widest possible range of types

• optimize template code usage

• detect type related user errors

• perform type inference and transformation at compile time

It includes:

• type classification traits

– describe a complete taxonomy of all possible C++ types, and state where in that taxonomy a given type belongs

• type property inspection traits

– allow important characteristics of types or of combinations of types to be inspected

• type transformations

– allow certain properties of types to be manipulated

TDDD38 APiC++ Templates 195

Type classification traits (1)

•unary type traits describes a property of a type

–type categories – is_integral, is_floating_point, is_array, is_pointer, is_class, is_function, is_reference, is_arithmetic, is_fundamental,

is_object, is_scalar, is_compound, is_member_pointer, …

–type properties – is_const, is_polymorphic, is_abstract, is_signed, is_copy_constructible, has_virtual_destructor, …

–type property queries – alignment_of, …

•binary type traits describes a relationship between two types

– is_same, is_base_of, is_convertible

•transformation traits modifies a property of a type

– const-volatile modifications – e.g. remove_const, remove_cv, add_volatile

– reference modifications – remove_reference, add_rlvalue_reference, add_rvalue_reference

– sign modifications – make_signed, make_unsigned

– array modifications – remove_extent, remove_all_extent

– pointer modifications – remove_pointer, add_pointer

– other transformations – …

(There is about 90 type traits in C++11).

TDDD38 APiC++ Templates 196

Type classification traits (2)

• class template integral_constant is the common base class for all value-based type traits.

template<typename T, T v>

struct integral_constant

{

static constexpr T value{ v }; // declaration and initialization

using value_type = T;

using type = integral_constant<T, v>; // the type itself

constexpr operator value_type() { return value; }

};

template<typename T, T v>

constexpr T integral_constant<T, v>::value; // definition for value

•true_type and false_type are provided for convenience – most value traits are Boolean properties and will inherit from these

using true_type = integral_constant<bool,true>;

using false_type = integral_constant<bool,false>;

•is_array as an example

template<typename>struct is_array : public false_type {}; // primary

template<typename T, std::size_t Size> struct is_array<T[Size]> : public true_type {};

template<typename T> struct is_array<T[]> : public true_type {};

TDDD38 APiC++ Templates 197

Type classification traits (3)

Examples of some simple type traits.

template<typename>struct is_const : public false_type {};

template<typename T> struct is_const<T const> : public true_type {};

template<typename T> struct remove_const { typedef T type; };

template<typename T> struct remove_const<T const> { typedef T type; };

template<typename T> struct add_const { typedef T const type; };

template<typename,typename>struct is_same : public false_type {};

template<typename T> struct is_same<T, T> : public true_type {};

template<typename T> struct is_arithmetic

:public integral_constant<bool, (is_integral<T>::value || is_floating_point<T>::value)> {};

template<typename T> struct is_object

:public integral_constant<bool, !(is_function<T>::value

|| is_reference<T>::value

|| is_void<T>::value)> {};

TDDD38 APiC++ Templates 198

Example: Dispatching constructor

Example from the containers library – wrong constructor can be chosen…

template <typename T> class Container {

…

Container(size_t n, const T& value) : size_(n), data_(allocate(size_))

{ std::fill_n(begin(), n, value); }

template <typename InputIterator>

Container(InputIterator first, InputIterator last) {

typedef typename std::is_integral<InputIterator>::type Integral; // check type category

initialize_dispatch(first, last, Integral()); // dispatch accordingly

}

template <typename Integer> // corresponds to the first constructor

void initialize_dispatch(Integer n, Integer value, std::true_type)

{ std::fill_n(begin(), n, value); }

template <typename InputIterator> // corresponds to the second constructor

void initialize_dispatch(InputIterator first, InputIterator last, std::false_type)

{ std::copy(first, last, begin()); } // memory must be allocated first!

};

•size_t is an unsigned integer type

•if T is, e.g. int, an instance of the template constructor (aimed for iterators!) is a better match than the first constructor

• check what type category InputIterator in the second constructor belongs to and dispatch to the corresponding helper function

TDDD38 APiC++ Templates 199

Example: Select the most efficient implementation of several possible (1)

The standard library divide iterators into different categories – one important issue is how they can be moved:

•anInputIterator can be moved forward one element at the time with ++

•aBidirectionalIterator can be moved forward one element at the time with ++ and backward one element at the time with --

•aRandomAccessIterator can be moved also by pointer arithmetics, i.e., also by using +,+=,-, and -=

advance() is a utility function to move an iterator a specified number of steps – advance(it, n)

• for an InputIterator n must be non-negative and the advancement is done by repeating ++it n times

• for a BidirectionalIterator advancement is done by repeating ++it n times, if n >= 0, and repeating --it n times, if n < 0

• for a RandomAccessIterator advancement can be done with it += n (n can be negative)

• advance() is implemented to select the most efficient way to advance an iterator, depending on which category it belongs to

template <typename InputIterator, typename Distance>

inline void advance(InputIterator& i, Distance n)

{

typename iterator_traits<InputIterator>::difference_type d = n;

advance_dispatch(i, d, typename iterator_traits<InputIterator>::iterator_category());

}

– the name InputIterator is used to specify the minimum requirements for the iterator

– Distance could be any relevant type – d is used to convert n to the correct difference type for the iterator in question

– iterator_traits<InputIterator>::iterator_category gives the category type for InputIterator, e.g. random_access_iterator_tag

– iterator_traits<InputIterator>::iterator_category() creates an object of that type – used to dispatch to a suitable overloading of

advance_dispatch()

TDDD38 APiC++ Templates 200

Example: Select the most efficient implementation of several possible (2)

• the basic requirement is that the given iterator must fulfill the requirements of InputIterator, and n >= 0 – dispatch to

template <typename InputIterator, typename Distance>

void advance_dispatch(InputIterator& i, Distance n, input_iterator_tag)

{

while (n--) ++i;

}

• if the given iterator is a BidirectionalIterator, n is allowed to be negative – dispatch to

template <typename BidirectionalIterator, typename Distance>

void advance_dispatch(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag)

{

if (n > 0)

while (n--) ++i;

else

while (n++) --i;

}

• if the given iterator is a RandomAccessIterator the iterator can be advanced in a more efficient way – dispatch to

template <typename RandomAccessIterator, typename Distance>

void advance_dispatch(RandomAccessIterator& i, Distance n, random_access_iterator_tag)

{

i += n;

}

TDDD38 APiC++ Templates 201

Example: Constraints check (1)

Suppose a class template C require a template type T to have a member function clone().

template<typename T> // T must have member function T* clone() const;

class C

{

…

private:

template <T* (T::*)() const>struct _check_Cloneable {};

using _check_Cloneable_t = _check_Cloneable<&T::clone>;

…

};

•_check_Cloneable is a utility template class

– a type definition is a static entity

–_check_Cloneable is a primary with one member function pointer parameter (name left out)

•_check_Cloneable_t is declared to be a name for the specialization _check_Cloneable<&T::clone>

– an alias declaration is a static entity

–T::clone is looked up in T and checked statically – this is what we actually want to do!

– if no such member function this will fail and generate a compile error

Note, leading underscores are used to emphasise internal use (typical compiler convention)

TDDD38 APiC++ Templates 202

Example: Constraints check (2)

As an alternative, define a concept class for checking cloneability.

template<typename T>

struct _Cloneable

{

void __constraints() { T* (T::*test)() const = &T::clone; }

};

template<typename T>

class C

{

…

private:

using __func = void (_Cloneable<T>::*)(); // simplifies the next declaration

template<__func> struct _check_Cloneable {};

using _check_Cloneable_t = _check_Cloneable<&_Cloneable<T>::__constraints>;

…

};

• becomes more general

–_Cloneable can be replaced by any concept class having member function __constraints()

–__constraints() can have several checks

– now we just have to find a way to simplify generating these declarations to check a concept

TDDD38 APiC++ Templates 203

Example: Constraints check (3)

(The simplification becomes a bit complicated though…)

• a preprocessor function macro can be used to create the declarations to check a concept _concept for a type _type

#define CLASS_REQUIRES(_type, _concept) \

using __func_##_type##_concept = void (_concept<_type>::*)(); \

template <__func_##_type##_concept> struct _check_##_type##_concept {}; \

using _check_typedef_##_type##_concept = \

_check_##_type##_concept<&_concept<_type>::__constraints>

• simple use

CLASS_REQUIRES(T, _Cloneable);

– all instances of ##_type are replaced by T

– all instances of ##_concept are replaced by _Cloneable

• result (actually as a single line)

using __func_T_Cloneable = void (_Cloneable<T>::*)();

template <__func_T_Cloneable> struct _check_T_Cloneable {};

using _check_typedef_T_Cloneable = _check_T_Cloneable<&_Cloneable<T>::__constraints>;

• leading underscores in names are to be regarded as reserved for the implementation, don’t use for user names

TDDD38 APiC++ Templates 204

Template compilation models

The inclusion compilation model

• the definition for a template is included in every file in which the template is instantiated

• one can still have a template function declaration on an inclusion file (fun.h) and its definition on a separate file (fun.tcc)

– in such case the .h files pulls in the .tcc file at its end – #include "fun.tcc"

– the alternative would be to have only the template function definition in fun.h, and no fun.tcc file

• a variation of this allows you to exclude #include "fun.tcc" in the fun.h file

– in this case the compiler implicitly knows by some rule where to look for fun.tcc

• the inclusion compilation model is the model that most current C++ compilers provide

The separation compilation model

• basically the traditional model with header files and corresponding implementation files

– an implementation file is not pulled into its header file

– compiled separately

– difficult to implement, few compilers have

• this compilation model is related to the keyword export

–export is removed from C++11 – “ The export keyword is unused but is reserved for future use.”

– seems meaningless to get into any details…

TDDD38 APiC++ Standard library – Overview 205

Standard library overview

• content is overall fairly traditional, e.g.

– containers (data structures)

– algorithms (standard functions)

– input and output (streams)

• new features in C++11

– threads

– regular expressions

– the whole standard library is adapted to support move semantics and perfect forwarding

• may seem complicated, but a closer look shows it to be

– flexible

– general

– extendible

– efficient

• the implementation uses several advanced core language features, often in combination, e.g.

– templates, including the new feature variadic templates

– derivation (single, multiple, repeated, virtual)

– operator overloading

– rvalue references (move semantics, perfect forwarding,…)

– type traits, template meta programming

TDDD38 APiC++ Standard library – Overview 206

Standard library content

•Language support – program start/termination, limits, dynamic memory handling, initializer lists, runtime support

•Diagnostics – components used to detect and report error conditions – exceptions and assertions

•General utilities – components used by other elements of the standard library and may be used by programs

– pair, tuples, type traits, function objects, function call wrappers, memory allocation, smart pointers, date and time, functions for move

semantics and forwarding, type traits

•Strings – components for manipulating sequences of characters, numeric conversions

•Localization – components programs may use to encapsulate cultural differences.

– character classification, string collation, numerics, monetary and date/time formatting and parsing

•Containers – components used for organizing collections of information – sequence containers, adaptors, associative containers

•Iterators – components used to perform iterations over containers and stream buffers

•Algorithms – components used to perform algorithmic operations on containers and other sequences

•Numerics – components used to perform numerical operations, random number generators, conformance with C99 functions

•Input / output – components for input/output operations

•Regular expressions – components to perform operations making regular expressions matching an searching

•Atomic operations – components for fine-grained atomic access

•Thread support – components to create and manage threads, perform mutual exclusion, and communicate conditions between threads

TDDD38 APiC++ Standard library – Overview 207

C++1y Standard Library

ISO/TS Technical Specifications – to be part of the standard, or withdrawn:

• Library fundamentals – e.g. classes and functions likely to be used widely within a program

• File system – standardized file access (paths, regular files, directories)

• Parallelism – vector and multi-core support

• Concurrency – tasks, thread pools

• Concepts – extensions to enable specification and checking of constraints on template arguments

• Arrays – dynamic arrays

• Transactional memory – STM (Software Transactional Memory)

• Ranges – support for range-based versions of the standard algorithms

• Networking

TDDD38 APiC++ Standard library – Overview 208

Standard library in this course

Main focus in this course:

• things related to data structures and algorithms

– containers

– algorithms

– iterators

– function objects

– lambda expressions (core language)

– related utilities

• streams and strings

– general streams

– file streams

– string streams

– std::string is a kind of container

• smart pointers

Containers

Function

Iterators Algorithms

objects

Streams

TDDD38 APiC++ Standard library – Overview 209

Example: containers – iterators – algorithms – function objects – streams

#include <algorithm> // copy, sort, unique, for_each

#include <functional> // greater, unary_function

#include <iostream> // ostream, cin, cout

#include <iomanip> // setw

#include <iterator> // istream_iterator, ostream_iterator

#include <numeric> // accumulate

#include <vector> // vector

// Function object to be used in algorithms for printing (suitable) objects of type T to an ostream

template<typename T>

class printw

{

public:

printw(std::ostream& os, int width = 6) : os_{ &os }, width_{ width } {}

void operator()(const T& x) const

{

*os_ << std::setw(width_) << x << ((++n_ % 10 == 0) ? "\n" : "");

}

private:

std::ostream* os_;

const int width_;

mutable int n_{ 0 };

};

TDDD38 APiC++ Standard library – Overview 210

int main()

{

using namespace std;

vector<int> v{ istream_iterator<int>{cin}, istream_iterator<int>{} };

copy(begin(v), end(v), ostream_iterator<int>{cout, " "});

sort(begin(v), end(v));

v.erase(unique(begin(v), end(v)), end(v));

sort(begin(v), end(v), greater<int>{});

for_each(begin(v), end(v), printw<int>{cout, 4});

cout << "\nSum = " << accumulate(begin(v), end(v), 0) << ’\n’;

}

TDDD38 APiC++ Standard Library – Containers 211

Standard Containers Library (1)

C++ containers are objects that store other objects – data structures.

• controls allocation and deallocation of the stored objects through constructors, destructors, insert and erase operations

• physical implementation is not defined by the standard, instead

– complexity requirements for each operation is stated, e.g. compile time, constant, linear, …

– elements are ordered in some containers

• the type of objects stored in standard containers must meet some general requirements, e.g.

–constructible – have copy constructor and destructor

–moveable – have move constructor

–assignable – have copy assignment operator

• especially efficient operations are typically applied directly at some specific, implicit position of the container, e.g.

–vector has push_back(x) and pop_back(),emplace_back(x)

–deque and list have also push_front(x) and pop_front(), emplace_front(x) and emplace_back(x)

• other operations typically take iterator arguments, e.g.

–insert(iterator,x) – the insertion of xcan typically be relatively costly

• emplace operations

– copy/move-free, in-place construction

– given arguments can be passed directly to a constructor for the element type

– vector has emplace_back(args) and emplace(iterator,args) – args to be passed to a constructor of the element type

TDDD38 APiC++ Standard Library – Containers 212

Standard Containers Library (2)

• basic sequence containers

–array – a fixed-sized container with performance of built-in arrays (std::arrays are aggregates)

–vector – the sequence container to “use by default”

–deque – when most insertions and deletions take place at the beginning or end

–list – when frequent insertions and deletions not at the beginning and/or end

–forward_list – a container with no storage or time overhead compared to a hand-written singly linked list

•sequence adaptors represent three frequently used specialized data structures

–stack

–queue

–priority_queue

– have a basic sequence container as member

– have an adapted interface – the set of operations is reduced and operations renamed according to convention

– provide no iterators

•associative containers (ordered)

–set and multiset store keys only – the key is the value

–map and multimap store key-value pairs

•unordered associative containers – hash-table-like data structures, bucket-organized

–unordered_set and unordered_multiset

–unordered_map and unordered_multimap

TDDD38 APiC++ Standard Library – Containers 213

Regarding exam

• important to have a good overview and understanding of the containers library

– good knowledge of different container types and their common and specific features

– sufficient practice in using containers, in combination with other components

– unordered associative containers will not be required for solving programming problems

•cplusplus.com Reference will be available at exam (web browser)

• see the course examination page for more information

TDDD38 APiC++ Standard Library – Containers 214

Container member types

• all containers defines member types, e.g. vector defines the following

typedef T value_type;

typedef Allocator allocator_type;

typedef value_type& reference;

typedef const value_type& const_reference;

typedef implementation-defined iterator;

typedef implementation-defined const_iterator;

typedef reverse_iterator<iterator> reverse_iterator;

typedef reverse_iterator<const_iterator> const_reverse_iterator

typedef implementation-defined size_type;

typedef implementation-defined difference_type;

typedef typename allocator_traits<Allocator>::pointer pointer;

typedef typename allocator_traits<Allocator>::const_pointer const_pointer;

– used in declarations of the member functions for declaring parameter types and return types

– used by other standard library components

– to be used otherwise whenever possible to reduce implementation dependencies and relax couplings

–implementation-defined types are typically defined by the associated memory allocator

– reverse iterators are easily defined by the iterator adapter reverse_iterator template

TDDD38 APiC++ Standard Library – Containers 215

Container iterators

• all containers except the sequence adaptors provide container specific iterators

• container iterator types

iterator

const_iterator

reverse_iterator

const_reverse_iterator

–const refers to the container and its elements

• iterators are divided into different iterator categories representing different levels of functionality

–vector,deque and array provide random access iterators

–list and all associative containers provide bidirectional iterators

–forward_list and all unordered associative containers provide forward iterators

• there is a special iterator value – past-the-end iterator

– represents the iterator position following after the last element in a container

– only for comparing with other iterators

for (vector<int>::iterator it = begin(v); it != end(v); ++it)

{

cout << *it << ’\n’;

}

– there might not exist any valid before-the-first position for some container implementations

TDDD38 APiC++ Standard Library – Containers 216

Container iterator interface

• each member function above is overloaded in a const and a non-const version

– if the container object is non-const the returned iterator is an iterator or reverse_iterator

– if the container object is const the returned iterator is a const_iterator or const_reverse_iterator

• these are only declared as const member functions

– can be invoked for both const and non-const containers

•forward_list and unordered associative containers does not provide reverse iterators

–no rbegin(), rend(), crbegin(), or crend()

c.begin() Returns an iterator to the ﬁrst element, a past-the-end iterator if c is empty

c.end() Returns a past-the-end iterator

c.rbegin() Returns a past-the-end reverse iterator

c.rend() Returns a reverse iterator to ﬁrst element in c, a past-the-end reverse iterator if c is empty

c.cbegin() Returns a const iterator to ﬁrst element, past-the-end const iterator if c is empty

c.cend() Returns a past-the-end const iterator

c.crbegin() Returns a past-the-end const reverse iterator

c.crend() Returns a const reverse iterator to ﬁrst element in c, a past-the-end const iterator if c is empty

TDDD38 APiC++ Standard Library – Containers 217

Container iterator semantics

•reverse_iterator is moved backwards with ++ – makes iterators and reverse iterators exchangeable

•rend() points to the same element as begin() – the first element (if any)

•rbegin() points to the same element as end() – “past-the-end-iterator”

• When a reverse_iterator is dereferenced, it is the preceding element that is obtained – don’t dereference rend()

For reverse iterators, operator* and operator->() are implemented as:

reference operator*() const pointer operator->() const

{{

iterator tmp = *this;return &(operator*());

return *--tmp; }

}

begin()

rend()

end()

rbegin()

rit

*rit

*it

TDDD38 APiC++ Standard Library – Containers 218

Container iterators – type conversions

• implicit conversions

– from iterator to const_iterator

– from iterator to reverse_iterator

– from const_iterator to const_reverse_iterator

• explicit conversions – member function base()

– from reverse_iterator to iterator

– from const_reverse_iterator to const_iterator

iterator const_iterator

reverse_iterator const_reverse_iterator

base()

TDDD38 APiC++ Standard Library – Containers 219

Sequence containers

• organizes objects of the same kind into a strictly linear arrangement

• how they can be pictured

–array

–vector

–deque

–list

–forward_list

• for some there is a distinction between size and capacity

–size refers to the number of stored elements – the logical size

–capacity refers to the size of the available storage – the physical size

•deque actually require a more complicated implementation than illustrated above to fulfill complexity requirements

TDDD38 APiC++ Standard Library – Containers 220

Sequence containers – construction, copying, assignment, and destruction (1)

All sequence containers have

•default constructor,copy constructor,copy assignment operator and destructor

vector<int> v1;

vector<int> v2{ v1 };

v2 = v1;

array<int, 100> a;

•move constructor and move assignment operator

vector<int> v3{ std::move(v1) };

v3 = std::move(v2);

• constructor taking an initializer list

vector<int> v4{ 1, 2, 3 };

TDDD38 APiC++ Standard Library – Containers 221

Sequence containers – construction, copying, assignment, and destruction (2)

All sequence containers except array have

• constructor for initializing with n value-initialized elements

vector<int> v5{ 10 };

• constructor for initializing with n elements with a specific value – cannot use braces here!

vector<int> v6(10, -1);

• constructor for initialize with values from an iterator range

vector<int> v7{ begin(v6), end(v6) };

• assignment operator taking an initializer list

v7 = { 1, 2, 3 };

• assign member functions

v5.assign({ 1, 2, 3 }); // values from an initializer list

v6.assign(10, -1); // 10 elements with value -1

v7.assign(begin(v6), end(v6)); // values from the range [begin(v6), end(v6))

Note: There is a versions of all constructors also taking an allocator.

TDDD38 APiC++ Standard Library – Containers 222

Sequence containers – operations (1)

Size, capacity vector deque list forward_list array

n = c.size() ••• •size() == max_size() for array

m = c.max_size() ••• • •

c.resize(sz)••• increase or decrease

c.resize(sz,x)••

n = c.capacity() •

b = c.empty() ••• • •

c.reserve(n)•increase capacity to at least n

c.shrink_to_fit() •• reduces capacity, maybe to size()

Element access

c.front() ••• • •

c.back() ••• •

c[i]•• •

c.at(i)•• •throws out_of_range, if invalid i

data() ••pointer to ﬁrst element

Note: access functions, except data(), returns a reference which allows for modiﬁcation, if c is non-const

TDDD38 APiC++ Standard Library – Containers 223

Sequence containers – operations (2)

Modiﬁers vector deque list forward_list array

c.push_back(x)•••

c.pop_back() •••

c.push_front(x)•• •

c.pop_front() •• •

it = c.insert(begin(c), x)•••

it = c.insert(begin(c), n,x)•••

it = c.insert(begin(c), { x,y,z }) •••

c.insert(begin(c), it1,it2)•••

it = c.erase(begin(c)) •••

it = c.erase(begin(c), end(c)) •••

c1.swap(c2)••• • •

c.clear() ••• •

TDDD38 APiC++ Standard Library – Containers 224

Sequence containers – operations (3)

•emplace – “to put into place” or “put into position”

– emplace functions are variadic template functions

–args is a template parameter pack – constructor arguments matching a constructor for the element type is expected

– stored objects are created inplace – no copy/move required (constructor arguments will be copied or moved)

Modiﬁers, cont. vector deque list forward_list array

c.emplace_front(args)•• •

c.emplace_back(args)•••

it = c.emplace(pos,args)•••

it = c.emplace_after(args)•

Comparisons vector deque list forward_list array

== != ••• • •

<<=>>= ••• • •

Specialized algorithm

swap(c1,c2)••• • •

TDDD38 APiC++ Standard Library – Containers 225

Sequence containers – special list and forward_list operations

Since list and forward_list does not provide random access iterators, a number of general algorithms cannot be applied.

There is also a number of special member functions, overloaded in several versions, related to list inserting,splicing and erasing

•insert(), splice(), and erase() for list

•insert_after(), splice_after(), and erase_after() for forward_list

•inserting will not affect source

•splicing will remove the element(s) in question from source

The following member functions corresponds to such general algorithms

c.remove(x)remove x

c.remove_if(pred)remove elements for which pred(element) is true

c.unique() remove consecutive equivalent elements; == used for comparison

c.unique(pred)remove consecutive equivalent elements; pred used for comparison

c1.merge(c2)merge c1 and c2; both must be ordered with <; c2 becomes empty

c1.merge(c2,comp)merge c1 and c2; both must be ordered with comp; c2 becomes empty

c1.sort() order elements with <

c1.sort(comp)order elements using comp

c1.reverse() place elements in reverse order

TDDD38 APiC++ Standard Library – Containers 226

Sequence adaptors

• each adaptor class adapts the interface to model one of three classic data structures

–stack

–queue

–priority_queue

• have a sequence container as private data member to store the elements

– for each adaptor type a default sequence container type is used internally

stack – deque

queue – deque

priority_queue – vector

– this container can be replaced by any other container fulfilling the requirements (operations and complexity)

– standard library heap operations are used to implement priority_queue operations

• these adaptions significantly simplifies the interface

– substantial reduction of the number of operations, compared to the sequence container used internally

– operations renamed according to “tradition” – e.g. push,top and pop for stack

– no iterators provided – not relevant for these data structures

TDDD38 APiC++ Standard Library – Containers 227

Sequence adaptors – construction, copying, assignment, and destruction

All sequence adaptors have

•default constructor,copy constructor,copy assignment operator and destructor

priority_queue<int> pq1;

•move constructor and move assignment operator

• constructor for initializing with elements from a container

vector<int> v;

...

queue<int> q1{ v };

• versions of the constructors and assignment operators above also taking an allocator

priority_queue also have

• constructor taking a comparer – default is std::less (corresponds to operator<)

priority_queue<int, std::greater<int>> pq2;

• constructor for initializing with elements from an iterator range

priority_queue<int> pq2{ begin(v), end(v) };

• versions of these constructors taking an allocator

TDDD38 APiC++ Standard Library – Containers 228

Sequence adaptors – operations

Size, capacity stack queue priority_queue

n = a.size() •• •

b = a.empty() •• •

Element access stack queue priority_queue

x = a.top() ••

x = pq.front() •

x = pq.back() •

Modiﬁers stack queue priority_queue

a.push(x)•• •

a.pop() •• •

a.emplace(args)•• •

Comparisons stack queue priority_queue

== != ••

<<=>>= ••

TDDD38 APiC++ Standard Library – Containers 229

std::initializer_list (1)

This is not a container type, it’s a language support component for implementing initializer lists – <initializer_list>

• have some similarities with sequence containers

• elements are stored in a hidden array of const E

• typically used as function parameter type for passing initializer lists as argument

vector& operator=(initializer_list<T>);

v = { 1, 2, 3, 4, 5 };

A pair of pointers, or a pointer and a length is obvious representations (GCC uses the latter)

• a private constructor, to be used by the compiler initialize this

Special member functions not declared (all except default constructor) are compiler generated.

• copying an initializer list does not copy the underlying elements

– shallow copy

12345

TDDD38 APiC++ Standard Library – Containers 230

std::initializer_list (2)

template<class E> class initializer_list

{

public:

typedef E value_type;

typedef const E& reference; // elements are const !

typedef const E& const_reference;

typedef std::size_t size_type;

typedef const E* iterator; // elements are const !

typedef const E* const_iterator;

initializer_list() noexcept;

size_type size() const noexcept;//number of elements

const_iterator begin() const noexcept;//first element

const_iterator end() const noexcept;//one past the last element

};

// initializer list range access

template<class E> constexpr const E* begin(initializer_list<E> il) noexcept;

template<class E> constexpr const E* end(initializer_list<E> il) noexcept;

TDDD38 APiC++ Standard Library – Containers 231

Utility class pair

• utility class for storing pair of values – used by map containers and functions returning two values

• defines types used by other components of the standard library (T1 and T2 are the template parameters)

typedef T1 first_type;

typedef T2 second_type;

• have default constructor, copy/move constructor, copy/move assignment operator, destructor and type converting constructors

pair<int,char> p2{ 1, ’A’ }; initialize with a pair of values

pair<double,int> p3{ p2 }; automatic type conversion

• element access – all members are public

p2.first

p2.second

• comparisons

== != < > <= >=

• utility template function make_pair to ease creation of a pair – template type parameters are deduced from the arguments

p = make_pair(x, y)

TDDD38 APiC++ Standard Library – Containers 232

Associative containers

Provide fast retrieval of data based on keys

• the following associative containers are ordered

map multimap set multiset

• corresponding unordered associative containers

unordered_map unordered_multimap unordered_set unordered_multiset

•set containers store only keys (values)

•map containers store key-value-pairs – uses pair to store a key and its associated value

• non-multi variants only allows unique keys

• multi variants allows equivalent keys

– several elements may have the same key and also the associated value may be the same

• in (ordered) associative containers elements are ordered by key

– parametrized on key type and ordering relation (and memory allocator)

– maps also associate an arbitrary type with the key, the value type

– typically implemented as a binary search tree (e.g. a red-black tree, a height-balanced binary search tree)

•inunordered associative containers elements are stored in a hash table

– parametrized on key type,hash function (unary function object), and equality relation (a binary predicate) (and memory allocator)

– maps also associate an arbitrary type with the key, the value type

– elements are organized into buckets – elements with keys having the same hash code appears in the same bucket

TDDD38 APiC++ Standard Library – Containers 233

Associative containers – construction, copying, assignment, and destruction

All associative containers have

•default constructor,copy constructor,copy assignment operator and destructor

map<int, string> m;

multi_set<string> ms;

unordered_map<int, X, hasher, equal> um;

•move constructor and move assignment operator

•constructor and assignment operator to initialize/assign with values from an initializer list

– unordered associative container constructor version can also take initial number of buckets,hash function, and equality relation

•constructor for initializing with values from an iterator range

– for ordered associative containers also with the possibility to give a comparer and an allocator

– for unordered associative containers also the initial number of buckets,hash function,equality relation, and an allocator can be given

•constructors equivalent to the default, copy and move constructors, also taking an allocator

TDDD38 APiC++ Standard Library – Containers 234

Associative containers (ordered)

#include <map>

#include <set>

Additional or redeclared member types

• map and multimap

typedef Key key_type; // Key is a template type parameter

typedef T mapped_type; // T is a template type parameter

typedef pair<const Key, T> value_type;

typedef Compare key_compare; // Compare is a template type parameter

value_compare is declared as a nested function object class

• set and multiset

typedef Key key_type; // Key is a template type parameter

typedef Key value_type;

typedef Compare key_compare; // Compare is a template type parameter

typedef Compare value_compare;

TDDD38 APiC++ Standard Library – Containers 235

Associative containers (ordered) – operations (1)

Size, capacity map multimap set multiset

n = a.size() ••••

n = a.max_size() ••••

b = a.empty() ••••

Comparisons map multimap set multiset

== != ••••

<<=>>= ••••

Element access map multimap set multiset

x = a[k]•

x = a.at(k)•throws out_of_range if no such element

Note: if an element with key k does not exist in the map, it is created by operator[], with the associated value default initialized

return value_type(k, T());

areference is returned which can be used to assign a value to second

m[k] = x;

TDDD38 APiC++ Standard Library – Containers 236

Associative containers (ordered) – operations (2)

*) in case map and multimap,x has type pair<key_type, value_type)

Modiﬁers map multimap set multiset

pair<iterator,bool> p = a.insert(x)••*

it = a.insert(x)••*

it = a.insert(pos,x)••••*

a.insert(first,last)••••

a.insert( { x,y,z } ) ••••

pair<iterator,bool> p = a.emplace(args); ••

it = a.emplace(args)••

it = a.emplace_hint(pos,args)••••

a.erase(it)••••

n = a.erase(k)••••

a.erase(first,last)••••

a1.swap(a2)••••

a.clear() ••••

TDDD38 APiC++ Standard Library – Containers 237

Associative containers (ordered) – operations (3)

Map and set operations map multimap set multiset

it = a.find(k)••••

n = a.count(k)••••

it = a.lower_bound(k)••••

it = a.upper_bound(k)••••

pair<iter,iter>p = a.equal_range(k); ••••

Specialized operation map multimap set multiset

swap(a1,a2)••••

Observers map multimap set multiset

comp = a.key_comp() ••••

comp = a.value_comp() ••••

TDDD38 APiC++ Standard Library – Containers 238

Unordered associative containers

• declared in <unordered_map> and <unordered_set>

• based on hash tables

– bucket count can change dynamically

– initial number of buckets is implementation defined

– each bucket has its own chain of elements

• default hash functions declared in <functional>, <string>, …

– bool

– character types

– integer types

– floating point types

– string types

– pointer types

– smart pointer types Conceptually, implementations may differ!

TDDD38 APiC++ Standard Library – Containers 239

Unordered associative containers

Additional or redeclared member types

•unordered_map and unordered_multimap

typedef Key key_type; // Key is a template type parameter

typedef T mapped_type; // T is a template type parameter

typedef pair<const Key, T> value_type;

•unordered_set and unordered_multiset

typedef Key key_type; // Key is a template type parameter

typedef Key value_type;

• hash function and hash key related

typedef Hash hasher; // Hash is a template type parameter

typedef Pred key_equal; // Pred is a template type parameter

• bucket iterators

typedef implementation-defined local_iterator;

typedef implementation-defined const_local_iterator;

TDDD38 APiC++ Standard Library – Containers 240

Unordered associative containers operations (1)

Size, capacity unordered_map unordered_multimap unordered_set unordered_multiset

n = u.size() ••••

n = u.max_size() ••••

b = u.empty() ••••

Comparisons unordered_map unordered_multimap unordered_set unordered_multiset

== != ••••

<<=>>=

Element access unordered_map unordered_multimap unordered_set unordered_multiset

x = u[k]•

x = u.at(k)•

Note 1: if an element with key k does not exist in the map, it is created by operator[], with the associated value default

initialized. A reference to the associated value is returned and can be used to assign a value.

Note 2: if an element with key k does not exist in the map, member function at(k) throws out_of_range.

TDDD38 APiC++ Standard Library – Containers 241

Unordered associative containers operations (2)

*) in case unordered_map or unordered_multimap, x has type pair<key_type, value_type>

Modiﬁers u_map u_multimap u_set u_multiset

pair<iterator,bool>p = u.insert(x); ••*

it = u.insert(x)••*

it = u.insert(it_hint,x)••••*

u.insert(first,last)••••

u.insert( { x,y,z } ) ••••

pair<iterator,bool>p = u.emplace(args); ••

it = u.emplace(args)••

it = u.emplace_hint(pos,args)••••

u.erase(it)••••

n = u.erase(k)••••

u.erase(first,last)••••

u1.swap(u2)••••

u.clear() ••••

TDDD38 APiC++ Standard Library – Containers 242

Unordered associative containers operations (3)

Map and set operations u_map u_multimap u_set u_multiset

it = u.find(k)••••

n = u.count(k)••••

pair<iter,iter>p = u.equal_range(k); ••••

Specialized operation u_map u_multimap u_set u_multiset

swap(u1,u2)••••

TDDD38 APiC++ Standard Library – Containers 243

Unordered associative containers operations (4)

Bucket interface

The hash table used for storing elements is bucket organized – each hash entry can store several elements.

n = u.bucket_count() current number of buckets for container u

m = u.max_bucket_count() maximum number of buckets possible for container u

s = u.bucket_size(b)number of elements in bucket b

b = u.bucket(k)bucket number where keys equivalent to k would be found

it = u.begin(b)iterator to the ﬁrst element in bucket b

it = u.end(b)const past-the-end iterator for bucket b

it = u.cbegin(b)iterator to the ﬁrst element in bucket b

it = u.cend(b)const past-the-end iterator for bucket b

pair<it,it>p = u.equal_range(k); range containing elements with keys equivalent to k

TDDD38 APiC++ Standard Library – Containers 244

Unordered associative containers operations (5)

Hash policy interface

Observers

f = u.load_factor() average number of elements per bucket.

f = u.max_load_factor() a positive number that the container attempts to keep the load factor less than or equal to

u.max_load_factor(f)may change the container’s maximum load factor, using fas a hint

u.rehash(n)alters the number of buckets to be at least nbuckets – rebuilds the hash table as needed

u.reserve(n)reserves space for at least the speciﬁed number of elements and regenerates the hash table

n = u.hash_function() u’s hash function

eq = u.key_eq() key equality predicate

TDDD38 APiC++ Standard Library – Containers 245

Iterating over buckets and bucket contents

unordered_map<string> table;

// table is populated…

auto n_buckets = table.bucket_count();

for (decltype(n_buckets) b = 0; b < n_buckets; ++b)

{

cout << "Bucket " << b " has " << table.bucket_size(b) << " elements: ";

copy(table.cbegin(b), table.cend(b), ostream_iterator<string>(cout, ", "));

cout << ’\n’;

}

The type of n_buckets and b is unordered_map<string, Item>::size_type

TDDD38 APiC++ Standard Library – Containers 246

Some comments on containers library design

• covers a wide variety of common data structures

• uniform interfaces

• all containers, except the sequence adaptors, provide iterators

– the elements in different type of containers can be operated upon in a uniform manner

• policy technique is used for different adaptions, e.g.

– memory allocation

– comparison and equivalence functions

– hash functions

• supports static polymorphism and generic programming

– templates parametrized on different aspects

• supports move semantics, perfect forwarding, and emplacement construction

• type traits and concept checking is frequent in the implementation

– checking requirements for instantiation types

– selecting the most efficient implementation among several candidates

– solving ambiguities that may arise due to instantiation types

• given array,vector and string there is little reason to use C-style arrays

TDDD38 APiC++ Standard Library – Algorithms 265

Standard Algorithms Library

#include <algorithm>

Generic components that programs may use to perform algorithmic operations on e.g. containers.

• mainly function templates

– most operate on data structures and objects through iterators

• categorized as follows in the standard library

– non-modifying sequence operations

– mutating sequence operations

– sorting and related operations

– algorithms for numeric computations are found in the Numerics library, <numeric>

– C library algorithms, <cstdlib>

• separated from the particular implementation of different data structures by iterators

– the iterator category names are used to reflect the minimum requirements of an algorithm, e.g. BidirectionalIterator

•move semantics may be applied by some algorithms

TDDD38 APiC++ Standard Library – Algorithms 266

Regarding exam

• the following algorithms are not an exam topic

– shuffle algorithms

– set algorithms

– heap algorithms

– lexicographical comparison algorithms

– permutation generators

– allowed, if suitable and available and not contradicted by given requirements

• important to have a good overview and understanding of the algorithms library

– what kind of algorithms available and how to use them

– sufficient practice in using algorithms, in combination with other components

•cplusplus.com Reference will be available at exam (web browser)

• see the course examination page for more information

TDDD38 APiC++ Standard Library – Algorithms 267

Notes on standard algorithms design (1)

• many algorithms comes in several versions, sometimes with slightly different names, for example

–abasic version and a version taking an additional predicate, named algorithm and algorithm_if

copy(begin(v1), end(v1), back_inserter(v2));

copy_if(begin(v1), end(v1), back_inserter(v2), bind(less_equal<int>{}, _1, 10));

–anin-place version and a copy version, named algorithm and algorithm_copy (and possibly algorithm_copy_if)

reverse(begin(v), end(v));

reverse_copy(begin(v1), end(v1), back_insert(v2));

– one version for one input range and one version for two input ranges

transform(begin(v1), end(v1), begin(v1), negate<int{}); // result in v1

transform(begin(v1), end(v1), begin(v2), back_inserter(v3), plus<int>{});

Note 1: less_equal,negate and plus are standard function object types, bind is a utility function for binding function arguments

Note 2: a lambda expression is much simpler to use instead of bind and less_equal

TDDD38 APiC++ Standard Library – Algorithms 268

Notes on standard algorithm design (2)

• some algorithms does not modify size, as one might expect, but instead leave “garbage” at the end of the modified range

unique(begin(v), end(v));

template<typename ForwardIterator>

ForwardIterator

unique(ForwardIterator first, ForwardIterator last)

{

// Skip to first occurrence of adjacent equal values

first = std::adjacent_find(first, last);

if (first == last)

return last;

// Uniquify the rest

ForwardIterator dest = first;

++first;

while (++first != last)

if (! (*dest == *first))

*++dest = std::move(*first);

return ++dest;

}

• to get rid of the “garbage” it also must be erased (size adjusted)

v.erase(unique(begin(v), end(v)), end(v));

123345556

123456556

first last

first lastdest

123456

TDDD38 APiC++ Standard Library – Algorithms 269

Notes on standard algorithm design (3)

• functions (function pointers or function objects) are passed and returned by value

template <typename InputIterator, typename Function>

Function

for_each(InputIterator first, InputIterator last, Function f)

{

for ( ; first != last; ++first)

f(*first);

return std::move(f);

}

– the return value from the function f, if any, is ignored – f typically have a side effect, e.g. to print the element

– classified as non-modifying, since it does not explicitly modify the elements, but…

void negate(int& i) { i = -i; } // reference parameter

for_each(begin(v), end(v), negate); // the elements in v are negated

– the fact that for_each returns f opens for interesting possibilities – f can be a function object with state

Fun_Obj fun;

fun = for_each(begin(v), end(v), fun);

cout << fun.get_result() << endl;

– or use a std::reference_wrapper to pass fun by reference – example later

TDDD38 APiC++ Standard Library – Algorithms 270

Notes on standard algorithm design (4)

• ordinary function call syntax is always used within the algorithms

template<typename ForwardIterator, typename Generator>

void

generate(ForwardIterator first, ForwardIterator last, Generator gen)

{

for (; first != last; ++first)

*first = gen();

}

– to call a member function, a function call wrapper must be used (covered in Function objects)

TDDD38 APiC++ Standard Library – Algorithms 271

Notes on standard algorithm design (4)

• assignment (operator=) is used for copying elements

template<typename InputIterator, typename OutputIterator>

OutputIterator

copy(InputIterator first, InputIterator last, OutputIterator result)

{

for ( ; first != last; ++result, ++first)

*result = *first;

return result;

}

– if the capacity of result is not guaranteed an insert iterator must be used

copy(begin(v1), end(v1), back_inserter(v2));

•operator== and operator< are used by default when comparing elements for equality or for ordering

– such algorithms typically come in two versions, one using the default implicitly and one taking a comparer as an extra argument

sort(begin(v1), end(v1)); // uses operator<

sort(begin(v1), end(v1), std::greater<int>{});

sort(begin(v1), end(v1), [](int x, int y){ return y < x; });

TDDD38 APiC++ Standard Library – Algorithms 272

Notes on standard algorithm design (5)

• iterators are passed by value

template <typename InputIterator, typename OutputIterator, typename Predicate>

OutputIterator

copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred)

{

for (; first != last; ++first)

if (pred(*first))

{

*result = *first;

++result;

}

return result;

}

– semantically the objects are accessed by reference

• input and output ranges may or may not overlap

– ranges may not overlap for (most) copy, swap and set algorithms

• iterators can be invalidated by algorithms

– modifying algorithms typically invalidate stored iterators

TDDD38 APiC++ Standard Library – Algorithms 273

Notes on standard algorithm design (6)

• input values of generic type are passed by const&, and return values are returned by const&, when suitable

template <typename T>

const T&

min(const T& a, const T& b)

{

if (b < a)

return b;

return a;

}

– semantically this is passing by value in a effective way, and reduces the requirements on T (no copy/destroy required)

• input values of (to be) simple type are passed by value

template <typename InputIterator, typename Size, typename OutputIterator>

OutputIterator

copy_n(InputIterator first, Size n, OutputIterator result)

{

for ( ; n > 0; --n)

{

*result = *first;

++first;

++result;

}

return result;

}

TDDD38 APiC++ Standard Library – Algorithms 274

reference_wrapper

Utility class to create objects that act as references but can be copied.

• two helper functions

–ref(T) returns a T& wrapper object

–cref(T) returns a const T& wrapper object

Example:

class sum {

public:

sum() : acc(0) {}

void operator()(int x) { acc += x; }

int get_sum() const { return acc; }

private:

int acc;

};

• algorithm for_each takes a function as third argument and passes it by value, and finally return that copy by value

vector<int> v{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

sum s;

for_each(begin(v), end(v), ref(s)); // alternative: s = for_each(begin(v), end(v), s);

cout << s.get_sum() << endl;

TDDD38 APiC++ Standard Library – Algorithms 275

Non-modifying sequence operations (1)

Function for_each(ﬁrst,last,f) applies the function f to each element in [ﬁrst,last); returns f

Note: f can be passed by reference using std::reference_wrapper

ncount(ﬁrst,last,value) returns the number of elements in [ﬁrst,last) equal to value

ncount_if(ﬁrst,last,pred) returns the number of elements in [ﬁrst,last) for which pred is true

iter ﬁnd(ﬁrst,last,value) ﬁnd the ﬁrst element in [ﬁrst,last) equal to value

iter ﬁnd_if(ﬁrst,last,pred) ﬁnd the ﬁrst element in [ﬁrst,last) for which pred is true

iter ﬁnd_if_not(ﬁrst,last,pred) ﬁnd the ﬁrst element in [ﬁrst,last) for which pred is false

iter ﬁnd_ﬁrst_of(ﬁrst1,last1,ﬁrst2,last2) ﬁnd the ﬁrst element in [ﬁrst1,last1) equal to one of the elements in [ﬁrst2,last2)

iter ﬁnd_end(ﬁrst1,last1,ﬁrst2,last2) ﬁnd the last subsequence in [ﬁrst1,last1) equal to [ﬁrst2,last2)

iter search(ﬁrst1,last1,ﬁrst2,last2) search for the ﬁrst subsequence in [ﬁrst1,last1) equal to [ﬁrst2,last2)

iter search_n(ﬁrst,last,count,value) search for the ﬁrst subsequence in [ﬁrst,last) of count elements equal to value

Note 1: algorithms returning an iterator returns last/last1 if not successful.

Note 2:ﬁnd_ﬁrst_of,ﬁnd_end,search and search_n use operator== by default to compare for equality; they all also come in a version

taking a binary predicate to be used instead.

TDDD38 APiC++ Standard Library – Algorithms 276

Non-modifying sequence operations (2)

bool all_of(ﬁrst1,last1,pred)true if pred is true for all elements in [ﬁrst1,last1)

bool any_of(ﬁrst1,last1,pred)true if pred is true for any element in [ﬁrst1,last1)

bool non_of(ﬁrst1,last1,pred)true if pred is true for none of the element in [ﬁrst1,last1)

iter adjacent_ﬁnd(ﬁrst,last) returns iterator to ﬁrst two consecutive equal elements in [ﬁrst,last), or last

bool equal(ﬁrst1,last1,ﬁrst2)true if the elements in [ﬁrst1,last1) and [ﬁrst2, …) are equal

pair<it1,it2>mismatch(ﬁrst1,last1,ﬁrst2) returns the positions in [ﬁrst1,last1) and [ﬁrst2, …) where the elements in the

sequences differ for the ﬁrst time; if all elements match, last1 and an iterator

into ﬁrst2 offset by the size of [ﬁrst1,last1) is returned

bool is_permutation(ﬁrst1,last1,ﬁrst2)true if there is a permutation of the elements in [ﬁrst2,…) with the same

number of elements as are in [ﬁrst1,last1) and for which the elements in the

permutation and in [ﬁrst1,last1) are equal

Note: adjacent_ﬁnd,equal,mismatch, and is_permutation by default uses operator== for equality test, They all also come in a version

taking a binary predicate to be used instead.

TDDD38 APiC++ Standard Library – Algorithms 277

Mutating sequence operations (1)

ﬁll(ﬁrst,last,value) assign value to the elements in [ﬁrst,last)

ﬁll_n(ﬁrst,n,value) assign value to the elements in [ﬁrst,ﬁrst + n)

generate(ﬁrst,last,gen) invokes gen() and assign the return value to each element in [ﬁrst,last)

generate_n(ﬁrst,n,gen) invokes gen() and assign the return value to each element in [ﬁrst,ﬁrst + n)

iter transform(ﬁrst,last,result,unary-op) applies unary-op to the elements in [ﬁrst,last), assigns result to [result, …)

iter transform(ﬁrst1,last1,ﬁrst2,result,binary-op) applies binary-op to the elements in two ranges, assigns result to [result, …)

iter copy(ﬁrst,last,result) copies all elements from [ﬁrst,last) into [result, …)

iter copy_n(ﬁrst,n,result) copies the ﬁrst n elements from [ﬁrst,…) into [result,…)

iter copy_if(ﬁrst,last,result,pred) copies all elements in [ﬁrst,last) for which pred is true

iter copy_backward(ﬁrst,last,result) copies elements backwards from [ﬁrst,last) into [result, …)

iter move(ﬁrst,last,result) like copy but elements are moved

iter move_backward(ﬁrst,last,result) like copy_backward but elements are moved

swap(x,y) exchanges values in two locations x and y

iter swap_ranges(ﬁrst1,last1,ﬁrst2) exchanges values pair-wise in two ranges [ﬁrst1,last1) and [ﬁrst2, …)

iter_swap(it1,it2) exchanges values pointed to by iterators it1 and it2

TDDD38 APiC++ Standard Library – Algorithms 278

Mutating sequence operations (2)

replace(ﬁrst,last,old,new) substitutes each element in [ﬁrst,last) equal to old with new

replace_if(ﬁrst,last,pred,new) substitutes each element in [ﬁrst,last) for which pred is true with new

iter replace_copy(ﬁrst,last,result,old,new)asreplace, but the result is copied into another range [result, …)

iter replace_copy_if(ﬁrst,last,result,pred,new)asreplace_if, but the result is copied into another range [result, …)

iter remove(ﬁrst,last,value) eliminates all elements in [ﬁrst,last) equal to value

iter remove_if(ﬁrst,last,pred) eliminates all elements in [ﬁrst,last) for which pred is true

iter remove_copy(ﬁrst,last,result,value)asremove but the result is copied into [result, …)

iter remove_copy_if(ﬁrst,last,result,pred)asremove_if but the result is copied into [result, …)

iter unique(ﬁrst,last) eliminates all but the ﬁrst from every consecutive group of equal elements

iter unique_copy(ﬁrst,last,result)asunique but the result is copied into [result, …)

reverse(ﬁrst,last) reverses the order of the elements in [ﬁrst,last)

iter reverse_copy(ﬁrst,last,result)asreverse but the result is copied into [result, …)

rotate(ﬁrst,new-ﬁrst,last) left rotate the elements in [ﬁrst,last) so new-ﬁrst becomes the ﬁrst element

iter rotate_copy(ﬁrst,new-ﬁrst,last,result)asrotate but the result is copied into [result, …)

Note 1:iter returned by the functions above, is an iterator pointing past-the-end of the resulting range.

Note 2: the input range for unique and unique_copy is normally supposed to be sorted.

Note 3: unique and unique_copy also comes in a version taking a predicate, to be used instead of operator== to compare for equality.

TDDD38 APiC++ Standard Library – Algorithms 279

Mutating sequence operations (3)

random_shufﬂe(ﬁrst,last) shufﬂes the elements in [ﬁrst,last) in a random way;

deprecated in C++14, use shufﬂe!

random_shufﬂe(ﬁrst,last,rand)asrandom_shufﬂe but using function rand;

deprecated in C++14, use shufﬂe!

shufﬂe(ﬁrst,last,uniform-rand) shufﬂes the elements in [ﬁrst,last) in a random way using function uniform-

rand

iter partition(ﬁrst,last,pred) places all element in [ﬁrst,last) satisfying pred before elements not

satisfying pred; iter points at the ﬁrst element in the second part

iter stable_partition(ﬁrst,last,pred)aspartition but the relative order of elements in both groups is preserved

bool is_partitioned(ﬁrst,last,pred)true if [ﬁrst, last) is empty, or if [ﬁrst,last) is partitioned by pred, i.e. all

elements satisfying pred occurs before those that do not

iter partition_point(ﬁrst,last,pred)[first,last) shall be partitioned by pred, i.e. all elements that satisfy pred

shall appear before those that do not; returns an iterator referring to the

partition point

pair partition_copy(ﬁrst,last,out-true,out-false,pred) copies elements in [ﬁrst,last) satisfying pred to out-true, elements not

satisfying pred to out-false; returns pair such that first is the end of the

output range beginning at out-true and second is the end of the output range

beginning at out-false

TDDD38 APiC++ Standard Library – Algorithms 280

Sorting and related operations (1)

sort(ﬁrst,last) sorts the elements in [ﬁrst,last)

stable_sort(ﬁrst,last)assort but preserving the relative order of equal elements

partial_sort(ﬁrst,middle,last) places the lowest-valued (middle -ﬁrst) elements in [ﬁrst,last) sorted in

[ﬁrst,middle)

iter partial_sort_copy(ﬁrst,last,result,result-last) places the min(last - ﬁrst,result-last - result) lowest-valued elements from

[ﬁrst,last) sorted in result in [result,result-last); iter is past-the-end of result

nth_element(ﬁrst,nth,last)nth must be an iterator pointing to an element in [ﬁrst,last); after

nth_element the element in the nth position is the element that would be

there if the whole range was sorted; elements to the left of nth are less or

equal to the nth element, elements to the right of nth are greater or equal, but

not ordered in any other way

bool is_sorted(ﬁrst,last) returns true is all elements in [ﬁrst,last) is sorted, false otherwise

iter is_sorted_until(ﬁrst,last) returns the last iterator in [ﬁrst,last) for which [ﬁrst,iter) is sorted

Note 1: operator< is used by default to compare; all also have a version taking a comparer to be used instead.

Note 2: from sort/stable_sort and down to nth_element, the degree of sorting is decreasing.

Note 3: library guarantee that sort moves (not copies), if available.

TDDD38 APiC++ Standard Library – Algorithms 281

Sorting and related operations (2)

bool binary_search(ﬁrst,last,value) returns true if value is found in [ﬁrst,last)

iter lower_bound(ﬁrst,last,value) returns ﬁrst position where value can be inserted without violating the ordering

iter upper_bound(ﬁrst,last,value) returns last position where value can be inserted without violating the ordering

pair<it1,it2>equal_range(ﬁrst,last,value) returns the largest subrange [it1,it2) where value can be inserted without

violating the ordering; the two iterators returned corresponds to the ones

returned by lower_bound and upper_bound.

Note 1: operator< is used by default to compare; all also have a version taking a comparer, to be used instead, as last argument.

Note 2:binary_search works for both random access an forward iterators.

iter merge(ﬁrst1,last1,ﬁrst2,last2,result) merges two sorted ranges, [ﬁrst1,last1) and [ﬁrst2,last2) into one sorted

range, [result, …); iter is past-the-end of the resulting range

inplace_merge(ﬁrst,middle,last) merges two sorted consecutive ranges, [ﬁrst,middle) and [middle,last), putting

the result into [ﬁrst,last)

Note 1: operator< is used by default to compare; both also have a version taking a comparer to be used instead.

Note 2: merging is stable, i.e. elements from the first range comes before equivalent elements from the second range.

TDDD38 APiC++ Standard Library – Algorithms 282

Set algorithms

Works on sorted structures, also works on multiset.

bool includes(ﬁrst1,last1,ﬁrst2,last2)true if every element in [ﬁrst2,last2) is contained in [ﬁrst1,last1)

iter set_union(ﬁrst1,last1,ﬁrst2,last2,result) constructs a sorted union in [result, …) of the elements from the

two ranges [ﬁrst1,last1) and [ﬁrst2,last2)

iter set_intersection(ﬁrst1,last1,ﬁrst2,last2,result) constructs a sorted intersection in [result, …) of the elements from

the two ranges [ﬁrst1,last1) and [ﬁrst2,last2)

iter set_difference(ﬁrst1,last1,ﬁrst2,last2,result) copies the elements of range [ﬁrst1,last1) which are not present in

[ﬁrst2,last2) to [result, …)

iter set_symmetric_difference(ﬁrst1,last1,ﬁrst2,last2,result) copies the elements of range [ﬁrst1,last1) not present in [ﬁrst2,

last2) and elements of range [ﬁrst2,last2) not present in range

[ﬁrst1,last1) to the range [result, …)

Note 1: operator< is used by default to compare; all also have a version taking a comparer to be used instead.

Note 2: the iterator returned by the functions above refers to the end of the constructed range (result).

TDDD38 APiC++ Standard Library – Algorithms 283

Heap algorithms

Example:

vector<int> v{ 8, 1, 4, 6, 5, 8, 3, 2, 7, 9 };

make_heap(begin(v), end(v)); // 9 8 8 7 5 4 3 2 6 1

v.push_back(10); // 9 8 8 7 5 4 3 2 6 1 10

push_heap(begin(v), end(v)); // 10 9 8 7 8 4 3 2 6 1 5

pop_heap(begin(v), end(v)); // 9 8 8 7 5 4 3 2 6 1 10

make_heap(ﬁrst,last) constructs a heap (max-heap) out of the range [ﬁrst,last)

push_heap(ﬁrst,last) the range [ﬁrst,last -1) must be a valid heap; the value to push must ﬁrst be placed in location

last-1; places the value in location last-1 into the resulting heap [ﬁrst,last)

pop_heap(ﬁrst,last) the range [ﬁrst,last) must be a valid heap; swaps the value in location ﬁrst with the value in location

last-1 and makes [ﬁrst,last -1) into a heap

sort_heap(ﬁrst,last) sorts the elements in the heap [ﬁrst,last); the range [ﬁrst,last) is thereafter not a heap; not stable

bool is_heap(ﬁrst,last) returns true if the elements in [ﬁrst,last) are heap ordered, otherwise false

iter is_heap_until(ﬁrst,last) returns the last iterator in [ﬁrst,last) for which the range [ﬁrst,iter) is heap ordered, otherwise last

Note 1: operator< is used by default to compare; all also have a version taking a comparer to be used instead.

Note 2:make_heap(), push_heap(), and pop_heap() are used in the implementation of priority_queue.

TDDD38 APiC++ Standard Library – Algorithms 284

Minimum and maximum operations

value min(a,b) returns the smaller value of a and b,a when a and b are equivalent

value min(initializer-list) returns the (leftmost) smallest value in initializer-list

value max(a,b) returns the larger value of a and b,a when a and b are equivalent

value max(initializer-list) returns the (rightmost) largest value in initializer-list

pair minmax(a,b) returns a pair with smallest of a and b ﬁrst

pair minmax(initializer-list) returns a pair with (leftmost) smallest and (rightmost) largest in initializer-list

iter min_element(ﬁrst,last) returns iterator to the (leftmost) smallest element in [ﬁrst,last)

iter max_element(ﬁrst,last) returns an iterator to the largest element in [ﬁrst,last); if several equivalently large elements,

an iterator to the ﬁrst of those

pair minmax_element(ﬁrst,last) returns a pair with iterators to the leftmost) smallest and the (rightmost) largest element in the

range [ﬁrst,last)

Note: operator< is used by default to compare; all also have a version taking a comparer to be used instead.

TDDD38 APiC++ Standard Library – Algorithms 285

Lexicographical comparison

Lexicographical comparison means

• if two sequences have the same number of elements and their corresponding elements are equivalent then neither sequence is

lexicographically less than the other

abcd1 < abcd2not true

abcd2 > abcd1not true

• if one sequence is a prefix of the other, then the shorter sequence is lexicographically less than the longer sequence

abc < abcde true

• otherwise the lexicographical comparison of two sequences yield the same result as the comparison of the first pair of elements that are

not equivalent

abcde < abcxetrue, because d < x

bool lexicographical_compare(ﬁrst1,last1,ﬁrst2,last2) returns true if the elements in [ﬁrst1,last1) are lexicographically less

than the elements in [ﬁrst2,last2)

Note: operator< is used by default to compare; there is also a version taking a comparer to be used instead.

TDDD38 APiC++ Standard Library – Algorithms 286

Permutation generators

• the next permutation is found by assuming that the set of all permutations are sorted with respect to operator<, or to a given comparer.

abc < acb < bac < bca < cab < cba

bool next_permutation(ﬁrst,last) takes the sequence [ﬁrst,last) and transforms it to the next permutation; returns true if such a

permutation exists, otherwise false

bool prev_permutation(ﬁrst,last) takes the sequence [ﬁrst,last) and transforms it to the previous permutation; returns true if

such a permutation exists, otherwise false

Note: operator< is used by default to compare; both also have a version taking a comparer, to be used instead

TDDD38 APiC++ Standard Library – Algorithms 287

Numeric algorithms

#include <numeric>

The Numerics library also have support for complex numbers,random number generation,numeric arrays, and C99 standard library

functionality.

Taccumulate(ﬁrst,last,init) initializes an accumulator with init, adds each value in [ﬁrst,last) to the accumulator

using operator+; returns accumulator value

Tinner_product(ﬁrst1,last1,ﬁrst2,init) initializes an accumulator with init; multiplies each pair of elements in [ﬁrst1,last1) and

[ﬁrst2,…) with each other and adds the result to the accumulator using operator+;

returns accumulator value

iter partial_sum(ﬁrst,last,result) assigns to every element in [result, …) the corresponding partial sum; (*ﬁrst),

(*ﬁrst + *(ﬁrst+1)), (*ﬁrst + *(ﬁrst+1) + *(ﬁrst+2)), …, using operator+;

returns past-the-end iterator for the resulting range

iter adjacent_difference(ﬁrst,last,result) the ﬁrst element in result is assigned to the ﬁrst value in [ﬁrst,last); each element in

[result+1,…) is assigned to the difference between the corresponding value in

[ﬁrst+1,last) and its previous value; returns past-the-end iterator for the resulting range.

iota(ﬁrst,last,value) assigns all elements in [ﬁrst,last) increasing values starting with value

Note 1: accumulate,inner_product, and partial_sum also have a version taking a binary operation to be used instead of operator+

Note 2:adjacent_difference also have a version taking a binary operation to be used instead of operator-

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 288

Function objects and lambda expressions

• function objects are objects of class type with the function call operator overloaded

–operator() must be a non-static member function

• important for effective use of the standard library

– enables algorithms to work with both ordinary functions and function objects

template<class InputIterator, class Function>

Function for_each(InputIterator first, InputIterator last, Function f);

for_each(begin(v), end(v), fun);

for_each(begin(v), end(v), fun_obj{});

– increases the expressive power of the library

• function objects are more flexible and powerful than functions

– can have data members to keep a state

– can have other member functions than operator()

– makes the resulting code more effective

transform(begin(v), end(v), std::negate<double>{}); // negate object can be inlined

•lambda expressions is a convenient way to create simple function objects inplace

– in many situations in C++98 where function objects was used, lambda expressions should be used in C++11

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 289

Regarding exam

• important to have a good understanding of function objects and lambda expressions

– know about the standard library function objects

– be able to define own function objects when needed

– sufficient practice in using function objects, both from standard library and your own, in combination with other components

– lambdas is often a good alternative to create simple function objects

•cplusplus.com Reference will be available at exam (web browser)

• see the course examination page for more information

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 290

Defining function object class types

• defining a simple, binary function object class

template<typename T>

struct logical_xor

{

constexpr bool operator()(const T& lhs, const T& rhs) const

{

return (lhs && !rhs) || (!lhs && rhs);

}

using first_argument_type = T;

using second_argument_type = T;

using result_type = bool;

};

–constexpr allows locical_xor be evaluated during compile-time, for appropriate arguments

–constexpr also implies inline

– the alias declarations (type definitions) are required by some library components, e.g., for declaring function parameters and other stuff

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 291

Using function objects

#include <iostream>

#include <functional>

#include <iterator>

#include <vector>

using namespace std;

int main()

{

vector<bool> b1{ false,false,true,true };

vector<bool> b2{ false,true,false,true };

vector<bool> b3;

transform(begin(b1), end(b1), begin(b2), back_inserter(b3), logical_xor<bool>{});

// b3 now contain b1 xor b2 (bit-wise)

return 0;

}

• the expression logical_xor<bool>{} creates a temporary object

– passed to the corresponding parameter, binary_op

– the function call in transform is

binary_op(*first1, *first2);

– can be either an ordinary function, a function object, or a lambda expression

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 292

Function objects with state

• Fibonacci number generator (F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 for n>1)

class Fibonacci

{

public:

Fibonacci() : Fn{0}, Fn_1{1} {}

unsigned long long int operator()() const

{

unsigned long long int next{Fn};

Fn = Fn_1;

Fn_1 = next + Fn;

return next;

}

private:

mutable unsigned long long int Fn;

mutable unsigned long long int Fn_1;

};

vector<unsigned long long int> v(20);

generate(begin(v), end(v), Fibonacci{}); // 0, 1, 1, 2, 3, 5, 8, …

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 293

Standard library function object classes

• the standard library declares function objects classes correspond to the arithmetic,comparison and logical operators.

plus addition x + y

minus subtraction x - y

multiplies multiplication x * y

divides division x / y

modulus reminder from integer division x % y

negate negation – performs -x

equal_to equality x == y

not_equal_to inequality x != y

greater greater-than x > y

less less-than x < y

greater_equal greater-or-equal x >= y

less_equal less-or-equal x <= y

logical_and logical conjunction x && y

logical_or logical disjunction x || y

logical_not logical negation !x

bit_and bit-wise and x & y

bit_or bit-wise or x | y)

bit_xor bit-wise xor x ^ y)

• makes it possible to pass “operators” as function arguments, and invoke them using ordinary function call syntax

transform(begin(v1), end(v1), begin(v2), back_inserter(v3), plus<int>{});

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 294

Standard library function object class definitions (1)

•std::plus is defined (default argument void is C++14)

template<typename T = void>struct plus

{

constexpr T operator()(const T& lhs, const T& rhs) const

{

return lhs + rhs;

}

using first_argument_type = T;

using second_argument_type = T;

using result_type = T;

};

– wrapper for operator+

– works for all types T having operator+ and copy construction

–implicit specialization (T = void) is illegal!

– explicit specialization for a specific type creates a simple instance with all T:s replaced with that type – plus<int>

•unary function objects should have the following two nested type definitions, instead of those three above

using argument_type = …;

using result_type = …;

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 295

Standard library function object class definitions (2)

•explicit (standard library) specialization for std::plus<void>(C++14)

template<> struct plus<void>

{

template <typename T, typename U>

constexpr auto operator()(T&& lhs, U&& rhs) const

-> decltype(std::forward<T>(lhs) + std::forward<U>(rhs))

{

return std::forward<T>(lhs) + std::forward<U>(rhs);

}

typedef unspecified is_transparent;

};

• parameter types and return types are deduced – arguments can be different, compatible types

• member type is_transparent indicates that this is a transparent function object

– accepts arguments of arbitrary types

– uses perfect forwarding

– avoids unnecessary copying and conversion when used in heterogeneous context, or with rvalue arguments

string a = "Hello ";

const char* b = "world";

cout << plus<>{}(a, b) << ’\n’;

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 296

Lambda expressions

Lambda expressions provide a quick way to create (simple) function objects at their point of use

array<int, 9> a{ 7, -2, -8, 4, 3, -5, 9, -1, 6 };

sort(begin(a), end(a), [](int x, int y) { return abs(x) < abs(y); });

•[] is the lambda introducer – introduces the declaration of a lambda expression

– can contain zero or more lambda captures

–[] only global and static entities can be referenced in the lambda – capture-less lambda expression

–[&] will capture any name used from the reaching scope implicitly by reference

–[=] will capture by value

–[x] explicitly capture the object named x, as read only

–[&x] will capture x by reference

–[=, &x] default capture is by value, x is captured by reference

–[this]will allow capturing members

•() contains ordinary parameter declarations

– can be left out if no parameters

•{} is a compound statement

• The return type is in the example above is implicitly deduced from the type of the returned value – it can be declared explicitly

[](int x, int y) -> bool { return abs(x) < abs(y); }

• there is more…

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 297

Closure objects

• The evaluation of a lambda expression creates a closure object

– a prvalue temporary

– behaves as a function object

•closure types are not specified but there are two easy ways to store closure objects

–auto

auto fun =[](int x, int y) { return abs(x) < abs(y); };

cout << fun(2, 1) << endl;

– template std::function (introduced later)

function<bool(int,int)> func = [](int x, int y) { return abs(x) < abs(y); };

cout << func(1, 2) << endl;

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 298

Non-generic lambda expressions and closure types

auto lambda = [](int a, int b) { return a < b; }

bool (*fp)(int,int) = lambda; // pointer-to-function conversion allowed for capture-less lambdas

The closure type for a non-generic lambda expression has a public operator() (1)

• same parameter types and return type as the lambda expression

•const if the lambda-expression’s parameter declaration clause is not followed by mutable

Capture-less lambdas have a pointer to function conversion (2)

• parameter types and return type are the same as for the function call operator

• returns the address of a function (3)that, when invoked, has the same effect as invoking the function call operator

class Closure {

public:

bool operator()(int a, int b) const { return a < b; } (1)

private:

static bool invoker_(int a, int b) { return a < b; } (3)

using fptr_t = bool (*)(int,int);

public:

operator fptr_t() const { return &invoker_; } (2)

};

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 299

Generic lambda expressions (C++14)

auto lambda = [](const auto& a, const auto& b) { return a + b; };

•auto indicates a generic lambda parameter

• closure operator() is a member template with one invented type template parameter for each occurrence of auto in the lambda

struct Closure

{

template<typename T, typename U>

auto operator()(const T& x, const U& y) const

{

return x + y;

}

};

–auto is used for the deduced return type of operator()

• conversion from a capture-less generic lambda to an appropriate pointer-to-function is allowed

long (*fp)(long,long) = lambda;

– parameter types and also return type may differ

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 300

Generic lambda expressions and closure types (C++14)

auto lambda = [](const auto& a, const auto& b) { return a + b; }

Complete closure type for a capture-less lambda expression:

struct Closure {

template<typename T, typename U>

auto operator()(const T& x, const U& y) const { return x + y; }

private:

template<typename T, typename U>

static auto invoker_(const T& x, const U& y) { return x + y; }

template<typename T, typename U> using fptr_t =

decltype(invoker_(declval<T>{}, declval<U>{})) (*)(T, U);

public:

template<typename T, typename U>

operator fptr_t<T, U>() const { return &invoker_; }

};

• function template declval returns an rvalue reference (T&& and U&&, respectively) without referring to any object

– references to (non-exciting) values of type T and U is used in the unevaluated call of invoker_ in decltype(…)

– the return type of fptr_t is deduced this way

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 301

Generic lambda expressions for function parameter packs (C++14)

The invented type template-parameter is a parameter pack if the corresponding parameter-declaration declares a function parameter pack.

auto lambda = [](auto&&... fpp){ … }; // function parameter pack

Closure type:

struct Closure {

public:

template<typename... Args> // parameter pack

auto operator()(Args&&... args) { … }

…

};

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 302

Function call syntax (1)

There are three ways to invoke a function f on a class object of type T:

f(x) Syntax #1: f is a normal function or function object and x is an object of type T

x.f() Syntax #2: f is a member function and x is an object of type T or a reference to an object of type T

p->f() Syntax #3: f is a member function and p is a pointer to an object of type T

Suppose we have a unary function that can operate on objects of type T, and a container with elements of type T

void fun(T& t);

vector<T> v;

• to apply fun to each object in the vector we can use the algorithm for_each

for_each(begin(v), end(v), fun); // Fine, for_each uses call syntax #1

•if fun instead is a member of T and we try the following, it will not work

for_each(begin(v), end(v), &T::fun); // Compile error, call syntax #2 required

• the third variant would be if the container stores pointers to T, and fun is a member of T, which also will not work

vector<T*> v;

for_each(begin(v), end(v), &T::fun); // Compile error, call syntax #3 required

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 303

Function call syntax (2)

• the implementation of for_each shows why the passed function f cannot be a member function, unless adapted

template<typename InputIterator, typename Function>

Function

for_each(InputIterator first, InputIterator last, Function f)

{

for (; first != last; ++first)

f(*first); // syntax #1

return f;

}

– works with both ordinary functions and function objects, but not for calling member functions

– all standard library algorithms use this normal function call syntax

– to be able to call a member function we must adapt the member function call syntax to ordinary function call syntax

x.memfun() –> f(x)

x.memfun(y) –> f(x, y)

• an ordinary function also need adaption, if a component require typedefs for argument type(s) and return type

–for_each does not

Before finding att how to solve this, lets find out what can be called…

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 304

Callable objects (1)

Something that can be called as a function.

• functions, function pointers, or function references

void fun(int x) { cout << x << endl; } // function

void (*fp)(int){ fun }; // function pointer (bound to fun above)

void (&fr)(int){ fun }; // function reference (bound to fun above)

fun(1); // 1

fp(2); // 2

fr(3); // 3

• objects implicitly converted to function pointer or to function reference

struct Type

{

using Fun_Ptr = void (*)(int); // alt. void (&)(int)

operator Fun_Ptr() const { return fun; } // conversion function – fun defined above

};

Type obj;

obj(4); // 4

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 305

Callable objects (2)

• function object

struct Fun_Obj_Type

{

void operator()(int x) const { cout << x << endl; }

};

Fun_Obj_Type obj;

obj(6); // 6

• closure object – behaves as a function object

auto f = [](int x){ cout << x << endl; };

f(7); // 7

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 306

Callable objects (3)

• pointer to non-static member function

struct Type

{

void mem_fun(int x) const { cout << x << endl; }

};

auto pmf = &Type::mem_fun; // void (Type::*pmf)(int)const = &Type::mem_fun;

Type obj;

(obj.*pmf)(8); // 8

• to point to a static member function, an ordinary function pointer must be used

struct Type

{

static void smem_fun(int x) { cout << x << endl; }

};

auto fp = &Type::smem_fun; // void (*fp)(int) = &Type::smem_fun;

Type obj;

(fp)(9); // 9

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 307

Function call wrappers

• negators

– function call wrappers to negate the result from calling a predicate function

–not1() helper function returning a function call wrapper for a unary predicate

–not2() helper function returning a function call wrapper for a binary predicate

• function argument binder

–bind() returns a function call wrapper which binds a callable object and arguments

• member function adaptor

–mem_fn() returns a function call wrapper to call a member function using normal function call syntax

• functions as first class citizens

–function is a polymorphic function wrapper that can store,copy, and call arbitrary callable objects

Note: These components are all defined using the new feature variadic template.

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 308

Negators (1)

•not1()

struct less_than_5 // a user defined unary predicate

{

constexpr bool operator()(int x) const { return x < 5; }

typedef int argument_type;

typedef bool return_type;

};

vector<int> v{ 1, 8, 3, 6, 10, 7, 5, 9, 2, 4 };

cout << count_if(begin(v), end(v), not1(less_than_5{})) << endl;

– the function object returned by not1() is applied to each element in v by transform

– calls less_than_5{} and returns the result negated

•not2()

transform(begin(v1), end(v1), begin(v2), begin(v3), not2(std::less<int>{}));

– the function object returned by not2() is applied to each pair of elements in v1 and v2 by transform

– calls std::less<int>{} and returns the result negated

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 309

Negators (2)

Utility function not1() takes a unary predicate Predicate and returns a function object of type unary_negate

template<typename Predicate>

unary_negate<Predicate> not1(const Predicate& pred)

{

return unary_negate<Predicate>(pred);

}

•Predicate must have nested type argument_type

template<typename Predicate> class unary_negate

{

public:

explicit unary_negate(const Predicate& x) : pred(x) {}

bool operator()(const typename Predicate::argument_type& x) const { return !pred(x); }

using argument_type = typename Predicate::argument_type;

using result_type = bool;

protected:

Predicate pred;

};

– defined by standard function objects

– defined by std::function when wrapping a unary or binary function

– defined by std::mem_fn when wrapping a unary or binary member function

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 310

Utility function std::bind

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

using namespace std::placeholders;

vector<int> v{ 0, 0, 1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9 }; // not necessarily sorted

• how many values in v are greater than 6?

auto n = count_if(begin(v), end(v), bind(greater<int>{}, _1, 6));

•bind is given a binary predicate, greater<int>{}, and the arguments to be bound

– the second parameter is bound to 6 – greater<int>()::operator(?, 6)

– argument for the first parameter is to be supplied when count_if calls the unary predicate created by bind

if (bind(greater<int>{}, _1, 6)(*it)) // effectively if (greater<int>{}(*it, 6))

– placeholder _1 refers to the first argument given in the call of the function call wrapper (*it)

– in this case there is only one argument – the only valid placeholder is _1

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 311

Utility function std::mem_fn

class C {

public:

C(int i = 0) : value_(i) {}

int times(int n) const { return n * value_; }

operator int() const { return value_; }

private:

int value_;

};

int a[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

vector<C> v(begin(a), end(a)); // initialize C objects with values from a

transform(begin(v), end(v), begin(a), ostream_iterator<int>{cout," "}, mem_fn(&C::times));

•mem_fn covers all member function call variants – the call to transform would be the same if v was storing pointers to C

vector<C*> v{ new C{1}, new C{2}, new C{3} };

• not restricted to member functions with just none or one parameter

• nested types

–result_type and argument_type are defined for member functions with no parameters

–result_type,first_argument_type, and second_argument_type are defined for member functions with one parameter

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 312

Template std::function (1)

•function wrapper class that can store, copy, and call arbitrary callable objects, such as

– normal functions

– function objects

– closure objects (acts as function objects)

– bind expressions

• allow functions to be first-class objects, that is, can be

– assigned

– passed by value

– returned by value

– stored in data structures

• exception bad_function_call is thrown by function::operator() when the function wrapper object has no target

class bad_function_call : public std::exception {

public:

bad_function_call() noexcept;

};

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 313

Template std::function (2)

function<double(double)> fn; // no function bound – throws bad_function_call, if called

fn = std::sinf; // normal function, signature float(float)

cout << fn(3.14) << endl;

// cos is overloaded in three version, for float, double, long double, type conversion required:

fn = static_cast<double(*)(double)>(std::cos);

cout << fn(3.14) << endl;

fn = [](double d) -> double { return 2 * d; }; // closure object (lambda expression)

cout << fn(3.14) << endl;

function<bool(int)> pred{ bind(std::greater<int>(), _1, 10) }; // bind expression

cout << boolalpha << pred(9) << ", " << pred(11) << endl;

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 314

Template std::function (3)

If instantiated for a unary or binary function:

• have type definitions for result type and argument type(s)

– for unary functions

argument_type

result_type

– for binary functions

first_argument_type

second_argument_type

result_type

• expected by some components

char* a[]{ "C++", "Ada", "Basic", "C", "C++", "Eiffel", "Java", "Python", "C++" }

count_if(begin(a), end(a), not1(function<int(const char*)>{bind(strcmp, "C++", _1)}))

–not1 require those types

–bind does not supply

– we can use function inbetween to supply the types

– a lambda expression is much simpler to use in many cases, e.g in this case:

count_if(begin(a), end(a), [](const char* s){ return !(strcmp("C++", s)); })

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 315

Template std::function (4)

Definition, parts of – just to give a hint on implementation:

template<class>class function; // primary – undefined

template <class R, class... ArgTypes> // result type, argument types

class function<R(ArgTypes...)> { // specialization for this function signature

public:

...

function();

function(const function&);

function(function&&);

...

function& operator=(const function&);

function& operator=(function&&);

...

template<class F> function(F); // constructor taking function

...

explicit operator bool() const noexcept;//true if *this has a target, otherwise false

Roperator()(ArgTypes...) const;//function call operator

...

};

TDDD38 APiC++ Standard Library – Function objects and lambda expressions 316

Summing up: Containers – Iterators – Algorithms – Functions objects

Designed for flexibility, extensibility, reuse and efficiency.

• uniform interfaces

– makes containers and iterators interchangeable

– many algorithms can be applied to a variety of structures

– makes learning and use easier

• iterators is the “glue” that allow for combining components

– algorithms operate on data through iterators

– containers provide iterators

– iterators can be bound to streams

– ordinary pointers can in many cases be used where iterators are expected

• function objects can be used for many different purposes

– algorithms and containers can take a function object to modify their behaviour

– function wrappers can be used to create more complicated operations from simple functions or function objects, e.g.

– function call adaptors

– reference wrapper

– use lambda expressions for simple function objects

• utilities for supporting rvalue references, move semantics, perfect forwarding, …

• the template mechanism is heavily used, supports together with e.g. variadic templates

– reusability, genericity, flexibility, efficiency