Generic Programming in Generic Programming in C++C++

(1)

Generic Programming in Generic Programming in C++ C++

Giuseppe Attardi Giuseppe Attardi Università di Pisa Università di Pisa

(2)

Generic Parameters Generic Parameters

 Function for squaring a number:Function for squaring a number:

sqr(x) { return x * x; }

 C version:C version:

int sqr(int x) { return x * x; }

 Multiple versions:Multiple versions:

int sqrInt(int x) { return x * x; }

 C++ overloading:C++ overloading:

int sqr(int x) { return x * x; }

double sqr(double x) { return x * x; }

(3)

C++ Templates C++ Templates

template<class T>

T sqr(T x) { return x * x; } T sqr(T x) { return x * x; }

 Compiler automatically generates a version Compiler automatically generates a version for each parameter type used by a program:

for each parameter type used by a program:

int a = 3;

double b = 3.14;

int aa = sqr(a);

double bb = sqr(b);

(4)

Notes: macros’ limits Notes: macros’ limits

#define sqr(x) ((x) * (x))

#define sqr(x) ((x) * (x)) int aa = sqr(a++);

int aa = sqr(a++);

int aa = ((a++) * (a++));

int aaa = sqr(aa);

#define fact(n) (n == 0) ? 1 : fact(n-1) * n

#define SQR(T) T sqr(T x) {return x * x; }

#define SQR(T) T sqr(T x) {return x * x; } SQR(int);

SQR(int);

SQR(double);

sqr(a);

sqr(b);

(5)

Other types as well?

class Complex { class Complex {

double real, imag;

Complex operator *(Complex y) { Complex operator *(Complex y) {

return Complex(

real * y.real – imag * y.imag, real * y.real – imag * y.imag,

real * y.imag + imag * y.real); } real * y.imag + imag * y.real); } }}

Complex c(1, 2);

Complex cc = sqr(c);

(6)

Compile time checking Compile time checking

template<class T>

void swap(T& a, T& b) { void swap(T& a, T& b) {

const T temp = a;

a = b;

b = temp;

}}

int a = 5, b = 9; int& ar = a; int* ap = *a;

ar++; *ap = (*ap)+1 ar++; *ap = (*ap)+1 swap(a, b);

swap(a, b); // OK// OK double c = 9.0;

double c = 9.0;

swap(a, c);

swap(a, c); // error// error

(7)

C++ Standard Template C++ Standard Template

Library Library

 Goal: represent algorithms in as general form Goal: represent algorithms in as general form as possible without compromising efficiency as possible without compromising efficiency

 Extensive use of templatesExtensive use of templates

 Only uses static binding (an inlining)Only uses static binding (an inlining)

 Use of Use of iteratorsiterators for decoupling algorithms for decoupling algorithms from containers

from containers

 Iterator: abstraction of pointersIterator: abstraction of pointers

(8)

STL Organization STL Organization

 ContainersContainers

 vector, deque, list, set, map, …

 AlgorithmsAlgorithms

 for_each, find, transform, sort

 IteratorsIterators

 forward_iterator, reverse_iterator, istream_iterator,

…

 Function ObjectsFunction Objects

 plus, equal, logical_and, project1

 AllocatorsAllocators

(9)

Examples from C++

Annotations Annotations

 vectorvector

 inner_productinner_product

 sortsort

(10)

Forward Iterator Forward Iterator

