Generic Programming and C++ Templates Overview

Templates & STL 1. Generic Programming 2. C++ Templates 3. Function Templates 4. Class Templates 5. Standard Template Library (STL) 6. Vectors 7. Iterators 1

Generic programming Generic programming encourages: Writing code without reference to a specific data type (float, int, etc.) Designing code in the most abstract manner possible Why? Trades a little extra design time for greatly improved re-usability 2

Generic programming Generalize algorithms Sometimes called lifting an algorithm The aim (for the end user) is Increased correctness Through better specification Greater range of uses Possibilities for re-use Better performance Through wider use of tuned libraries Unnecessarily slow code will eventually be thrown away Go from the concrete to the more abstract The other way most often leads to bloat 3

Generic Programming Resources STL Standard Template Library (Reference Pages www.sgi.com/tech/stl/ ) GTL : Graph Template Library BGL : Boost Graph Library MTL : Matrix Template Library ITL : Iterative Template Library 4

Macros A macro (short for "macroinstruction", from Greek - 'long') in computer science is a rule or pattern that specifies how a certain input sequence (often a sequence of characters) should be mapped to a replacement input sequence (also often a sequence of characters) according to a defined procedure. The mapping process that instantiates (transforms) a macro use into a specific sequence is known as macro expansion. A facility for writing macros may be provided as part of a software application or as a part of a programming language. In the former case, macros are used to make tasks using the application less repetitive. In the latter case, they are a tool that allows a programmer to enable code reuse or even to design domain-specific languages. 5

C++ Templates I always knew C++ templates were the work of the Devil, and now I'm sure... Part of the ongoing development of the C++ language Integral part of the larger C++ Standard Library (The Standard Template Library) C++ templates: "a clever kind of macro that obeys the scope, naming, and type rules of C++ ". A template describes a set of related classes or set of related functions in which a list of parameters in the declaration describe how the members of the set vary. The compiler generates new classes or functions when you supply arguments for these parameters; this process is called template instantiation. This class or function definition generated from a template and a set of template parameters is called a specialization. 6

C++ Templates Kinds of Templates Function Permit the development of generic algorithms Class Permit the development of generic objects 7

Overview of C++ Templates Templates are used to plug in different types Can re-use same code with int, string, etc. Also called type parameterization Types are given as parameters to a template Like variables are given as a function s parameters Can make templates for functions and classes The user of a class template must declare the type parameters when declaring an instance Don t have to declare the type parameters when calling a function template (call as though a non-template function) The compiler figures it out for you, based on function call signature 8

Function Templates Function template: A pattern for creating definitions of functions that differ only in the type of data they manipulate Better than overloaded functions, since the code defining the algorithm of the function is only written once 9

Two functions that differ only in the type of the data they manipulate void swap(int &x, int &y) { int temp = x; x = y; y = temp; } void swap(char &x, char &y) { char temp = x; x = y; y = temp; } 10

A swap Template The logic of both functions can be captured with one template function definition template<class T> void swap(T &x, T &y) { T temp = x; x = y; y = temp; } 11

Using a Template Function When a function defined by a template is called, the compiler creates the actual definition from the template by inferring the type of the type parameters from the arguments in the call: int i = 1, j = 2; swap(i,j); This code makes the compiler instantiate the template with type int in place of the type parameter T 12

Function Template Notes A function template is a pattern No actual code is generated until the function named in the template is called A function template uses no memory When passing a class object to a function template, ensure that all operators referred to in the template are defined or overloaded in the class definition 13

Introduction to Function Templates Basic idea same code is re-used for different types Function template swap takes one type parameter, T Definition interchanges values of two passed arguments of the parameterized type Compiler infers type is really int when swap is called Compiler instantiates the function template definition using type int template <typename T> void swap(T &lhs, T &rhs) { T temp = lhs; lhs = rhs; rhs = temp; } int main () { int i = 3; int j = 7; swap (i,j); return 0; } 14

Function Templates A function templateis a generic function that can work with any data type. The programmer writes the specifications of the function, but substitutes parameters for data types. When the compiler encounters a call to the function, it generates code to handle the specific data type(s) used in the call. This is not like inheritance. 15

An Example Function Template Indicates a template is being defined Indicates T is our formal template parameter template <class T> T Min(const T &a, const T &b) { if (a < b) return a; else return b; } Instantiated functions will return a value whose type is the actual template parameter Instantiated functions require two actual parameters of the same type. Their type will be the actual value for T 16

