Kurt Nørmark
Department of Computer Science, Aalborg University

Abstract Previous lecture Index References Contents

...

C++ iterators are modelled as generalized pointers The pointer-related operators are used to manipulate iterators

Reference The C++ Prog. Lang. (3. edition): Page 57, 550

Reference The C++ Prog. Lang. (4. edition): Page 103, 953

References The iterator design pattern Collections in C#

The most important operators on iterators Access to the current element: * and -> Go to the next element: ++ Equality and inequality: == and != The start of a sequence s s.begin() The end of a sequence s s.end() Designates a non-existing one past the last element Iterator validity An iterator can only be used if it is valid An iterator is invalid if it is non-intialized, points to the end, if the container has been destroyed, resized, ...

Example uses of iterators - basic stuff Slide Contents Index References

We show a simple, practical example of iterators and their use

Program: A really simple example of iterators.

#include <iostream> #include <string> #include <vector> int main(){ using namespace std; vector<double> vd; for(int i = 1; i <= 10; i++) vd.push_back(i + i/10.0); auto it1 = vd.begin(); // auto covers the type vector<double>::iterator while(it1 != vd.end()){ cout << *it1 << " "; // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 ++it1; } }

Program: The same program using a reverse iterator.

// Reverse iterator - instead of forward iterator. #include <iostream> #include <string> #include <vector> int main(){ using namespace std; vector<double> vd; for(int i = 1; i <= 10; i++) vd.push_back(i + i/10.0); auto it1 = vd.rbegin(); while(it1 != vd.rend()){ cout << *it1 << " "; // 11 9.9 8.8 7.7 6.6 5.5 4.4 3.3 2.2 1.1 ++it1; } }

Program: Equivalent program with range-for - with iterators abstracted away - C++11.

// No iterators at all - range-for instead (C++11). #include <iostream> #include <string> #include <vector> int main(){ using namespace std; vector<double> vd; for(int i = 1; i <= 10; i++) vd.push_back(i + i/10.0); for(auto el: vd){ cout << el << " "; // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 } }

Different classifications of iterators Slide Contents Index References

C++ iterators are classified in a number of different dimensions - not always completely orthogonal Despite being heavily classified, the iterator types are not organized in a class hierarchy

Reference The C++ Prog. Lang. (3. edition): Page 551, 553, 557, 561

Reference The C++ Prog. Lang. (4. edition): Page 953

Const and non-const iterators A const iterator cannot be used for modification of the designated element Checked and non-checked iterators A checked iterator enforces range checking Reverse and 'normal non-reverse' iterators For a reverse iterator, ++ moves backward Insert iterators Inserting - instead of overwriting - elements in a container Input, output, forward, bidirectional, random-access iterators Input and output iterators have relative few operators defined Random access iterators have many operators defined Next slide

Categories of iterators Slide Contents Index References

Tabular overview of the five catetories at the top of page 956 in The C++ Prog. Lang. (4. edition) The classification below shows operations that can be implemented efficiently - O(1)

Reference The C++ Prog. Lang. (3. edition): Page 550

Reference The C++ Prog. Lang. (4. edition): Page 955

Reference Iterator categories at cplusplus.com

All iterators ++, * Input iterator p Can read the current element (at least once) by x = *p Cannot necessarily write to current element by *p = x Other operators: ==, != Output iterator p Can write (once) into the container with *p = x Cannot necessarily read the current element by x = *p Forward Like input and output iterator Can read and write repeatedly Bidirectional Like forward iterator -- applies Random-access Like bidirectional iterator Can add and subtract integers to/from iterators Can compare iterators with <, <=, >, and >=

The categories are not represented by inheritance, but they appear in iterator tags types (page 956 The C++ Prog. Lang. (4. edition)) - used for convenient functions overloding The distance between two iterators can be calculated for most iterators, simply by advancing the first until it meets the other

Insert iterators Slide Contents Index References

Many algorithms overwrite existing elements It is also necessary to be able to insert new elements Insertion is normally done by the container operations push_back(), push_front(), and insert() Insertion can also be accomplished via insert-iterators, which are output iterators Using these, assignments are used for insertion of new elements Insertion iterators can be created by the template (factory) functions back_inserter, front_inserter, and inserter.

Reference The C++ Prog. Lang. (3. edition): Page 555

Reference The C++ Prog. Lang. (4. edition): Page 963

Program: Output insert-iterators and factory functions that create such iterators.

// Demonstration of output iterators and inserters (C++11, due to >> in template notation, and not > >). #include <iostream> #include <string> #include <vector> #include <list> template <typename CONT> void print_seq(const CONT &v); int main(){ using namespace std; // Make and initialize a vector: vector<double> vd; for(int i = 1; i <= 10; i++) vd.push_back(i + i/10.0); typedef back_insert_iterator<vector<double> > back_ins_vec_it; // BACK INSERT ITERATOR: // Make back insert iterator (an output iterator) - using a factory function on the container // The back inserter overloads the assignment operator, see The C++ Programming Language 4ed, page 964. back_ins_vec_it bii = back_inserter(vd); *bii = 20; *bii = 21; print_seq(vd); // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 20 21 // FRONT INSERT ITERATOR (cannot be used on vector) typedef front_insert_iterator<list<double>> front_ins_list_it; list<double> ld; for(int i = 1; i <= 10; i++) ld.push_back(i + i/10.0); front_ins_list_it fii = front_inserter(ld); *fii = -3; *fii = -5.7; print_seq(ld); // -5.7 -3 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 // INSERT ITERATOR typedef insert_iterator<list<double>> ins_list_it; typename list<double>::iterator ins_begin = ld.begin(); ++++++ins_begin; // Advance the iterator 3 positions - confusing use of prefix increment. // An inserter that starts inserting at ins_begin ins_list_it ili = inserter(ld, ins_begin); *ili = 100; *ili = 101; print_seq(ld); // -5.7 -3 1.1 100 101 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 } // Print the sequence v on standard output: template <typename CONT> void print_seq(const CONT &v){ typename CONT::const_iterator it = v.begin(); while(it != v.end()){ std::cout << *it << " "; it++; } std::cout << std::endl; }

Program: Same program - simplified in various ways in C++11.

// C++11 version - Still demonstration of output iterators and inserters. // Takes advantages of auto. Uses next instead of chaining of prefix increment. #include <iostream> #include <string> #include <vector> #include <list> #include <iterator> // std::next template <typename CONT> void print_seq(const CONT &v); int main(){ using namespace std; // Make and initialize a vector: vector<double> vd; for(int i = 1; i <= 10; i++) vd.push_back(i + i/10.0); // BACK INSERT ITERATOR: // Make back insert iterator (an output iterator). // The back inserter overloads the assignment operator, // see The C++ Programming Language 3ed, page 556. auto bii = back_inserter(vd); *bii = 20; *bii = 21; print_seq(vd); // 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 20 21 // FRONT INSERT ITERATOR (cannot be used on vector) list<double> ld; for(int i = 1; i <= 10; i++) ld.push_back(i + i/10.0); auto fii = front_inserter(ld); *fii = -3; *fii = -5.7; print_seq(ld); // -5.7 -3 1.1 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 // INSERT ITERATOR (on the list ld. Will also work on the vector vd). auto ins_begin = ld.begin(); auto pos = next(ld.begin(), 3); // Advance the iterator 3 positions. // An inserter that starts inserting at ins_begin auto ili = inserter(ld, pos); *ili = 100; *ili = 101; print_seq(ld); // -5.7 -3 1.1 100 101 2.2 3.3 4.4 5.5 6.6 7.7 8.8 9.9 11 } // Print the sequence v on standard output: template <typename CONT> void print_seq(const CONT &v){ typename CONT::const_iterator it = v.begin(); while(it != v.end()){ std::cout << *it << " "; it++; } std::cout << std::endl; }

Reference insert_iterator at cplusplus.com

Be sure to use the online documentation of the STL container library http://www.cplusplus.com/reference/stl/ Lots of useful examples

STL - Standard Template Library The template library for containers and iterators

Overview of containers Slide Contents Index References

Three kinds of containers in the C++ template library The most important container types - not a complete listing

Reference The C++ Prog. Lang. (3. edition): Page 52-56

Reference The C++ Prog. Lang. (4. edition): Page 101

Reference Vectors in C++

Sequences vector, list, forward_list, deque stack, queue, priority_queue via adaptors on other sequences - restricting interfaces Associative containers Based on balanced trees:   map, multimap, set, multiset Based on hash tables:   unordered_map, unordered_multimap, unordered_set, unordered_multiset Almost containers string, valarray, bitset, and built-in arrays array (C++11) Contains it elements directly (not a handle to its elements) Fixed size - the size is a constant expression Move is not more efficient than copy

Reference The C++ Prog. Lang. (4. edition): array. Page 974

References vector at cplusplus.com list at cplusplus.com forward_list at cplusplus.com deque at cplusplus.com stack at cplusplus.com queue at cplusplus.com priority_queue at cplusplus.com map at cplusplus.com multimap at cplusplus.com set at cplusplus.com multiset at cplusplus.com array at cplusplus.com - C++11

Common properties of containers Slide Contents Index References

Overall properties of STL containers

Reference The C++ Prog. Lang. (3. edition): Page 441