int main(int argc, char **argv) { int main(int argc, char **argv) {

vector<string> args(argv, argv + argc);

vector<string>::iterator iter = args.begin();

for ( ; iter != args.end(); ++iter ) for ( ; iter != args.end(); ++iter )

cout << *iter << " ";

cout << endl;

(11)

Reverse Iterator Reverse Iterator

vector<string>::reverse_iterator iter = vector<string>::reverse_iterator iter = args.rbegin();

args.rbegin();

for (; iter != args.rend(); ++iter )for (; iter != args.rend(); ++iter ) cout << *iter << " ";

cout << *iter << " ";

cout << endl;cout << endl;

(12)

Inner Product Inner Product

vector<unsigned> ia1 = {1, 2, 3, 4, 5, 6, 7};

vector<unsigned> ia2 = {7, 6, 5, 4, 3, 2, 1};

// dot product // dot product

inner_product(ia1.begin(), ia1.end(), ia2.begin(), 0);

(13)

inner_product: definition inner_product: definition

T inner_product(InputIterator first1, T inner_product(InputIterator first1,

InputIterator last1, InputIterator first2, InputIterator last1, InputIterator first2,

T init, BinaryFunction op1, BinaryFunction op2); T init, BinaryFunction op1, BinaryFunction op2);

 Initializes Initializes resultresult to to initinit

 For each iterator For each iterator i1i1 in in [first1, last1)[first1, last1), , and i2 =

and i2 = first2 + (i1 - first1))first2 + (i1 - first1)) updates

updates resultresult as follows: as follows:

result = op1(result, op2(*i1, *i2)) result = op1(result, op2(*i1, *i2))

(14)

Inner Product (string Inner Product (string

concat) concat)

class Join { class Join {

public:

Join(string const &sep): sep(sep) {}

string operator()(string const& s1, string const& s2) { string operator()(string const& s1, string const& s2) {

return s1 + sep + s2; } return s1 + sep + s2; } private:

private:

string sep;

};};

vector<string> names1= {"Frank", "Karel", "Piet"};

vector<string> names2 = {"Brokken", "Kubat", "Plomp"};

inner_product(names.begin(), names1.end(), names2.begin(), "\t“, inner_product(names.begin(), names1.end(), names2.begin(), "\t“,

Join("\n"), Join(" ")) ; Join("\n"), Join(" ")) ;

(15)

Parametrized Bubblesort Parametrized Bubblesort

template<class T>

struct greater { struct greater {

bool operator()(const T& a, const T& b) const { bool operator()(const T& a, const T& b) const {

return a > b;

};};

template<class T>

struct less { struct less {

bool operator()(const T& a, const T& b) const {bool operator()(const T& a, const T& b) const { return a < b;

return a < b;

};};

(16)

Note Note

int x = 3, y = 5;

bool b = greater<int>()(x, y);

(17)

Function object version Function object version

template<class T, class C=less<T> >

void bubblesort(vector<T> a, const C& comp) { void bubblesort(vector<T> a, const C& comp) { for (unsigned i = 0; i < a.size(); ++i)for (unsigned i = 0; i < a.size(); ++i)

for (unsigned j = i+1; j < a.size(); ++j)for (unsigned j = i+1; j < a.size(); ++j) if (comp(a[i], a[j]))

if (comp(a[i], a[j]))

swap(a[i], a[j]);

};};

(18)

Traditional Functional Traditional Functional

version version

template<class T>

void bubblesort(vector<T> a, bool (*comp)(T&, void bubblesort(vector<T> a, bool (*comp)(T&,

T&)) { T&)) {

for (unsigned i = 0; i < size; ++i)for (unsigned i = 0; i < size; ++i)

for (unsigned j = i+1; j < size; ++j)for (unsigned j = i+1; j < size; ++j) if (comp(a[i], a[j]))

if (comp(a[i], a[j]))

swap(a[i], a[j]);

};};

(19)

Bubblesort usage Bubblesort usage

vector<int> x = {1, 5, 3, 4, 2};

bubblesort(x, greater<int>());

bubblesort(x, less<int>());

// implicit type inference // implicit type inference

vector<float> f;

bubblesort(f);

bubblesort(f); // uses less<float>// uses less<float>

(20)

(Partial) Template (Partial) Template

Specialization Specialization

 an alternate version of the class template code can be provided for certain template parameters

template<>

void bubblesort<vector<string&> >(…) { } void bubblesort<vector<string&> >(…) { }