Template Example We want a function that prints out the values of an array. This function should work with arrays of type int, float, char, or string. In a perfect world (where all these types descended from the same base type), we could use inheritance to make this happen. 17

printArray.cpp Program #include <iostream> #include <string> using namespace std; template< class T> void printArray ( const T *array, const int size ) { for ( int i = 0; i < size; i++ ) { if ( !( i % 10 ) ) cout << endl; cout << array[i] << " "; } // for cout << endl; } // printArray 18

printArray.cpp Program (cont) void main ( void ) { const int aSize = 5, bSize = 7, cSize = 6, dSize = 3; int a[ aSize ] = { 1, 2, 3, 4, 5 }; float b[ bSize ] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 }; char c[ cSize ] = "Hello"; string d[ dSize ] = { "I", "love", "CS" }; printArray( a, aSize ); printArray( b, bSize ); printArray( c, cSize ); printArray( d, dSize ); } // main 19

Generic swap Suppose we wanted a generic swap. void swap ( T &var1, T &var2 ) { T temp; template <class T> temp = var1; var1 = var2; var2 = temp; } // swap 20

Suppose we want a generic Max function template <class T> T maximum(T a, T b) { return a > b ? a : b ; // Familiar operator? } void main() { cout << "max(10, 15) = " << maximum(10, 15) << endl ; cout << "max('k', 's') = " << maximum('k', 's') << endl ; cout << "max(10.1, 15.2) = " << maximum(10.1, 15.2) << endl ; } 21

Generic Sorting template <class T> void InsertionSort(T A[], int n) { for (int i = 1; i < n; ++i) { if (A[i] < A[i-1]) { T val = A[i]; int j = i; do { A[j] = A[j-1]; --j; } while ((j > 0) && (val < A[j-1])); A[j] = val; } } } 22

STLs Template Functions STL provides template definitions for many programming tasks Use them! Do not reinvent the wheel! Searching and sorting find(), find_if(), count(), count_if(), min(), max(), binary_search(), lower_bound(), upper_bound(), sort() Comparing equal() Rearranging and copying unique(), replace(), copy(), remove(), reverse(), random_shuffle(), merge() Iterating for_each() 23

Function Templates Example of a Function Template Declaration: // Returns the minimum of array x[ ]. The data // type of x[ ] is arbitrary & customizable template<typename T> T min(T x[], int length){ T m = x[0]; // m is the minimum so far for (int i=1;i<n;i++) if (x[i]<m) m=x[i]; return m; } Example of Use: int x[]= {11, 13, 5, 7, 4, 10}; double y[]= {4.5, 7.13, 17}; int minx = min<int>(x,6); double miny= min<double>(y,3); 24

Class Templates It is possible to define templates for classes. Unlike functions, a class template is instantiated by supplying the type name (int, float, string, etc.) at object definition 25

Class Template Consider the following classes 1. Class used to join two integers by adding them: class Joiner { public: int combine(int x, int y) {return x + y;} }; 2. Class used to join two strings by concatenating them: class Joiner { public: string combine(string x, string y) {return x + y;} }; 26

Example class Template A single class template can capture the logic of both classes: it is written with a template prefix that specifies the data type parameters: template <class T> class Joiner { public: T combine(T x, T y) {return x + y;} }; 27

Using Class Templates To create an object of a class defined by a template, specify the actual parameters for the formal data types Joiner<double> jd; Joiner<string> sd; cout << jd.combine(3.0, 5.0); cout << sd.combine("Hi ", "Ho"); Prints 8.0 and Hi Ho 28

Introduction to Class Templates Parameterized type T must be specified in class template declaration Both as a parameter, and where it s used in the class When an instance is declared, must also explicitly specify the concrete type parameter E.g., int vs. string in function main() In previous function template example, didn t have to say swap<int> template <typename T> class Array { public: Array(const int size); ~Array(); private: T * values_; const int size_; }; int main() { Array<int> a(10); Array<string> b(5); return 0; } 29

Tips on Using Function and Class Templates Push common code and variables up into non-template base classes Gives compiler less work to do instantiating templates Reduces program size and compilation time Use function templates when you want type parameterization to be invisible to programmer To force an explicit declaration of the parameterized type, use member functions of class templates instead Use class templates when you want to parameterize member variables types Lots of containers in the STL do this (vector, list, etc.) We ll talk about the STL and how it uses templates later in the semester 30

Introduction to the Standard Template Library Standard Template Library (STL): a library containing templates for frequently used data structures and useful algorithms Programs can be developed faster and are more portable if they use templates from the STL An ISO C++ standard framework of about 10 containers and about 60 algorithms connected by iterators Other organizations provide more containers and algorithms in the style of the STL Boost.org, Microsoft, SGI, Probably the currently best known and most widely used example of generic programming 31

Standard Template Library The Standard Template Library (STL) is a software library included in the C++ Standard Library. It provides containers, iterators, and algorithms. More specifically the C++ Standard Library is based on the STL Library published by SGI. Both include some features not found in the other. SGI's STL is rigidly specified as a set of headers, while ISO C++ does not specify header content, and allows implementation either in the headers, or in a true library. STL was architected by Alexander Stepanov in 1979. 32

Introduction The C++ Standard Template Library (STL) has become part of C++ standard The main author of STL is Alexander Stephanov He chose C++ because of templates and no requirement of using OOP! The library is somewhat unrelated with the rest of the standard library which is OO

3D generic world DATA STRUCTURES Stephanov observed three orthogonal dimensions in algorithms: iterators allow algorithms to iterate over data structures. Iterators are very akin with C pointers and compatible with them ALGORITHMS ITERATORS

STL Disadvantages The quality of the C++ compiler has a large impact on usability of STL: Error messages involving templates are difficult to decipher. Excessive usage of STL templates leads to code bloat. Template instantiation tends to increase compilation time and memory usage (sometimes by as much as an order of magnitude). STL implementations non-standardized. 35

The three parts of STL Containers Algorithms Iterators 36

Standard Template Library Two important types of data structures in the STL: containers: classes that store data and impose some organization on it OR a class that stores data and organizes it in some fashion. iterators: like pointers; provides mechanisms for accessing elements in a container OR similar to a pointer and is used to access the individual data elements in a container. 37

Containers What are they? Containers are objects that hold other objects. Two types of container classes in STL: sequential containers: organize and access data sequentially, as in an array. These include vector, dequeue, and list containers. associative containers: use keys to allow data elements to be quickly accessed (allowing efficient retrieval of values based on keys). These include set, multiset, map, and multimap containers. 38

Creating Container Objects To create a list of int, write list<int> mylist; To create a vector of string objects, write vector<string> myvector; Requires the vector header file 39

Iterators (1) We need a subscript operator to access container elements BUT in a generic way STL provides objects called iterators can point at an element can access the value within that element can move from one element to another They are independent of any particular container thus a generic mechanism 40

Iterators (2) Generalization of pointers, used to access information in containers Four types: forward(uses++) bidirectional(uses++and--) random-access input(can be used with cin and istream objects) output(can be used with cout and ostream objects) 41

Iterators Given a vector which has had values placed in the first 4 locations: vector<int> v 9 4 15 3 v.begin() v.end() v.begin() will return the iterator value for the first slot, v.end() for the next empty slot 42

Iterators Each STL container declares an iterator type can be used to define iterator objects To declare an iterator object the identifier iterator must be preceded by name of container scope operator :: Example: vector<int>:: iterator vecIter = v.begin() 43

Containers and Iterators Each container class defines an iterator type, used to access its contents The type of an iterator is determined by the type of the container: list<int>::iterator x; list<string>::iterator y; x is an iterator for a container of type list<int> 44

Containers and Iterators Each container class defines functions that return iterators: begin(): returns iterator to item at start end(): returns iterator denoting end of container 45

Containers and Iterators Iterators support pointer-like operations: if iter is an iterator: *iter is the item it points to: this dereferences the iterator iter++ advances to the next item in the container iter-- backs up in the container The end() iterator points to past the end: it should never be dereferenced 46

Traversing a Container Given a vector: vector<int> v; for (int k=1; k<= 5; k++) v.push_back(k*k); Traverse it using iterators: vector<int>::iteratoriter=v.begin(); while (iter != v.end()) { cout << *iter << " "; iter++} 1 4 9 16 25 Prints 47

Algorithms STL contains algorithms implemented as function templates to perform operations on containers. Requires algorithm header file Collection of algorithms includes binary_search for_each max_element random_shuffle and others count find min_element sort 48

Using STL algorithms Many STL algorithms manipulate portions of STL containers specified by a begin and end iterator max_element(iter1, iter2) finds max element in the portion of a container delimited by iter1, iter2 min_element(iter1, iter2) is similar to above 49

MoreSTLalgorithms random_shuffle(iter1,iter2) randomly reorders the portion of the container in the given range sort(iter1,iter2) sorts the portion of the container specified by the given range 50