Reference C# counterpart - Collection class hierarchy

No common base class for the standard containers However, each container provides standard operations with standard names and semantics Emphasis on iterators Different kinds of iterators are not related by a common base class Non-intrusive containers Elements of containers do no need to be instances of certain classes An object is not aware of being an element of a particular container Values of built-in types can be elements in a container Standard containers rely heavily on templates Template specializations provide shared implementations for pointers to elements

A priority queue example Slide Contents Index References

A priority queue is a heap top() returns the largest element in the queue We show an example of a priority queue of points, which is built on top of double-ended queue A priority queue relies on a comparison function - in our case the overloaded   <   operator in class Point A priority queue is an adoptor of an underlying container - defaulted to vector - in the example below we use deque

Reference The C++ Prog. Lang. (3. edition): Page 478

Reference The C++ Prog. Lang. (4. edition): Page 923

References priority_queue at cplusplus.com deque at cplusplus.com

Program: Illustration of priority_queue<Point, deque<Point> >.

#include <iostream> #include <string> #include <queue> #include <list> #include "point.h" int main(){ using namespace std; priority_queue<Point, deque<Point> > point_queue; // A priority queue of points. // Built on a deque<Point>. Point p1(1,2), p2(-5,27), p3(3,4), p4(7,8), p5(-3,-4), p6(0,0); point_queue.push(p1); point_queue.push(p2); point_queue.push(p3); point_queue.push(p4); point_queue.push(p5); point_queue.push(p6); while (not (point_queue.empty())){ cout << point_queue.top() << " "; // (-5,27) (7,8) (3,4) (1,2) (0,0) (-3,-4) point_queue.pop(); } }

Program: Class point with an overloaded operator<.

class Point { private: double x, y; public: Point(double, double); Point(); double getx () const; double gety () const; void move(double, double); double distance_to(Point); friend bool operator< (const Point&, const Point&); }; std::ostream& operator<<(std::ostream&, const Point&);

Program: The implementation of class Point and in particular operator<.

#include <cmath> #include <iostream> #include "point.h" Point::Point(double x_coord, double y_coord): x(x_coord), y(y_coord){ } Point::Point(): x(0.0), y(0.0){ } double Point::getx () const{ return x; } double Point::gety () const{ return y; } void Point::move(double dx, double dy){ x += dx; y += dy; } double Point::distance_to(Point p){ return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); } // funny implementation - compares sum of x and y coordinates bool operator<(const Point& p, const Point& q){ return p.x + p.y < q.x + q.y; } std::ostream& operator<<(std::ostream& s, const Point& p){ return s << "(" << p.getx() << "," << p.gety() << ")" ; }

A map example Slide Contents Index References

We show a simple example of the use of the map standard container An example taken from The C++ Prog. Lang. (3. edition) page 483

Reference map at cplusplus.com

Program: Illustration of the map standard container.

// Reproduced from The C++ Programming Language, 3ed, page 483. // Read strings and counts from standard input, and keep track of the // sum for a particular string in the map. Also calculate the final total. #include <iostream> #include <string> #include <map> using namespace std; void readitems(map<string, int> &m){ string word; int val; while (cin >> word >> val) m[word] += val; // Relies on the default map value initialization. } int main(){ map<string,int> str_count; // All values in the map are initialized to 0. readitems(str_count); int total = 0; using CI = map<string,int>::const_iterator; // C++11 // Accumulating total - and printing - via use of const interator: for(CI it = str_count.begin(); it != str_count.end(); ++it){ pair<string,int> element = *it; // Emphasizing that keys and values are grouped in a pair. total += element.second; cout << element.first << "\t\t" << element.second << endl; } cout << "-------------------------\ntotal\t\t" << total << endl; }

Program: Alternative version - using range-for for traveral of the map.

// Alternative version where the map is traversed with a range-for statement. // Read strings and counts from standard input, and keep track of the // sum for a particular string in the map. Also calculate the final total. #include <iostream> #include <string> #include <map> using namespace std; void readitems(map<string, int> &m){ string word; int val; while (cin >> word >> val) m[word] += val; // Relies on the default map value initialization. } int main(){ map<string,int> str_count; // All values in the map are initialized to 0. readitems(str_count); int total = 0; // Accumulating total - and printing - via use of range-for: for(auto element: str_count){ // C++11 total += element.second; cout << element.first << "\t\t" << element.second << endl; } cout << "-------------------------\ntotal\t\t" << total << endl; }

Program: Sample program input.

abba 7 beatles 8 abba 3 stones 10 elvis 12 cash 13 abba 5 beatles 12 cash 10 abba 7

Reference Stream state

Program: Program output - as produced on the input from above.

abba 22 beatles 20 cash 23 elvis 12 stones 10 ------------------------- total 87

Container member types Slide Contents Index References

Each standard container defines a number of types - via using type aliases These type definitions serve as standard type names that apply for all container types

Reference The C++ Prog. Lang. (3. edition): Page 443, 462

Reference The C++ Prog. Lang. (4. edition): Page 896

Reference The C++ Prog. Lang. (4. edition): using type alias. Page 167

Examples of member types defined in standard containers, such as value_type iterator, const_iterator, reverse_iterator, const_reverse_iterator size_type, difference_type pointer, const_pointer reference, const_reference

Program: Illustration of the use of member types for a list of chars.

// Examples of member types of list<T>. #include <iostream> #include <string> #include <list> int main(){ using namespace std; list<char> lc; lc.push_back('a'); lc.push_back('b'); lc.push_back('e'); list<char>::value_type x = 'c'; // A complicated way to denote the type char list<char>::iterator lc_it = lc.begin(); // The iterator type of list<char> list<char>::size_type sz = lc.size(); // The size type of list<char> }

Program: Same program - now with use of typename as prefix of 'nested dependent type names'.

// Using typename to emphasize that a dependent name (a name that depends on a template parameter) is a type name. #include <iostream> #include <string> #include <list> int main(){ using namespace std; list<char> lc; lc.push_back('a'); lc.push_back('b'); lc.push_back('e'); typename list<char>::value_type x = 'c'; // A complicated way to denote the type char typename list<char>::iterator lc_it = lc.begin(); // The iterator type of list<char> typename list<char>::size_type sz = lc.size(); // The size type of list<char> }

In C++11 it is often possible to avoid use of container member type names - because auto can be used instead

Member types - ambiguities Slide Contents Index References

Some ambiguities may occur - in part related to uses of member types of containers

Program: Illustration of a couple of ambiguities.

// Example of an ambiguity: #include <vector> int x = 5; template<typename T>double f(){ // The name iterator depends on T (it is a dependent name, page 746 (4ed)). T::iterator *x; // Ambiguity 1: // T::iterator multiplied by x OR // x declared as a pointer to the type named T::iterator // ... } int main(){ f<std::vector<double>>(); // Ambiguity 2: // >> shift right OR // end of nested template argument list }

Program: Compiler error messages.

ambiguities-1.cpp: In function 'int main()': ambiguities-1.cpp:13:23: error: '>>' should be '> >' within a nested template argument list ambiguities-1.cpp: In function 'double f() [with T = std::vector<double>]': ambiguities-1.cpp:13:26: instantiated from here ambiguities-1.cpp:6:3: error: dependent-name 'T:: iterator' is parsed as a non-type, but instantiation yields a type ambiguities-1.cpp:6:3: note: say 'typename T:: iterator' if a type is meant

Program: Ambiguities resolved.

// Ambiguities resolved. #include <vector> int x = 5; template<typename T>double f(){ typename T::iterator *x; // Notice use of typename: // Means that the dependent name is a typename. // ... } int main(){ f<std::vector<double> >(); // >> is written > > // Not necessary in C++11. }

Program: An alternative resolution of the ambiguity .

// An alternative approach: using a 'using type alias'. C++11 #include <vector> int x = 5; template<typename T>double f(){ using it = typename T::iterator; // a 'using type alias' it *x; // A simpel and plain declaration: x is of type it* // ... } int main(){ f<std::vector<double>>(); // >> is OK in C++11 }

A vector specialization: vector<bool> Slide Contents Index References

vector<bool> is a specialization of vector<T> that provides for compact representation of boolean vectors vector<bool> complements the fixed-typed container bitset<N>

Reference The C++ Prog. Lang. (3. edition): Vector<bool>. Page 548

Reference The C++ Prog. Lang. (4. edition): Vector<bool>. Page 981-982

Program: Illustration of the use of vector<bool>.

#include <iostream> #include <vector> int main(){ using namespace std; vector<bool> vb; vb.push_back(true); vb.push_back(true); vb.push_back(false); vb.push_back(false); vb.push_back(false); vb.push_back(true); for(auto be: vb) cout << be; // 110001 }

Program: Another slightly more complicated (almost) equivalent program.

#include <iostream> #include <vector> int main(){ using namespace std; vector<bool> vb; vb.push_back(true); vb.push_back(true); vb.push_back(false); vb.push_back(false); vb.push_back(false); vb.push_back(true); typedef vector<bool>::const_iterator VBI; cout << boolalpha; // Use a stream manipulator, see The C++ PL (4ed) page 1094. for(VBI it = vb.begin(); it != vb.end(); it++) cout << *it; // truetruefalsefalsefalsetrue }