 partial specialization: when only some of the template parameters are supplied

(21)

Template Enumeration Template Enumeration

template<class T>

class Vector : public vector<T> { class Vector : public vector<T> {

public:

Enumeration getEnumeration() { Enumeration getEnumeration() {

return (Enumeration(*this));

}}

class Enumeration { … } class Enumeration { … } };};

(22)

Enumeration (2) Enumeration (2)

class Enumeration { class Enumeration {

private:

vector<T> const& v; vector<T> const& v;

unsigned idx; unsigned idx;

public:

Enumeration(vector<T> const& vector) :Enumeration(vector<T> const& vector) : v(vector), idx(0) { }v(vector), idx(0) { }

T const& next() { // uses TT const& next() { // uses T

if (idx == vp.size())if (idx == vp.size())

throw NoSuchElementException(index);throw NoSuchElementException(index);

return vp[idx++];return vp[idx++];

} }

bool hasNext() { return idx < vp.size(); }bool hasNext() { return idx < vp.size(); } };};

(23)

Enumeration (3) Enumeration (3)

Vector<int> vector;

……

Vector<int>::Enumeration en = Vector<int>::Enumeration en =

vector.getEnumeration();

while (en.hasNext()) while (en.hasNext())

cout << en.next() << endl;

(24)

Issue: template Issue: template

instantiation instantiation

// file sumVector.h // file sumVector.h

template <class T>

T sumVector(T* array, unsigned n) T sumVector(T* array, unsigned n) {{

T sum(0);

for (int i = 0; i < n; ++i) for (int i = 0; i < n; ++i) sum += array[i];sum += array[i];

return sum;

} }

(25)

Instantiation (1) Instantiation (1)

#include "sumVector.h"

int x[] = {1, 2};

double y[] = {1.1, 2.2};

cout << sumVector(x, 2) << endl cout << sumVector(x, 2) << endl

<< sumVector(y, 2) << endl;

 If the same template function definition is included in If the same template function definition is included in different source files, separately compiled and linked, different source files, separately compiled and linked,

there will be only one instantiation, per type of there will be only one instantiation, per type of

template function template function

(26)

Instantiation (2) Instantiation (2)

 declaredeclare a template function, if it is a template function, if it is knownknown that that the required instantiation is available in

the required instantiation is available in another source file:

another source file:

template<class T>

T sumVector(T* tp, unsigned n);

int v[] = {1, 2};

sumVector(v, 2);

(27)

Instantiation (3) Instantiation (3)

 declaredeclare template functions in header files, keep template functions in header files, keep the definition in a template source file:

the definition in a template source file:

template<class T>

T sumVector(T* tp, unsigned n) { T sumVector(T* tp, unsigned n) {

return *tp;

}}

static void* p1 = static void* p1 =

static_cast<int (*)(int*, unsigned)>(sumVector);

(28)

Forcing Instantiations Forcing Instantiations

static void* p[] = { static void* p[] = {

static_cast<int (*)(int*, static_cast<int (*)(int*,

unsigned)>(sumVector), unsigned)>(sumVector),

static_cast<double (*)(double*, static_cast<double (*)(double*,

unsigned)>(sumVector), unsigned)>(sumVector),

static_cast<unsigned (*)(unsigned *, static_cast<unsigned (*)(unsigned *, unsigned)>(sumVector)

unsigned)>(sumVector) }; };

(29)

Explicit Instantiations Explicit Instantiations

template<class T>

T sumVector(T *tp, unsigned n) T sumVector(T *tp, unsigned n) { return (*tp); }

{ return (*tp); }

template int sumVector<int>(int *, unsigned);

template double sumVector<double>(double *, template double sumVector<double>(double *,

unsigned);

template unsigned sumVector<unsigned>(unsigned *, template unsigned sumVector<unsigned>(unsigned *,

unsigned);