Be sure to use the online documentation of the algorithms library http://www.cplusplus.com/reference/algorithm/ Lots of useful examples

Overview of Algorithms Slide Contents Index References

The C++11 Standard Library contains approximately 80 standard algorithms Most of these represent simple ideas, as opposed to algorithms in an Algorithms and Data Structure course tradition The design here is not on the desing of algorithms or even on the use of any but the simplest and most obvious algorithms, §18.2 in The C++ Prog. Lang. (3. edition)

Reference The C++ Prog. Lang. (3. edition): Page 508

Reference The C++ Prog. Lang. (4. edition): Page 927

Nonmodifying sequence algorithms for-each(): Applies a function on each element of a sequence find(): Find the first element that compares equal to a given value. Return iterator to element find_if(): Find the first element that satisfies a given predicate. Return iterator to element Modifying sequence algorithms transform(): Applies a function on each element, and writes the result into another container. replace(): Replace elements that satisfies a predicate with a another value Sorting and searching algorithms (on sequences): sort binary_search Set algorithms Heap algorithms make_heap, push_heap, and pop_heap Min and max algorithms The naive min and max functions max_element and min_element: Generalization to sequences of elements Permutation algorithms next_permutation and prev_permutation: Systematic creation of permutations of a sequence Numeric algorithms

Principles used for algorithms Slide Contents Index References

We list a number of principles (ideas and concepts) which are typically used for a number of standard algorithms

Generalization by function parameters Insight from higher-order functions Spawns some work on C++ function objects, §19.2.2 (4ed) In part, due to the lack of lambda expressions until C++11 A sequence is defined by two iterators Beginning at the first element Ended by the one-beyond-the-last element Failure to find an element in a sequence Return the (off by one) end of sequence iterator The time complexities of the algorithms are specified by the C++ standard

Reference Example: binary_search

The for-each algorithm Slide Contents Index References

In C++ for-each is an algorithm, not a control structure like foreach in C# C++11 has introduced the 'range-for loop' similar to foreach in C#

Program: A possible implementation of the for-each algorithm.

// A possible definition of the for_each function template. template <typename InputIt, typename Function> Function for_each(InputIt first, InputIt last, Function f){ while (first != last) f(*first++); // Notice the use of operator() on f return f; }

Reference C Operator priorities

Program: Implementation and sample use of for-each on an C-style array.

// A reproduction of the for-each algorithm, and a sample use on a C-style array. #include <iostream> #include <string> // A possible definition of the for_each function template. template <typename InputIt, typename Function> Function for_each(InputIt first, InputIt last, Function f){ while (first != last) f(*first++); // Notice the use of operator() on f return f; } void print_element(const int &i){ std::cout << i << std::endl; } int main(){ int a[] = {7,9,8,1,-1}; // The two first parameters are iterators: for_each(a, a+3, print_element); // 7, 9, 8 std::cout << std::endl; // Same with a lambda expression. for_each(a, a+3, [](const int &el){std::cout << el << std::endl;}); // 7, 9, 8 }

Program: Implementation and sample use of for-each on a list of integers.

// Same defintion of for-each. Use of the algorithm on a list of integers: list<int>. #include <iostream> #include <string> #include <list> // A possible definition of the for_each function template. template <typename InputIt, typename Function> Function for_each(InputIt first, InputIt last, Function f){ while (first != last) f(*first++); return f; } void print_element(int i){ std::cout << i << std::endl; } int main(){ using namespace std; list<int> lst; lst.push_back(7); lst.push_back(9); lst.push_back(8); lst.push_back(1); lst.push_back(-1); // The two first parameters are iterators: for_each(lst.begin(), lst.end(), print_element); // 7 9 8 1 -1 }

Program: Use of std::for-each instead of our own definition of for-each.

// Use the Standard Libaray for-each instead of your own version of it. #include <iostream> #include <string> #include <list> #include <algorithm> void print_element(int i){ std::cout << i << std::endl; } int main(){ std::list<int> lst; lst.push_back(7); lst.push_back(9); lst.push_back(8); lst.push_back(1); lst.push_back(-1); // The two first parameters are iterators: std::for_each(lst.begin(), lst.end(), print_element); // 7 9 8 1 -1 }

A Stroustrup advice: "In general, before using for_each(), consider if there is a more specialized algorithm that would do more for you" Such as find() or accumulate() Observation about the return-value of for_each The function f is returned. Later we will see an example where this is convenient

Function objects Slide Contents Index References

A function object (or function-like object or functor) is an object for which an application operator, operator(), has been defined A function object can be called - pretending that it is a function

Reference The C++ Prog. Lang. (3. edition): Page 514-515, 287

Reference The C++ Prog. Lang. (4. edition): Page 80-82, 551

Reference Lambda expressions

Program: Class Point with overloadings of the application operator.

// Class Point becomes a function object, because it can be called as a function. // Class Point with two overloads of the function call operator, operator(). class Point { private: double x, y; public: Point(double, double); Point(); double getx () const; double gety () const; void move(double, double); double distance_to(Point); double operator()(int) const; double operator()(Point) const; }; std::ostream& operator<<(std::ostream&, const Point&);

Program: Definition of funny Point application operators.

// Member definitions for class Point, including the definition of the funny Point function call operators. #include <cmath> #include <iostream> #include "point.h" Point::Point(double x_coord, double y_coord): x{x_coord}, y{y_coord}{ } Point::Point(): x{0.0}, y{0.0}{ } double Point::getx () const{ return x; } double Point::gety () const{ return y; } void Point::move(double dx, double dy){ x += dx; y += dy; } double Point::distance_to(Point p){ return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); } double Point::operator()(int i) const{ return x + y + 2*i; } double Point::operator()(Point otherP) const{ return x*otherP.x + y*otherP.y; } std::ostream& operator<<(std::ostream& s, const Point& p){ return s << "(" << p.getx() << "," << p.gety() << ")" ; }

Program: Sample uses of the application operators - Funny and artificial.

// Sample uses of the Point function call operators. #include <iostream> #include <string> #include "point.h" int main(){ using namespace std; Point p{1,2}, q{3,4}; double d, e; d = p(5); // Use the application operator on p, pass 5 as the int parameter. // Pretends that p is a function. // 1 + 2 + 2*5 cout << "d: " << d << endl; // 13 e = p(q); // Another overload of the application operator. // Applies p on q // Pretends, in a similar way, that p is a function. // 1*3 + 2*4 cout << "e: " << e << endl; // 11 }

As another example, we provide access to x and y in point p via p(1) and p(2)

Program: Class Point with another overloading of the application operator.

// Another example - another overload of the Point application operator, as applied on int. class Point { private: double x, y; public: Point(); Point(double); Point(double, double); double getx () const; double gety () const; void move(double, double); double distance_to(Point); double operator()(int i) const; // Accesses x or y }; class IndexProblem{}; std::ostream& operator<<(std::ostream&, const Point&);

Program: Definition of then Point application operator.

// Definition of class Point members - including the call operator that accesses x or y. #include <cmath> #include <iostream> #include "point.h" Point::Point(): x{0.0}, y{0.0}{ } Point::Point(double x_coord): x{x_coord}, y{0}{ } Point::Point(double x_coord, double y_coord): x{x_coord}, y{y_coord}{ } double Point::getx () const{ return x; } double Point::gety () const{ return y; } void Point::move(double dx, double dy){ x += dx; y += dy; } double Point::distance_to(Point p){ return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); } double Point::operator()(int i) const{ if (i == 1) return x; else if (i == 2) return y; else throw IndexProblem(); } std::ostream& operator<<(std::ostream& s, const Point& p){ return s << "(" << p.getx() << "," << p.gety() << ")" ; }

Program: Sample uses of the application operators - slightly more realistic.

// Sample uses of the operator()(int). #include <iostream> #include <string> #include "point.h" int main(){ using namespace std; Point p, q(1), // less confusing if {} initializer r(3,4); // syntax is used here try{ cout << "p(1): " << p(1) << endl; // 0 cout << "p(2): " << p(2) << endl; // 0 cout << "q(1): " << q(1) << endl; // 1 cout << "q(2): " << q(2) << endl; // 0 cout << "r(1): " << r(1) << endl; // 3 cout << "r(2): " << r(2) << endl; // 4 cout << "p(3): " << p(3) << endl; // Throws IndexProblem exception. } catch (IndexProblem){ cout << "Recovering from indexing problem" << endl; } }

Using the sort algorithm Slide Contents Index References

We adapt an example program that uses the sort algorithm from cplusplus.com

Reference sort at cplusplus.com

Program: Two overloads of the sort function template.

template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Program: Sorting a vector of integers.

// sort algorithm example - adapted from www.cplusplus.com #include <iostream> // std::cout #include <algorithm> // std::sort #include <vector> // std::vector template<typename Cont> void print_container(Cont c); bool myfunction (int i,int j) { return (i<j); } struct myclass { bool operator() (int i,int j) { return (i<j);} }; int main () { int myints[] = {32,71,12,45,26,80,53,33}; std::vector<int> myvector (myints, myints+8); print_container(myvector); // 32 71 12 45 26 80 53 33 // using default comparison (operator <): std::sort(myvector.begin(), myvector.begin()+4); print_container(myvector); // (12 32 45 71)26 80 53 33 // using function for comparison: std::sort(myvector.begin()+4, myvector.end(), myfunction); print_container(myvector); // 12 32 45 71(26 33 53 80) // using an object of type myclass for comparison: std::sort(myvector.begin(), myvector.end(), myclass{}); print_container(myvector); // 12 26 32 33 45 53 71 80 // using a lambda expression for comparison - descending order! std::sort(myvector.begin(), myvector.end(), [](const int &i, const int &j){return j < i;}); print_container(myvector); // 80 71 53 45 33 32 26 12 return 0; } template<typename Cont> void print_container(Cont c){ for(auto el: c) std::cout << ' ' << el; std::cout << std::endl; }

Program: Program output.

32 71 12 45 26 80 53 33 12 32 45 71 26 80 53 33 12 32 45 71 26 33 53 80 12 26 32 33 45 53 71 80 80 71 53 45 33 32 26 12

An example of for-each and function objects Slide Contents Index References

An sample use of for-each() to find out if a list is sorted Initial discussions of possible solutions to this simple problem

Program: A possible use of for-each to solve this problem.

// Example from C++ in a Nutshell (2003), page 337-338. Slightly revised. Rather tricky. #include <iostream> #include <algorithm> #include <list> // An object of an instance of Is_sorted is used as a function // with state, corresponding to the three data members. template<typename T> class Is_sorted{ private: bool first_time, // true when applied first time sorted; // true as along as prefix is sorted T prev_item; // the previous item public: Is_sorted(): first_time{true}, sorted{true}{ } void operator() (const T& item){ // Called for each item in the list. if (first_time) // If two elements out of order is met, sorted becomes false. first_time = false; else if (item < prev_item) // two elements out of order. sorted = false; prev_item = item; } operator bool(){return sorted;} }; int main(){ using namespace std; // Make a list with some elements: list<int> lst{3, 15, 9, 11, 13, 15, 21}; // Make an instance of the class IsSorted: Is_sorted<int> is_sorted{}; // Use for_each to find out if lst is sorted: if(for_each(lst.begin(), lst.end(), is_sorted)) // for_each returns the object is_sorted cout << "The list lst is sorted" << endl; // via the boolean conversion operator. else cout << "The list lst is NOT sorted" << endl; // The given list is not sorted. }

Observations Use of objects as functions via an overload of the application operator A function surrounded by private, mutable state Use of the returned value from for-each

Program: Following the advice: Solve the problem with a more appropriate algorithm.

// A more straightforward solution - using the adjent_find algorithm #include <iostream> #include <algorithm> #include <list> int main(){ using namespace std; list<int> lst{3, 15, 9, 11, 13, 15, 21}; if(adjacent_find(lst.begin(), lst.end(), greater<int>{}) != lst.end()) // find a pair of elements out of order. cout << "The list lst is NOT sorted" << endl; // greater is shown in the next program. else cout << "The list lst is sorted" << endl; }

Observation greater is a wrapper around the > operator, §33.4 (4ed)

Program: Possible definitions of the type greater and its base class.

template <class Arg1, class Arg2, class Result> struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; }; template <class T> struct greater : binary_function <T,T,bool> { bool operator() (const T& x, const T& y) const {return x>y;} };

Use of function objects in STL Slide Contents Index References

Operators are not functions - operators need some wrapping to be applicable as function parameters to algorithms. Binders, Adapters and Negaters.

Reference The C++ Prog. Lang. (3. edition): Page 518

Reference The C++ Prog. Lang. (4. edition): Page 966 ff.

Wrapping operator predicates Predicates such as ==, < and > Available as equal_to, less, and greater - see §33.4 (4ed) Wrapping arithmetic operators Operators such as + and - Available as plus and minus, see §33.4 (4ed) Binding one argument of a two argument function Currying as of functional programming Allowing a member function to be used as a function mem_fun, applied on a member pointer, serves as a function that can called on an object Negating a predicate

Adapter examples Slide Contents Index References

We show a couple of example of Adapters Adaption of an operator (+) and adaptation of a member function (print in Point)

Program: An illustration of plus<double>.

// A program that illustrate the difference between the plus operator // and a function of two arguments that adds the arguments together. #include <iostream> #include <list> #include <numeric> // accumulate #include <functional> // plus int main(){ using namespace std; // We make a list of doubles, and insert some numbers in the list: list<double> lst; for(int i = 1; i <= 10; i++) lst.push_back(i); // 1, 2, ..., 10 // An operator is NOT a first class entity in C++: double res = accumulate(lst.begin(), lst.end(), 0.0, + ); // error: expected primary-expression .... // We must make an object which serves as a binary plus function: double res = accumulate(lst.begin(), lst.end(), 0.0, plus<double>{}); cout << "The plus accumulation is: " << res << endl; // 55 }

Program: A possible definition of plus.

// We show a possible definition of plus, as a struct with an // application operator. The binary_function is not strictly necessary. // Notice that the struct plus is derived from binary_function (inheritance). // binary_function only contains a few typedefs. #include <iostream> #include <list> #include <numeric> // accumulate #include <functional> // binary_function template <class T> struct plus: public std::binary_function<T,T,T> { T operator() (const T& x, const T& y) const {return x+y;} }; int main(){ std::list<double> lst; for(int i = 1; i <= 10; i++) lst.push_back(i); // 1, 2, ..., 10 // We must make an object which serves as a binary plus function: double res = std::accumulate(lst.begin(), lst.end(), 0.0, plus<double>{} ); std::cout << "The plus accumulation is: " << res << std::endl; // 55 }

Program: Another definition of plus - as a function template.

// We show another definition of plus, as a function template. // A rather direct and more down-to-earth approach. #include <iostream> #include <list> #include <numeric> // accumulate #include <functional> // binary_function template<typename T> T plus_fn(T a, T b){ return a + b; } int main(){ std::list<double> lst; for(int i = 1; i <= 10; i++) lst.push_back(i); // 1, 2, ..., 10 // We must make an object which serves as a binary plus function: double res = std::accumulate(lst.begin(), lst.end(), 0.0, plus_fn<double>); std::cout << "The plus accumulation is: " << res << std::endl; // 55 }

Program: Yet another alternative where a lambda expression is used.

// We show how a lambda expression can be used instead. #include <iostream> #include <list> #include <numeric> // accumulate #include <functional> // binary_function int main(){ std::list<double> lst; for(int i = 1; i <= 10; i++) lst.push_back(i); // 1, 2, ..., 10 // We can also supply a lambda expression. double res = std::accumulate(lst.begin(), lst.end(), 0.0, [](const double& d, const double& e){return d + e;}); std::cout << "The plus accumulation is: " << res << std::endl; // 55 }

Program: Illustration of member function adaptions.

// A new example: Illustration of member function adaptions. // We cannot just pass a pointer to a member function to for_each and // similar functions, because we miss the target. And we cannot easily // make use of the .* operator to bind the target object. #include <iostream> #include <string> #include <list> #include <algorithm> #include "point.h" void f(std::list<Point> &lp){ using namespace std; // error: must use .* or ->* to call pointer-to-member function: for_each(lp.begin(), lp.end(), &Point::print); // Adapting the member function pointer to print, such that it becomes // a function that can be called by for_each: for_each(lp.begin(), lp.end(), mem_fun_ref(&Point::print)); } int main(){ using namespace std; Point p1(1,2), p2(-5,27), p3(3,4), p4(7,8), p5(-3,-4), p6(0,0); list<Point> point_list; point_list.push_back(p1); point_list.push_back(p2); point_list.push_back(p3); point_list.push_back(p4); point_list.push_back(p5); point_list.push_back(p6); f(point_list); }

Program: The definition of Point - point.h.

class Point { private: double x, y; public: Point(double, double); Point(); double getx () const; double gety () const; void move(double, double); double distance_to(Point); void print(); };

Generic programming in C++ emphasizes programming of algorithms at a high abstraction level using templates

Reference The C++ Prog. Lang. (4. edition): Page 700

A programming paradigm - or a design philosophy A generic program will work on a number of different types, which are not related by subtype relationships Generic programming emphasizes requirements on arguments Lifting Generalizing one or more concrete functions as a single algorithm Typically with use of type parameters - templates Without sacrificing efficiency Compile time duck typing Assuming requirements on the type arguments Using the idea of concepts (§24.3, 4ed) The template's requirements for its type arguments Expressed with a type predicate In terms of a static_assert - for improved error messages

Reference static_assert

What is metaprogramming in C++? Slide Contents Index References

Metaprogramming in C++ emphasizes compile time computations that yields types or functions C++ offers compile time functional programming

Reference The C++ Prog. Lang. (4. edition): Page 779-781

Reference constexpr

constexpr in C++11 Possible compile time calculations Type functions Calculation of types at compile time Type returning functions Support of selection - in between types "Compile Time if-else" Support of iteration Via recursion Other names for metaprogramming Two-level programming, generative programming, template metaprogramming

A metaprogram is a compile time computation yielding types or functions to be used at run time (§28.1, 4ed)

What is metaprogramming used for in C++? Slide Contents Index References

Example of use cases for the C++ metaprogramming facilities

Optimization Precomputations at compile time Program configuration at compile time Calculating sizes and limits of data structures May lead to the need of functions and abstraction Computations on types Computations on functions Conditional declaration Assertions at compile time

C++ is not strong in the area of traditional program reflection Types cannot be accessed at run time - types are not first class objects

Static assert Slide Contents Index References

static_assert is checked at compile time, whereas assert from <cassert> is checked at run time If static_assert fails, a compiler error message will appear

Program: Static assert about the size of int.

// In p1.cc Does not compile on my laptop, because sizeof(int) is 4. #include <iostream> #include <string> static_assert(sizeof(int)==8, "Assuming that 8 bytes are used for int"); int main(){ }

Program: Compilation of p1.cpp.

$ g++ p1.cc -std=c++11 p1.cc:4:1: error: static assertion failed: Assuming that 8 bytes are used for int static_assert(sizeof(int)==8, "Assuming that 8 bytes are used for int"); $

Program: Static asserts abstracted in constexpr function.

// In p4.cc Does not compile on my laptop, float is not void or integral. #include <iostream> #include <string> #include <type_traits> template<class T> constexpr bool void_or_integral(){ return std::is_void<T>::value || std::is_integral<T>::value; } static_assert(void_or_integral<float>(), "Expected void or integral"); int main(){ }

Program: Compilation of p4.cpp.

$ g++ p4.cc -std=c++11 p4.cc:12:1: error: static assertion failed: Expected void or integral static_assert(void_or_integral<float>(), "Expected void or integral"); $

Reference Specialization of class templates - complete and partial

Program: An example a static_assert in a template user specialization program.

// Illustrates a static_assert on top of the template specialization stuff. // Compiles, meaning that the static assert holds (in this program at least). #include <iostream> #include <string> #include <type_traits> template <typename S, typename T> class A{ // The primary template class public: int a; S s; T t; A() : a{1}, s{}, t{} {}; }; template<> class A <int, std::string> { // Complete specialization to S = int, T = string public: int a; int s; std::string t; A() : a{2}, s{}, t{}{}; }; template<typename S, typename T> class A <S*, T*> { // Partial Specialization to pointers public: int a; S s; T t; A() : a{3}, s{}, t{}{}; static_assert(!std::is_pointer<S>::value, "S is not (normally) expected to be a pointer type"); }; template<typename T> class A <T, T> { // Partial specialization: T and S are the same types public: int a; T s; T t; A() : a{4}, s{}, t{}{}; }; int main(){ A<double,bool> a1; // Use of A<S,T> A<int,std::string> a2; // Use of A<int,string> A<double*,std::string*> a3; // Use of A<T*,S*> A<double,double> a4; // Use of A<T,T> std::cout << a1.a << std::endl; // 1 std::cout << a2.a << std::endl; // 2 std::cout << a3.a << std::endl; // 3 std::cout << a4.a << std::endl; // 4 }

Exercise 6.2. Working with static_assert

In this program on the accompanying slide the static_assert holds. In main, enforce a couple of other template instantiations that will cause the static_assert to fail.

There is a lot of useful type functions in <type_traits> - see The C++ Prog. Lang. (4. edition) page 1018 - which can be used in static_assert

Type functions Slide Contents Index References

Type functions accept or return C++ types Some sample type functions are listed below - see Section 35.4 of The C++ Prog. Lang. (4. edition) for a comprehensive listing

Reference The C++ Prog. Lang. (4. edition): Type functions. Page 1018

Type predicates, such as is_floating_point<X> is_pointer<X> is_lvalue_reference<X> is_rvalue_reference<X> is_class<X> is_fundamental<X> is_polymorphic<X> is_abstract<X> Type relations, such as is_same<X,Y> is_base_of<X,Y> Type valued functions, such as remove_pointer<X> remove_reference<X> add_lvalue_reference<X>

Program: Illustration of of type functions in a number static assertions - all of which hold.

// Compiles without errors, meaning that all the static_asserts hold. #include <iostream> #include <string> #include <type_traits> class D {}; class E{ public: virtual void vf(){}; }; int main(){ int a; int &b = a; int *c = &a; D d; E *ep; std::remove_pointer<decltype(ep)>::type f; // Corresponds to E f; f.vf(); // OK, because the type of f is E. static_assert(std::is_integral<decltype(a)>::value, "type of a is expected to be integral"); static_assert(std::is_fundamental<decltype(a)>::value, "type of a is expected to be a fundamental type"); static_assert(std::is_reference<decltype(b)>::value, "type of b is expected to be a reference"); static_assert(std::is_lvalue_reference<decltype(b)>::value, "type of b is expected to be a lvalue reference"); static_assert(!std::is_rvalue_reference<decltype(b)>::value, "type of b is NOT expected to be a rvalue reference"); static_assert(std::is_pointer<decltype(c)>::value, "type of c is expected to be a pointer"); static_assert(std::is_class<decltype(d)>::value, "type of d is expected to be a class"); static_assert(std::is_polymorphic<E>::value, "E is expected to be polymorphic - it has a virtual function"); static_assert(std::is_polymorphic<std::remove_pointer<decltype(ep)>::type>::value, "ep (without ptr) is expected to be polymorphic"); }

Reference decltype

Constant expressions in C++11 Slide Contents Index References

A constant expression - constexpr - can be evaluated at compile time, as well as run-time - a C++11 feature In contrast, const means immutable - cannot be modified at run-time.

Reference The C++ Prog. Lang. (4. edition): Page 42-43, 262-264, 311-313

Reference Effective Modern C++: Use constexpr whenever possible. Item 15

Reference Constants

constexpr Expressive power: Integers, floating-point, and enumeration values Any operator that does not modify a program state Literal types - structs, or classes with a consexpr constructor constexpr functions - pure functions - (relaxed in C++14) Single return No loops, no local variables, no side-effects Recursion Conditional expressions can be used:   - the operator ?:

Examples of constant expressions Slide Contents Index References

We show a number of examples of constant expressions

Program: Examples of constant expressions - C++11.

// A number of examples of constant expressions (C++11). #include <iostream> constexpr int I1 = 5, I2 = 7, I3 = 9; constexpr int I4 = (I1 % 2 == 0) ? I2 : I3; constexpr bool even(int n){ return n % 2 == 0; } constexpr int I5 = even(I1) ? I2 : I3; // Eqvivalent to I4 constexpr long int fac(int n){ return (n == 0) ? 1 : n * fac(n - 1); } constexpr long int FAC5 = fac(5); constexpr long int FAC10 = fac(10); constexpr long int fib(int n){ return (n == 0) ? 0 : (n == 1) ? 1 : fib(n - 1) + fib(n - 2); } constexpr long int FIB20 = fib(20); // int i3 = 3; // constexpr int I6 = (I1 % 2 == 0) ? I2 : i3; // Error: i3 is not a const, and not a constexpr int main(){ // In order to check the results from about (at run time). using namespace std; cout << I1 << " " << I2 << " " << I3 << endl; // 5 7 9 cout << I4 << endl; // 9 cout << I5 << endl; // 9 cout << FAC5 << endl; // 120 cout << FAC10 << endl; // 362800 int i = 10; cout << fac(i) << endl; // 362800 - fac can also be called at run time. cout << FIB20 << endl; // 6765 }

Program: The same program - with results statically asserted.

// The same examples again, with static_assert's of results (instead of output at run time). // Compiles without errors, with g++ constexpr-1-statass.cpp -std=c++11 -c // This means that all asserted results are correctly computed at compile time. #include <iostream> constexpr int I1 = 5, I2 = 7, I3 = 9; constexpr int I4 = (I1 % 2 == 0) ? I2 : I3; constexpr bool even(int n){ return n % 2 == 0; } constexpr int I5 = even(I1) ? I2 : I3; // Eqvivalent to I4 static_assert(I5==I3, "Expected: I5=I3"); constexpr long int fac(int n){ return (n == 0) ? 1 : n * fac(n - 1); } constexpr long int FAC5 = fac(5); static_assert(FAC5==120, "Expected: FAC5 is 120"); constexpr long int FAC10 = fac(10); static_assert(FAC10==3628800, "Expected: FAC10 is 362800"); constexpr long int fib(int n){ return (n == 0) ? 0 : (n == 1) ? 1 : fib(n - 1) + fib(n - 2); } constexpr long int FIB20 = fib(20); static_assert(FIB20==6765, "Expected: FIB20 is 6765");

Program: Evaluation of constexpr at run-time - C++11.

// Illustrates that constexpr functions can be evaluated at run-time as well. #include <iostream> constexpr long int fib(int n){ return (n == 0) ? 0 : (n == 1) ? 1 : fib(n - 1) + fib(n - 2); } constexpr long int fac(int n){ return (n == 0) ? 1 : n * fac(n - 1); } int main(){ using namespace std; int i; cout << "Enter an integer: "; cin >> i; cout << "Fib(i): " << fib(i) << " fac(i): " << fac(i) << endl; }

Program: Relaxed constexpr in C++14.

// Constexpr as of C++14. Not yet compilable in g++. Due in gcc version 5. #include <iostream> constexpr long int fib(int n){ int a = 0, b = 1, tmp; for(int i = 1; i <= n; ++i){ tmp = a; a = b; b = tmp + b; } return a; } constexpr long int fac(int n){ int res = 1; for(int i = 1; i <= n; ++i) res = res * i; return res; } int main(){ using namespace std; constexpr int FAC5 = fac(5); constexpr int FIB10 = fib(10); cout << "FAC5 " << FAC5 << " FIB10: " << FIB10 << endl; }

Program: Examples of a literal type, struct Point - C++11.

// Illustrates a struct Point - a literal type - with constexpr member functions. #include <iostream> #include <string> struct Point { // A literal type double x, y; constexpr double getx () {return x;} constexpr double gety () {return y;} constexpr Point move(double dx, double dy){return Point{x + dx, y + dy};} }; // Points handled at compile-time - the last is an array of points: constexpr Point origo {0,0}; constexpr Point p1 = origo.move(3.1, 4.2); constexpr Point pa[] = {origo, p1, p1.move(0.9, -0.2)}; int main(){ using namespace std; cout << "(" << origo.getx() << "," << origo.gety() << ")" << endl; // (0,0) cout << "(" << p1.getx() << "," << p1.gety() << ")" << endl; // (3.1, 4.2) for(auto p: pa) cout << "(" << p.getx() << "," << p.gety() << ")" << endl; // (0,0) (3.1, 4.2) (4,4) }

Program: The same program - with results statically asserted.

// Same as above, but with static_asserts that check for correct results. // Compiles, and therefore all static_asserts hold. // Compile with: g++ constexpr-2-statass.cpp -std=c++11 -c #include <iostream> #include <string> struct Point { // A literal type double x, y; constexpr double getx () {return x;} constexpr double gety () {return y;} constexpr Point move(double dx, double dy){return Point{x + dx, y + dy};} }; // Points handled at compile-time - the last is an array of points: constexpr Point origo {0,0}; static_assert(origo.x==0 && origo.y == 0, "Expected: Origo at (0,0)"); constexpr Point p1 = origo.move(3.1, 4.2); static_assert(p1.x==3.1 && p1.y == 4.2, "Expected: p1 at (3.1, 4.2)"); constexpr Point pa[] = {origo, p1, p1.move(0.9, -0.2)}; constexpr bool pa_is_OK(const Point pa[3]){ return pa[0].x == 0 && pa[0].y == 0 && pa[1].x == 3.1 && pa[1].y == 4.2 && pa[2].x == 3.1+0.9 && pa[2].y == 4.2-0.2; } static_assert(pa_is_OK(pa), "expected: pa is as expected...");

Program: Examples of class Circle with a constexpr constructor - C++11.

// Illustrates class circle with aconstexpr constructors and constexpr member functions. // Compiles without errors. #include <iostream> constexpr double square(double x){ return x * x; } constexpr double PI = 3.14159; class Circle { private: double cx, cy; double radius; public: constexpr Circle(double x, double y, double r) : cx{x}, cy{y}, radius{r}{ } constexpr Circle(const Circle& c) : cx(c.cx), cy(c.cy), radius(c.radius){ } constexpr double area(){ return square(radius) * PI; } constexpr Circle move(double dx, double dy){ return Circle(cx+dx, cy+dy, radius); } constexpr double x(){return cx;} constexpr double y(){return cy;} constexpr double r(){return radius;} }; // Compile time use of class circle: constexpr Circle C1{1.1, 2.2, 4.0}, C2 = C1.move(0.9, 0.8); constexpr double C1_Area = C1.area(); static_assert(C1_Area == 4.0 * 4.0 * PI, "Expected vaue of C1_Areal is 4.0 * 4.0 * PI"); // End of compile time use of class Circle. int main(){ using namespace std; cout << "C1: " << C1.area() << endl; // 50.2654 cout << "C2: " << C2.area() << endl; // 50.2654 // cout << C1.cx << " " << C1.cy << " " << C1.radius << endl; // Error - access to private variables. // cout << C2.cx << " " << C2.cy << " " << C2.radius << endl; // Error - access to private variables. cout << C1.x() << " " << C1.y() << " " << C1.r() << endl; // 1.1 2.2 4 cout << C2.x() << " " << C2.y() << " " << C2.r() << endl; // 2 3 4 // Run time use of class Circle: Circle *pc1{new Circle(10, 20, 5)}; Circle c2 = pc1->move(1,-1); Circle c3{C2}; // Constructing c3 based on compile time constructed C2. cout << "*pc1: " << pc1->x() << " " << pc1->y() << " " << pc1->r() << endl; // *pc1: 10 20 5 cout << "c2: " << c2.x() << " " << c2.y() << " " << c2.r() << endl; // c2: 11 19 5 cout << "c3: " << c3.x() << " " << c3.y() << " " << c3.r() << endl; // c3: 2 3 4 delete pc1; // End of run time use of class Circle. }

Selection between two types Slide Contents Index References

Selection between types is supported by the struct conditional in <type_traits> We first show an example that uses conditional - after that the struct itself is studied

Reference The C++ Prog. Lang. (4. edition): Selection of types. Page 790

Program: An sample use of conditional.

// Conditional example - adapted from www.cplusplus.com. Simple stuff. // Illustrates std::conditional and std:is_same. // Ilustrates using syntax (4ed, pages 167). #include <iostream> #include <type_traits> int main() { // Establish aliases for selected types: using A = std::conditional<true, int, float>::type; // select int using B = std::conditional<false, int, float>::type; // select float using C = std::conditional<std::is_integral<A>::value, long, int>::type; // select long - because type A is int using D = std::conditional<std::is_integral<B>::value, long, int>::type; // select int - because B is float // Use established types: A a{}; // A variable of type A B b = [](B x) -> B{return x/2;}(10.0); // Use of type B in a lambda expressions, and its immediate call // Print info about types: std::cout << std::boolalpha; // print boolean values as false and true // (rather than 0 and 1) std::cout << "typedefs of int:" << std::endl; std::cout << "A: " << std::is_same<int,A>::value << std::endl; // A: true std::cout << "B: " << std::is_same<int,B>::value << std::endl; // B: false std::cout << "C: " << std::is_same<int,C>::value << std::endl; // C: false std::cout << "D: " << std::is_same<int,D>::value << std::endl; // D: true return 0; }

Program: Same - syntactically embellished.

// Introducing a template alias (4ed, page 694) - a slight improvement. // Conditional example - adapted from www.cplusplus.com. #include <iostream> #include <type_traits> // Conditional is a syntactical embellishment of the application of underlying conditional template: template<bool B, typename T, typename F> using Conditional = typename std::conditional<B, T, F>::type; int main() { using namespace std; using A = Conditional<true,int,float>; // select int using B = Conditional<false,int,float>; // select float using C = Conditional<is_integral<A>::value,long,int>; // select long - because type A is int using D = Conditional<is_integral<B>::value,long,int>; // select int - because B is float // ... }

Program: Use of my_conditional in the example from above.

// A slightly more realistic use of type selection. #include <iostream> #include <type_traits> // Conditional is a syntactial embellishment of the application of underlying conditional template. // We are using a template alias: template<bool B, typename T, typename F> using Conditional = typename std::conditional<B, T, F>::type; constexpr long int LIMIT = 5000; constexpr bool large(int n){ return n > LIMIT; } int main() { using namespace std; const long int SZ = 1234; using FloatingPointT = Conditional<large(SZ),double,float>; // select type - float is selected in this // particular context. FloatingPointT x = 1234.5678; cout << "sizeof(double) = " << sizeof(double) << endl; // 8 cout << "sizeof(float) = " << sizeof(float) << endl; // 4 cout << "sizeof(FloatingPointT) = " << sizeof(FloatingPointT) << endl; // 4 return 0; }

Program: Possible definition of conditional - here as my_conditional.

// Possible definition of conditional - here as my_conditional - in file conditional-def.cc // The standard library definition is in <type_traits> template<bool C, typename T, typename F> // Template, catching all other cases than the struct my_conditional { // specialization (below). using type = T; }; template<typename T, typename F> // Template specialization, for the false branch. struct my_conditional <false, T, F>{ using type = F; };

Program: Use of my_conditional - in the example from above.

// Using my_conditional instead of std:conditional, via a programmed syntactial embellishment Conditional. #include <iostream> #include <type_traits> #include "conditional-def.cc" // Conditional is a syntactial embellishment of the underlying conditional template: template<bool B, typename T, typename F> using Conditional = typename my_conditional<B, T, F>::type; int main() { using namespace std; using A = Conditional<true,int,float>; // select int using B = Conditional<false,int,float>; // select float using C = Conditional<is_integral<A>::value,long,int>; // select long - because type A is int using D = Conditional<is_integral<B>::value,long,int>; // select int - because B is float // ... return 0; }

Selection between two functions Slide Contents Index References

Compile time selection between two functions Illustrated with an example from page 787 of The C++ Prog. Lang. (4. edition)

Reference The C++ Prog. Lang. (4. edition): Page 787, 791

Program: Selection one of two functions at compile time.

// An illustration of function objects. Very close to the program on page 787 of "The C++ Programming Language" 4ed. #include <iostream> #include <type_traits> // Conditional is a syntactial embellishment of the application of underlying conditional template: template<bool B, typename T, typename F> using Conditional = typename std::conditional<B, T, F>::type; struct X{ void operator()(int x){ std::cout << "X: " << x << std::endl; } // ... }; struct Y{ void operator()(int y){ std::cout << "Y: " << y << std::endl; } // ... }; void f(){ Conditional<(sizeof(int)>4), X, Y>{}(7); // Select either X or Y depending on the value of sizeof(int)>4. // Y is selected, instantiated, and called on 7. Y{}(7); // Equivalent. Y: 7 using Z = Conditional<std::is_polymorphic<X>::value, X, Y>; // X is not polymorphic, therefore Z becomes an alias of Y. Z zz{}; // makes an X or a Y zz(8); // calls an X og a Y. // Y: 8 } int main(){ std::cout << "size(int): " << sizeof(int) << std::endl; // 4 on my laptop. f(); }

Can we do similar run time selection of functions in C++? Are functions first class objects in C++?

Conditional declarations Slide Contents Index References

Conditional declaration can be done with enable_if Illustrated on the move member in class Point<C>

Reference The C++ Prog. Lang. (4. edition): enable_if. Page 795

Program: Class Point header file - where move is only enabled for floating point types.

// Point<C> where move is only enabled for floating point types. #include <type_traits> // One of the usual syntactical embellishments, here of enable_if. template <bool B, typename T> using Enable_if = typename std::enable_if<B,T>::type; template<typename C>class Point { private: C x, y; public: Point(C, C); Point(); C getx () const; C gety () const; Enable_if<std::is_floating_point<C>::value, Point<C>>& move(C, C); // if C is not a floating point type, // the move function is not present. double distance_to(Point); }; template<class C> std::ostream& operator<< (std::ostream&, const Point<C>&);

Program: Implementation of Point<C> members.

// point.cc in which move is only present if C is a floating point type. #include <cmath> #include <iostream> #include "point.h" template<typename C> Point<C>::Point(C x_coord, C y_coord): x(x_coord), y(y_coord){ } template<typename C> Point<C>::Point(): x(0.0), y(0.0){ } template<typename C> C Point<C>::getx () const{ return x; } template<typename C> C Point<C>::gety () const{ return y; } // if C is not a floating point type, the move function is not present. template<typename C> Enable_if<std::is_floating_point<C>::value, Point<C>>& Point<C>::move(C dx, C dy){ x += dx; y += dy; return *this; } template<typename C> double Point<C>::distance_to(Point<C> p){ return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); // Similar assumptions for - and * } template<typename C> std::ostream& operator<< (std::ostream& s, const Point<C>& p){ return s << "(" << p.getx() << "," << p.gety() << ")" ; }

Program: Use of class Point<double> with move - OK.

// Compiles and runs, because double (in Point<double>) is a floating point type. #include <iostream> #include <string> #include "point.cc" int main(){ Point<double> p1, p2(1,2); p1.move(1,1); // OK p2.move(2,2); // OK std::cout << "p1: " << p1 << std::endl; // (1,1) std::cout << "p2: " << p2 << std::endl; // (3,4) }

Program: Use of class Point with move - does not compile.

// Does not compiles, because int (in Point<int>) is NOT a floating point type. #include <iostream> #include <string> #include "point.cc" int main(){ Point<int> p1, p2(1,2); p1.move(1,1); // error: class Point<int> has no member named move p2.move(2,2); // error: class Point<int> has no member named move std::cout << "p1: " << p1 << std::endl; // (1,1) std::cout << "p2: " << p2 << std::endl; // (3,4) }

Example of type function: Integer of given byte size Slide Contents Index References

We show how to program a type function: Integer_of_byte_size<N> A function from an int to some C++ integer type

Reference The C++ Prog. Lang. (4. edition): Page 781

A function from int to an integer type Input: N (such as 0, 1, 2, 3) Output: A C++ integer type, such as unsigned char or short int

The concrete mapping: 0 is mapped to void (it is an error) 1 is mapped to usigned char 2 is mapped to short int 3 is mapped to void (it is an error)

Program: First version of type function.

// Use of the Select template struct for selection anmong a number of different types. // Select corresponds to the switch control structure. #include <iostream> #include <string> #include "select-stuff.cc" // Integer<N>::type is an integer type of N bytes: (4ed, page 782) template<int N> struct Integer{ using Error = void; using type = Select<N, Error, // 0 selects Error (void) signed char, // 1 selects singed char short int, // 2 selects short int Error // 3 selects Error (void) >; }; int main(){ using namespace std; typename Integer<1>::type i = 65; // similar to: unsigned char i = 10; // 'A' typename Integer<2>::type j = 66; // similar to: short int j = 8; cout << "i: " << i << " of size: " << sizeof(i) << endl; // i: A of size 1 cout << "j: " << j << " of size: " << sizeof(j) << endl; // j: 66 of size 2 }

Program: Second version of type function - embellished syntax of the type function.

// Simplifying the use of Select via use of a template alias (4ed page 694). #include <iostream> #include <string> #include "select-stuff.cc" // Integer<N>::type is now defined as an integer type of N bytes: (4ed, page 782) template<int N> struct Integer{ using Error = void; using type = Select<N, Error, // 0 selects Error (void) signed char, // 1 selects singed char short int, // 2 selects short int Error // 3 selects Error (void) >; }; // Embellish the notation Integer<N>::type to Integer_of_size<N> - made by use of a template alias (4ed, 23.6). template<int M> using Integer_of_byte_size = typename Integer<M>::type; int main(){ using namespace std; Integer_of_byte_size<1> i = 65; // similar to: unsigned char i = 10; // 'A' Integer_of_byte_size<2> j = 66; // similar to: short int j = 8; cout << "i: " << i << " of size: " << sizeof(i) << endl; // i: A of size 1 cout << "j: " << j << " of size: " << sizeof(j) << endl; // j: 66 of size 2 }

Program: The ugly and bulky selection stuff.

// Select stuff - templates that define selection of one out of four types (4ed, page 792). struct Nil {}; // A trivial Nil type // select - declared, but not defined in the general case. Only specializations are defined. template <int I, typename T1 = Nil, typename T2 = Nil, typename T3 = Nil, typename T4 = Nil> struct select; // A using alias Select that binds unused types to Nil template <int I, typename T1 = Nil, typename T2= Nil, typename T3 = Nil, typename T4 = Nil> using Select = typename select<I, T1, T2, T3, T4>::type; // Specializations for 0-3 template <typename T1, typename T2, typename T3, typename T4> struct select<0, T1, T2, T3, T4> {using type = T1;}; // Specialization for 0 template <typename T1, typename T2, typename T3, typename T4> struct select<1, T1, T2, T3, T4> {using type = T2;}; // Specialization for 1 template <typename T1, typename T2, typename T3, typename T4> struct select<2, T1, T2, T3, T4> {using type = T3;}; // Specialization for 2 template <typename T1, typename T2, typename T3, typename T4> struct select<3, T1, T2, T3, T4> {using type = T4;}; // Specialization for 3

Generalizing Select with use of a variadic template Slide Contents Index References

The selection shown on the previous slides is ugly - and limited to selection of one out of 4 types Here we illustrate a generalization of select programmed with variadic templates An embellishment removes a little syntactical noice The Integer struct is straightforward

Reference The C++ Prog. Lang. (4. edition): Variadic templates. Page 809

Program: Yet another version of type function - generalized to selection among an arbitrary number of types.

// The example generalized to selection based on a bytelength from 0 to 8. #include <iostream> #include <string> #include "select-stuff-general.cc" // Integer<N>::type is now defined as an integer type of N bytes: (4ed, page 782) template<int N> struct Integer{ using Error = void; using type = Select<N, Error, // 0 selects Error (void) signed char, // 1 selects singed char short int, // 2 selects short int Error, // 3 selects Error (void) int, // 4 selects int Error, // 5 selects Error (void) Error, // 6 selects Error (void) Error, // 7 selects Error (void) long long int // 8 selects long long int >; }; // Embellish the notation Integer<N>::type to Integer_of_size<N> - made by use of a template alias (4ed, 23.6). template<int M> using Integer_of_byte_size = typename Integer<M>::type; int main(){ using namespace std; Integer_of_byte_size<1> i = 65; // similar to: unsigned char i = 10; // 'A' Integer_of_byte_size<2> j = 66; // similar to: short int j = 66; Integer_of_byte_size<4> k = 67; // similar to: int k = 67; Integer_of_byte_size<8> l = 68; // similar to: long int l = 68; cout << "i: " << i << " of size: " << sizeof(i) << endl; // i: A of size 1 cout << "j: " << j << " of size: " << sizeof(j) << endl; // j: 66 of size 2 cout << "k: " << k << " of size: " << sizeof(k) << endl; // k: 67 of size 4 cout << "l: " << l << " of size: " << sizeof(l) << endl; // l: 68 of size 8 }

Program: General selection stuff - shorter and more elegant - using variadic templates (C++11).

// Select stuff - templates that define selection in the general case (4ed, page 792). // Uses variadic templates (4ed, 809). C++11. // select - declared, but never instantiated. The specialization below will be instantiated template<unsigned int N, typename... Types> struct select; // Specialization that just recurses in the base type: template <unsigned int N, typename T, typename... Types> struct select<N, T, Types...>: select<N-1, Types...>{ }; // Specialization that represent the base case of the recursion. // Defines what type stands for: template<typename T, typename... Types> struct select<0, T, Types...>{ using type = T; }; // A using alias Select that embellish the use of select - as before: template <unsigned int N, typename... Types> using Select = typename select<N, Types...>::type;

Compile Time iteration Slide Contents Index References

Compile Time iteration takes place via recursion There is no variable state at compile time Iterative control structures are therefore not applicable

Program: The factorial function defined as a constexpr function (C++11).

// Factorial defined as a constexpr function definition. (4ed page 793). // A function that can be use by the compiler, as well as on run time. // C++11 #include <iostream> constexpr int fac(int i){ return (i <= 0) ? 1 : i * fac(i - 1); } // compile-time test cases: static_assert(fac(5)==120, "fac(5) problem"); static_assert(fac(10)==3628800, "fac(10) problem"); int main(){ using namespace std; // CALL OF fac AT COMPILE TIME: constexpr int res = fac(10); cout << "fac(10) = " << res << endl; // fac(10) = 3628800 cout << "fac(5) = " << fac(5) << endl; // fac(5) = 120 // CALL OF fac AT RUN TIME: int i; cout << "Enter i: "; cin >> i; cout << "fac(2*i) " << fac(2*i) << endl; // Depends in user input of i }

Program: The factorial function defined as a function template - using a template int parameter.

// Factorial defined as a function template (4ed page 793). // The input N is a templates parameter. // C++11 #include <iostream> template<int N> constexpr int fac(){ return N * fac<N-1>(); } template<> // A specialization for N = 1 constexpr int fac<1>(){ return 1; } int main(){ using namespace std; // call of fac at compile time: constexpr int res = fac<10>(); static_assert(res==3628800, "Value of fac<10> is incorrect"); cout << "fac(10) = " << res << endl; // fac(10) = 3628800 cout << "fac(5) = " << fac<5>() << endl; // fac(5) = 120 // attempt to call of fac at run time - not possible, however: int i; cout << "Enter i: "; cin >> i; cout << "fac(2*i) " << fac<2*i>() << endl; // Compile time error: // the value of 'i' is not usable in a constant expression }

Program: The factorial function programmed in struct - with recursion.

// Factorial defined as a static int member in a struct. // Can only be used a compile time // Does not rely on C++11 facilities. #include <iostream> // Defining and holding the factorial value in a static int member. template<int N> struct Fac{ static const int value = N * Fac<N-1>::value; }; template<> // A specialization for N = 1 struct Fac<1>{ static const int value = 1; }; int main(){ using namespace std; // Call of fac at compile time: const int res = Fac<10>::value; cout << "fac(10) = " << res << endl; // fac(10) = 3628800 cout << "fac(5) = " << Fac<5>::value << endl; // fac(5) = 120 // Fac cannot be called with run time input. }

More compile time computations - older stuff Slide Contents Index References

We show examples of simple recursive functions which can be called and evaluated by the compiler

Program: The factorial function - from Wikipedia.

// Factorial template function from Wikipedia. #include <iostream> #include <string> // The general case: template <int N> struct Factorial { static const int value = N * Factorial<N - 1>::value; }; // The base case of the recursion, via template specialization: template <> struct Factorial<0> { static const int value = 1; }; int main(){ Factorial<5> facBox; std::cout << facBox.value << std::endl; // 120 std::cout << Factorial<10>::value << std::endl; // 3628800 }

Program: The power function on integer type arguments.

// The power function on integer type arguments. #include <iostream> // The general case: template <unsigned int N, unsigned int P> struct Power{ static const unsigned int value = N * Power<N,P-1>::value; }; // The base case, via template specialization: template <unsigned int N>struct Power<N,1> { static const unsigned int value = 1; }; int main(){ std::cout << Power<5,3>::value << std::endl; // 25 std::cout << Power<5,5>::value << std::endl; // 625 std::cout << Power<5,7>::value << std::endl; // 15625 }

Program: The power function on integer type arguments - alternative implementation with an enumeration constant.

// The power function on integer type arguments - use of enumeration constants. #include <iostream> // The general case: template <unsigned int N, unsigned int P> struct Power{ enum {value = N * Power<N,P-1>::value}; }; // The base case, via template specialization: template <unsigned int N>struct Power<N,1> { enum {value = 1}; }; int main(){ std::cout << Power<5,3>::value << std::endl; // 25 std::cout << Power<5,5>::value << std::endl; // 625 std::cout << Power<5,7>::value << std::endl; // 15625 }

Reference The math behind the quick power function

Program: A more advanced version of the power function - from Stack Overflow.

// John Bartholomew, stack overflow // http://stackoverflow.com/questions/4608763/compile-time-templated-c-calculations-on-unsigned-long-long-on-doubles #include <iostream> template <unsigned long long N, unsigned int P, int Odd = (P&1)> struct Power; template <unsigned long long N, unsigned int P> struct Power<N,P,0> { // 0: P is even (square N and halve the power) static const unsigned long long val = Power<N*N,(P/2)>::val; }; template <unsigned long long N, unsigned int P> struct Power<N,P,1> { // 1: P is odd (multiply by N and decrement the power) static const unsigned long long val = N * Power<N,(P-1)>::val; }; template <unsigned long long N> struct Power<N,0,0> { // zero (x**0 is 1 for all x != 0) static const unsigned long long val = 1; }; int main() { std::cout << "2**0 = " << Power<2,0>::val << "\n"; std::cout << "2**1 = " << Power<2,1>::val << "\n"; std::cout << "2**2 = " << Power<2,2>::val << "\n"; std::cout << "2**3 = " << Power<2,3>::val << "\n"; std::cout << "2**4 = " << Power<2,4>::val << "\n"; std::cout << "2**5 = " << Power<2,5>::val << "\n"; std::cout << "2**6 = " << Power<2,6>::val << "\n"; std::cout << "2**7 = " << Power<2,7>::val << "\n"; std::cout << "2**8 = " << Power<2,8>::val << "\n"; std::cout << "2**9 = " << Power<2,9>::val << "\n"; std::cout << "2**10 = " << Power<2,10>::val << "\n"; std::cout << "2**11 = " << Power<2,11>::val << "\n"; std::cout << "2**12 = " << Power<2,12>::val << "\n"; std::cout << "2**30 = " << Power<2,30>::val << "\n"; std::cout << "2**40 = " << Power<2,40>::val << "\n"; std::cout << "2**50 = " << Power<2,50>::val << "\n"; std::cout << "2**60 = " << Power<2,60>::val << "\n"; return 0; }

Program: A variant of the more advanced version of the power function.

// John Bartholomew, stack overflow // http://stackoverflow.com/questions/4608763/compile-time-templated-c-calculations-on-unsigned-long-long-on-doubles #include <iostream> template <unsigned long long N, unsigned int P, int Odd = (P&1)> struct Power; template <unsigned long long N, unsigned int P> struct Power<N,P,0> { // 0: P is even (square N and halve the power) static const unsigned long long val = Power<N,(P/2)>::val * Power<N,(P/2)>::val; }; template <unsigned long long N, unsigned int P> struct Power<N,P,1> { // 1: P is odd (multiply by N and decrement the power) static const unsigned long long val = N * Power<N,(P-1)>::val; }; template <unsigned long long N> struct Power<N,0,0> { // zero (x**0 is 1 for all x != 0) static const unsigned long long val = 1; }; int main() { std::cout << "2**0 = " << Power<2,0>::val << "\n"; std::cout << "2**1 = " << Power<2,1>::val << "\n"; std::cout << "2**2 = " << Power<2,2>::val << "\n"; std::cout << "2**3 = " << Power<2,3>::val << "\n"; std::cout << "2**4 = " << Power<2,4>::val << "\n"; std::cout << "2**5 = " << Power<2,5>::val << "\n"; std::cout << "2**6 = " << Power<2,6>::val << "\n"; std::cout << "2**7 = " << Power<2,7>::val << "\n"; std::cout << "2**8 = " << Power<2,8>::val << "\n"; std::cout << "2**9 = " << Power<2,9>::val << "\n"; std::cout << "2**10 = " << Power<2,10>::val << "\n"; std::cout << "2**11 = " << Power<2,11>::val << "\n"; std::cout << "2**12 = " << Power<2,12>::val << "\n"; std::cout << "2**30 = " << Power<2,30>::val << "\n"; std::cout << "2**40 = " << Power<2,40>::val << "\n"; std::cout << "2**50 = " << Power<2,50>::val << "\n"; std::cout << "2**60 = " << Power<2,60>::val << "\n"; return 0; }

Program: Program output - both versions.

2**0 = 1 2**1 = 2 2**2 = 4 2**3 = 8 2**4 = 16 2**5 = 32 2**6 = 64 2**7 = 128 2**8 = 256 2**9 = 512 2**10 = 1024 2**11 = 2048 2**12 = 4096 2**30 = 1073741824 2**40 = 1099511627776 2**50 = 1125899906842624 2**60 = 1152921504606846976

The 'functions' from above relies on the compiler's ability to evaluate constant expressions, see §C.5 in The C++ Prog. Lang. (3. edition)

Chapter 6: The Standard Library and Metaprogramming
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: August 1, 2017, 13:31:59