EECE 330 Chapter 1 Old Lectures, Fall 2007

An Overview of C++ Douglas C. Schmidt Professor Department of EECS d.schmidt@vanderbilt.edu Vanderbilt University www.dre.vanderbilt.edu/∼schmidt/ (615) 343-8197 August 31, 2009 An Overview of C++ Douglas C. Schmidt C++ Overview • C++ was designed at AT&T Bell Labs by Bjarne Stroustrup in the early 80’s – The original cfront translated C++ into C for portability ∗ However, this was difficult to debug and potentially inefficient – Many native host machine compilers now exist ∗ e.g., Borland, DEC, GNU, HP, IBM, Microsoft, Sun, Symantec, etc. • C++ is a mostly upwardly compatible extension of C that provides: 1. Stronger typechecking 2. Support for data abstraction 3. Support for object-oriented programming 4. Support for generic programming Vanderbilt University 1 An Overview of C++ Douglas C. Schmidt C++ Design Goals • As with C, run-time efficiency is important – Unlike other languages (e.g., Ada) complicated run-time libraries have not traditionally been required for C++ ∗ Note, that there is no language-specific support for concurrency, persistence, or distribution in C++ • Compatibility with C libraries & traditional development tools is emphasized, e.g., – Object code reuse ∗ The storage layout of structures is compatible with C ∗ e.g., support for X-windows, standard ANSI C library, & UNIX/WIN32 system calls via extern block – C++ works with the make recompilation utility Vanderbilt University 2 An Overview of C++ Douglas C. Schmidt C++ Design Goals (cont’d) • “As close to C as possible, but no closer” – i.e., C++ is not a proper superset of C → backwards compatibility is not entirely maintained ∗ Typically not a problem in practice... • Note, certain C++ design goals conflict with modern techniques for: 1. Compiler optimization – e.g., pointers to arbitrary memory locations complicate register allocation & garbage collection 2. Software engineering – e.g., separate compilation complicates inlining due to difficulty of interprocedural analysis – Dynamic memory management is error-prone Vanderbilt University 3 An Overview of C++ Douglas C. Schmidt Major C++ Enhancements 1. C++ supports object-oriented programming features • e.g., abstract classes, inheritance, & virtual methods 2. C++ supports data abstraction & encapsulation • e.g., the class mechanism & name spaces 3. C++ supports generic programming • e.g., parameterized types 4. C++ supports sophisticated error handling • e.g., exception handling 5. C++ supports identifying an object’s type at runtime • e.g., Run-Time Type Identification (RTTI) Vanderbilt University 4 An Overview of C++ Douglas C. Schmidt Important Minor Enhancements • C++ enforces type checking via function prototypes • Provides type-safe linkage • Provides inline function expansion • Declare constants that can be used to define static array bounds with the const type qualifier • Built-in dynamic memory management via new & delete operators • Namespace control Vanderbilt University 5 An Overview of C++ Douglas C. Schmidt Useful Minor Enhancements • The name of a struct, class, enum, or union is a type name • References allow “call-by-reference” parameter modes • New type-secure extensible iostreams I/O mechanism • “Function call”-style cast notation • Several different commenting styles • New mutable type qualifier • New bool boolean type Vanderbilt University 6 An Overview of C++ Douglas C. Schmidt Questionable Enhancements • Default values for function parameters • Operator & function overloading • Variable declarations may occur anywhere statements may appear within a block • Allows user-defined conversion operators • Static data initializers may be arbitrary expressions Vanderbilt University 7 An Overview of C++ Douglas C. Schmidt Language Features Not Part of C++ 1. Concurrency • “Concurrent C” by Gehani • Actor++ model by Lavender & Kafura 2. Persistence • Object Store, Versant, Objectivity • Exodus system & E programming language 3. Garbage Collection • USENIX C++ 1994 paper by Ellis & Detlefs • GNU g++ 4. Distribution • CORBA, RMI, COM+, SOAP, etc. Vanderbilt University 8 An Overview of C++ Douglas C. Schmidt Strategies for Learning C++ • Focus on concepts & programming techniques – Don’t get lost in language features • Learn C++ to become a better programmer – More effective at designing & implementing – Design Patterns • C++ supports many different programming styles • Learn C++ gradually – Don’t have to know every detail of C++ to write a good C++ program Vanderbilt University 9 An Overview of C++ Douglas C. Schmidt Stack Example • The following slides examine several alterative methods of implementing a Stack – Begin with C & evolve up to various C++ implementations • First, consider the “bare-bones” implementation: typedef int T; #define MAX_STACK 100 /* const int MAX_STACK = 100; */ T stack[MAX_STACK]; int top = 0; T item = 10; stack[top++] = item; // push ... item = stack[--top]; // pop • Obviously not very abstract... Vanderbilt University 10 An Overview of C++ Douglas C. Schmidt Data Hiding Implementation in C • Define the interface to a Stack of integers in C in Stack.h: /* Type of Stack element. */ typedef int T; /* Stack interface. */ int create (int size); int destroy (void); void push (T new_item); void pop (T *old_top); void top (T *cur_top); int is_empty (void); int is_full (void); Vanderbilt University 11 An Overview of C++ Douglas C. Schmidt Data Hiding Implementation in C (cont’d) • /* File stack.c */ #include "stack.h" static int top_, size_; /* Hidden within this file. */ static T *stack_; int create (int size) { top_ = 0; size_ = size; stack_ = malloc (size * sizeof (T)); return stack_ == 0 ? -1 : 0; } void destroy (void) { free ((void *) stack_); } void push (T item) { stack_[top_++] = item;} void pop (T *item) { *item = stack_[--top_]; } void top (T *item) { *item = stack_[top_ - 1]; } int is_empty (void) { return top_ == 0; } int is_full (void) { return top_ == size_; } Vanderbilt University 12 An Overview of C++ Douglas C. Schmidt Data Hiding Implementation in C (cont’d) • Use case #include "stack.h" void foo (void) { T i; push (10); /* Oops, forgot to call create! */ push (20); pop (&i); destroy (); } • Main problems: 1. The programmer must call create() first & destroy() last! 2. There is only one stack & only one type of stack 3. Name space pollution... 4. Non-reentrant Vanderbilt University 13 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C • An ADT Stack interface in C: typedef int T; typedef struct { size_t top_, size_; T *stack_; } Stack; int Stack_create (Stack *s, size_t size); void Stack_destroy (Stack *s); void Stack_push (Stack *s, T item); void Stack_pop (Stack *, T *item); /* Must call before pop’ing */ int Stack_is_empty (Stack *); /* Must call before push’ing */ int Stack_is_full (Stack *); /* ... */ Vanderbilt University 14 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C (cont’d) • An ADT Stack implementation in C: #include "stack.h" int Stack_create (Stack *s, size_t size) { s->top_ = 0; s->size_ = size; s->stack_ = malloc (size * sizeof (T)); return s->stack_ == 0 ? -1 : 0; } void Stack_destroy (Stack *s) { free ((void *) s->stack_); s->top_ = 0; s->size_ = 0; s->stack_ = 0; } void Stack_push (Stack *s, T item) { s->stack_[s->top_++] = item; } void Stack_pop (Stack *s, T *item) { *item = s->stack_[--s->top__]; } int Stack_is_empty (Stack *s) { return s->top_ == 0; } Vanderbilt University 15 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C (cont’d) • Use case void foo (void) { Stack s1, s2, s3; /* Multiple stacks! */ T item; Stack_pop (&s2, &item); /* Pop’d empty stack */ /* Forgot to call Stack_create! */ Stack_push (&s3, 10); s2 = s3; /* Disaster due to aliasing!!! */ /* Destroy uninitialized stacks! */ Stack_destroy (&s1); Stack_destroy (&s2); } Vanderbilt University 16 An Overview of C++ Douglas C. Schmidt Main problems with Data Abstraction in C 1. No guaranteed initialization, termination, or assignment 2. Still only one type of stack supported 3. Too much overhead due to function calls 4. No generalized error handling... 5. The C compiler does not enforce information hiding e.g., s1.top_ = s2.stack_[0]; /* Violate abstraction */ s2.size_ = s3.top_; /* Violate abstraction */ Vanderbilt University 17 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C++ • We can get encapsulation and more than one stack: typedef int T; class Stack { public: Stack (size_t size); Stack (const Stack &s); void operator= (const Stack &); ~Stack (void); void push (const T &item); void pop (T &item); bool is_empty (void) const; bool is_full (void) const; private: size_t top_, size_; T *stack_; }; Vanderbilt University 18 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C++ (cont’d) • Manager operations Stack::Stack (size_t s): top_ (0), size_ (s), stack_ (new T[s]) {} Stack::Stack (const Stack &s) : top_ (s.top_), size_ (s.size_), stack_ (new T[s.size_]) { for (size_t i = 0; i < s.size_; i++) stack_[i] = s.stack_[i]; } void Stack::operator = (const Stack &s) { if (this == &s) return; T *temp_stack = new T[s.size_]; delete [] stack_; for (size_t i = 0; i < s.size_; i++) temp_stack[i] = s.stack_[i]; stack_ = temp_stack; top_ = s.top_; size_ = s.size_; } Stack::~Stack (void) { delete [] stack_; } Vanderbilt University 19 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C++ (cont’d) • Accessor & worker operations bool Stack::is_empty (void) const { return top_ == 0; } bool Stack::is_full (void) const { return top_ == size_; } void Stack::push (const T &item) { stack_[top_++] = item; } void Stack::pop (T &item) { item = stack_[--top_]; } Vanderbilt University 20 An Overview of C++ Douglas C. Schmidt Data Abstraction Implementation in C++ (cont’d) • Use case #include "Stack.h" void foo (void) { Stack s1 (1), s2 (100); T item; if (!s1.is_full ()) s1.push (473); if (!s2.is_full ()) s2.push (2112); if (!s2.is_empty ()) s2.pop (item); // Access violation caught at compile-time! s2.top_ = 10; // Termination is handled automatically. } Vanderbilt University 21 An Overview of C++ Douglas C. Schmidt Benefits of C++ Data Abstraction Implemenation 1. Data hiding & data abstraction, e.g., Stack s1 (200); s1.top_ = 10 // Error flagged by compiler! 2. The ability to declare multiple stack objects Stack s1 (10), s2 (20), s3 (30); 3. Automatic initialization & termination { Stack s1 (1000); // constructor called automatically. // ... // Destructor called automatically } Vanderbilt University 22 An Overview of C++ Douglas C. Schmidt Drawbacks with C++ Data Abstraction Implementation 1. Error handling is obtrusive • Use exception handling to solve this (but be careful)! 2. The example is limited to a single type of stack element (int in this case) • We can use C++ “parameterized types” to remove this limitation 3. Function call overhead • We can use C++ inline functions to remove this overhead Vanderbilt University 23 An Overview of C++ Douglas C. Schmidt Exception Handling Implementation in C++ (cont’d) • C++ exceptions separate error handling from normal processing typedef int T; class Stack { public: class Underflow { /* ... */ }; class Overflow { /* ... */ }; Stack (size_t size); ~Stack (void); void push (const T &item) throw (Overflow); void pop (T &item) throw (Underflow); bool is_empty (void) const; bool is_full (void) const; private: size_t top_, size_; T *stack_; }; Vanderbilt University 24 An Overview of C++ Douglas C. Schmidt Exception Handling Implementation in C++ (cont’d) • Stack.cpp void Stack::push (const T &item) throw (Stack::Overflow) { if (is_full ()) throw Stack::Overflow (); stack_[top_++] = item; } void Stack::pop (T &item) throw (Stack::Underflow) { if (is_empty ()) throw Stack::Underflow (); item = stack_[--top_]; } Vanderbilt University 25 An Overview of C++ Douglas C. Schmidt Exception Handling Implementation in C++ (cont’d) • Stack.cpp Stack::Stack (const Stack &s): : top_ (s.top_), size_ (s.size_), stack_ (0) { scoped_array<T> temp_array (new T[s.size_]); for (size_t i = 0; i < s.size_; i++) temp_array[i] = s.stack_[i]; temp_array.swap (stack_); } void Stack::operator = (const Stack &s) { if (this == &s) return; // Check for self-assignment Stack t (s); std::swap (t.top_, top_); std::swap (t.size__, size_); std::swap (t.stack_, stack_); } Vanderbilt University 26 An Overview of C++ Douglas C. Schmidt Exception Handling Implementation in C++ (cont’d) • scoped_array extends auto_ptr to arrays • Deletion of array is guaranteed on destruction of scoped_array template <typename T> class scoped_array { public: explicit scoped_array (T *p = 0) : ptr_ (p) {} ~scoped_array () { delete [] ptr_; } T &operator[](std::ptrdiff_t i) const { return ptr_[i]; } T *get() const { return ptr_; } void swap (T *&b) { T *tmp = b; b = ptr_; ptr_ = tmp; } private: T *ptr_; // Disallow copying scoped_array (const scoped_array<T> &); scoped_array &operator=(const scoped_array<T> &); }; Vanderbilt University 27 An Overview of C++ Douglas C. Schmidt Exception Handling Implementation in C++ (cont’d) • Use case #include "Stack.h" void foo (void) { Stack s1 (1), s2 (100); try { T item; s1.push (473); s1.push (42); // Exception, push’d full stack! s2.pop (item); // Exception, pop’d empty stack! s2.top_ = 10; // Access violation caught! } catch (Stack::Underflow) { /* Handle underflow... */ } catch (Stack::Overflow) { /* Handle overflow... */ } catch (...) { /* Catch anything else... */ throw; } } // Termination is handled automatically. } Vanderbilt University 28 An Overview of C++ Douglas C. Schmidt Template Implementation in C++ • A parameterized type Stack class interface using C++ template <typename T> class Stack { public: Stack (size_t size); ~Stack (void) void push (const T &item); void pop (T &item); bool is_empty (void) const; bool is_full (void) const; private: size_t top_, size_; T *stack_; }; • To simplify the following examples we’ll omit exception handling, but note that it’s important to ensure exception-safety guarantees! Vanderbilt University 29 An Overview of C++ Douglas C. Schmidt Template Implementation in C++ (cont’d) • A parameterized type Stack class implementation using C++ template <typename T> inline Stack<T>::Stack (size_t size) : top_ (0), size_ (size), stack_ (new T[size]) { } template <typename T> inline Stack<T>::~Stack (void) { delete [] stack_; } template <typename T> inline void Stack<T>::push (const T &item) { stack_[top_++] = item; } template <typename T> inline void Stack<T>::pop (T &item) { item = stack_[--top_]; } Vanderbilt University 30 An Overview of C++ Douglas C. Schmidt Template Implementation in C++ (cont’d) • Note minor changes to accommodate parameterized types #include "Stack.h" void foo (void) { Stack<int> s1 (1000); Stack<float> s2; Stack< Stack <Activation_Record> *> s3; s1.push (-291); s2.top_ = 3.1416; // Access violation caught! s3.push (new Stack<Activation_Record>); Stack <Activation_Record> *sar; s3.pop (sar); delete sar; // Termination is handled automatically } Vanderbilt University 31 An Overview of C++ Douglas C. Schmidt Template Implementation in C++ (cont’d) • Another parameterized type Stack class template <typename T, size_t SIZE> class Stack { public: Stack (void); ~Stack (void) void push (const T &item); void pop (T &item); private: size_t top_, size_; T stack_[SIZE]; }; • No need for dynamic memory, though SIZE must be const, e.g., Stack<int, 200> s1; Vanderbilt University 32 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ • Problems with previous examples: – Changes to the implementation will require recompilation & relinking of clients – Extensions will require access to the source code • Solutions – Combine inheritance with dynamic binding to completely decouple interface from implementation & binding time – This requires the use of C++ abstract base classes Vanderbilt University 33 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • Defining an abstract base class in C++ template <typename T> class Stack { public: virtual ~Stack (void) = 0; // Need implementation! virtual void push (const T &item) = 0; virtual void pop (T &item) = 0; virtual bool is_empty (void) const = 0; virtual bool is_full (void) const = 0; void top (T &item) { // Template Method pop (item); push (item); } }; • By using “pure virtual methods,” we can guarantee that the compiler won’t allow instantiation! Vanderbilt University 34 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • Inherit to create a specialized stack implemented via an STL vector: #include "Stack.h" #include <vector> template <typename T> class V_Stack : public Stack<T> { public: enum { DEFAULT_SIZE = 100 }; V_Stack (size_t size = DEFAULT_SIZE); virtual void push (const T &item); virtual void pop (T &item); virtual bool is_empty (void) const; virtual bool is_full (void) const; private: size_t top_; // built-in std::vector<T> stack_; // user-defined }; Vanderbilt University 35 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • class V Stack implementation template <typename T> V_Stack<T>::V_Stack (size_t size): top_ (0), stack_ (size) {} template <typename T> void V_Stack<T>::push (const T &item) { stack_[top_++] = item; } template <typename T> void V_Stack<T>::pop (T &item) { item = stack_[--top_]; } template <typename T> int V_Stack<T>::is_full (void) const { return top_ >= stack_.size (); } Vanderbilt University 36 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • Inheritance can also create an linked list stack: template <typename T> class Node; // forward declaration. template <typename T> class L_Stack : public Stack<T> { public: enum { DEFAULT_SIZE = 100 }; L_Stack (size_t hint = DEFAULT_SIZE); ~L_Stack (void); virtual void push (const T &new_item); virtual void pop (T &top_item); virtual bool is_empty (void) const { return head_ == 0; } virtual bool is_full (void) const { return 0; } private: // Head of linked list of Node<T>’s. Node<T> *head_; }; Vanderbilt University 37 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • class Node implementation template <typename T> class Node { friend template <typename T> class L_Stack; public: Node (T i, Node<T> *n = 0): item_ (i), next_ (n) {} private: T item_; Node<T> *next_; }; • Note that the use of the “Cheshire cat” idiom allows the library writer to completely hide the representation of class V Stack... Vanderbilt University 38 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • class L Stack implementation: template <typename T> L_Stack<T>::L_Stack (size_t): head_ (0) {} template <typename T> void L_Stack<T>::push (const T &item) { Node<T> *t = new Node<T> (item, head_); head_ = t; } template <typename T> void L_Stack<T>::pop (T &top_item) { top_item = head_->item_; Node<T> *t = head_; head_ = head_->next_; delete t; } template <typename T> L_Stack<T>::~L_Stack (void) { for (T t; head_ != 0; pop (t)) continue; } Vanderbilt University 39 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • Using our abstract base class, it is possible to write code that does not depend on the stack implementation, e.g., template <typename T> Stack<T> *make_stack (bool use_V_Stack) { return use_V_Stack ? new V_Stack<T> : new L_Stack<T>; } template <typename T> void foo (Stack<T> *stack, const T &t) { T s; stack->push (t); stack->pop (s); // ... } foo<int> (make_stack<int> (true), 10); Vanderbilt University 40 An Overview of C++ Douglas C. Schmidt Object-Oriented Implementation in C++ (cont’d) • Moreover, we can make changes at run-time without modifying, recompiling, or relinking existing code – i.e., can use “dynamic linking” to select stack representation at run-time, e.g., char stack_symbol[MAXNAMLEN]; char stack_file[MAXNAMLEN]; cin >> stack_file >> stack_symbol; void *handle = ACE_OS::dlopen (stack_file); void *sym = ACE_OS::dlsym (handle, stack_symbol); if (Stack<int> *sp = // Note use of RTTI dynamic_cast <Stack<int> *> (sym)) foo (sp); • Note, no need to stop, modify, & restart an executing application! – Naturally, this requires careful configuration management... Vanderbilt University 41 An Overview of C++ Douglas C. Schmidt Summary • A major contribution of C++ is its support for defining abstract data types (ADTs) & for generic programming – e.g., classes, parameterized types, & exception handling • For some systems, C++’s ADT support is more important than using the OO features of the language • For other systems, the use of C++’s OO features is essential to build highly flexible & extensible software – e.g., inheritance, dynamic binding, & RTTI Vanderbilt University 42 EECE 330 Data Structures and Algorithms American University of Beirut Topic #01: INTRODUCTION TO ALGORITHM ANALYSIS; SORTING PROBLEM READINGS: [Shaffer] Chapters 2,3 REFERENCES: [CLRS] Chapters 1,2 • MOTIVATION: Linear Search, Binary Search • SORTING PROBLEM • INSERTION SORT • MERGE SORT – E.C.E., AUB – 1 THE SORTING PROBLEM; MOTIVATION • One of the most frequently performed tasks −→ Introduction to “algorithm analysis” • Having “sorted” data makes searching more efficient Recall Linear Search Binary Search – E.C.E., AUB – 2 Linear Search: Pseudocode: LINEAR-SEARCH(A[1,··· ,n],key) 1 for i ← 1 to n 2 do if A[i] = key 3 then return i 4 return Not Found Translation into C++: Running Time: – E.C.E., AUB – 3 Binary Search: Assumes the array is already sorted Compare the key to middle element If smaller, search first half If greater, search second half BINARY-SEARCH(A[1,··· ,n],key) 1 min ← 1 2 max ← n 3 while min ≤ max 4 do mid ← (min+max)/2 5 if key = A[mid] 6 then return mid 7 else if key > A[mid] 8 then min ← mid +1 9 else max ← mid −1 10 return Not Found – E.C.E., AUB – 4 Translation into C++: Running Time: – E.C.E., AUB – 5 THE SORTING PROBLEM; DEFINITION Definition: Sorting Problem Input: sequence (a1,a2,··· ,an) of numbers Output: permutation (a′ 1,a′ 2,··· ,a′ n) such that a′ 1 ≤ a′ 2 ≤ ··· ≤ a′ n Example: −→ Need an algorithm to solve this problem We will see 2 algorithms: Insertion sort and Merge sort – E.C.E., AUB – 6 INSERTION SORT Like sorting your deck of cards in a game of “Tarnib” Example: INSERTION-SORT(A[1,··· ,n]) 1 for i ← 2 to n 2 do key ← A[i] 3 j ← i−1 4 while j > 0 and A[j] > key 5 do A[j +1] ← A[j] 6 j ← j −1 7 A[j +1] ← key – E.C.E., AUB – 7 Correctness Proof Claim: At the end of each iteration of the for loop, A[1,··· ,i] consists of the original elements of A[1,··· ,i] but in sorted order Proof of claim: Proof of correctness of Insertion-Sort: Note: loop-invariant properties ⇐⇒ arguments by induction – E.C.E., AUB – 8 Running Time Best case? Worst case? “Average” case? −→ Function of the input size −→ Machine dependent ! Notes: Remove machine-dependencies: ignore machine-dependent constants Consider asymptotic growth: as input-size n increases to infinity −→ Drop low order terms −→ Ignore constants Example: – E.C.E., AUB – 9 Notation: We say 5n2 +n ∈ Θ(n2) or simply 5n2 +n = Θ(n2) Examples: 2n−6√n = Θ(n), 4n+logn = Θ(n) Formal definitions ... later Worst-case running-time of Insertion-Sort: Let T(n) be the max running time on all inputs of size n Occurs when input is sorted in reverse order! Fix such input Let u(i) be the time of the i-th iteration in the “for loop” – E.C.E., AUB – 10 T(n) = n ∑ i=2 u(i) Now u(i) = c2 +c3 +c4i+c5(i−1)+c6(i−1)+c7, Since n ∑ i=2 i = ⇒ T(n) = – E.C.E., AUB – 11 MERGE SORT It’s a recursive procedure as opposed to iterative (like Insertion Sort) Idea: Input A[1···n] (i) If n = 1 DONE (ii) If n > 1, recursively sort A[1,··· ,⌈n/2⌉] and A[⌈n/2⌉+1,··· ,n] (iii) Merge the two sorted arrays Big Picture: Divide & Conquer approach Divide the problem into a number of subproblems Conquer subproblems by solving them recursively (until sizes are small enough) Combine the solutions of the subproblems into the solution of the original problem Example: – E.C.E., AUB – 12 MERGE-SORT(A, p,r) 1 if p < r 2 then q ← ⌊ p+r 2 ⌋ 3 MERGE-SORT(A, p,q) 4 MERGE-SORT(A,q+1,r) 5 MERGE(A[p,··· ,q],A[q+1,··· ,r]) Note: Initial call: Merge-Sort (A,1,n) The “Merge” function takes as input two sorted arrays – E.C.E., AUB – 13 MERGE(L[1,··· ,n1],R[1,··· ,n2]) 1 Construct an all-zero array C of size n1 +n2 2 i ← 1 3 j ← 1 4 for k ← 1 to n1 +n2 5 do if L[i] ≤ R[j] 6 then C[k] ← L[i] 7 i ← i+1 8 else C[k] ← R[j] 9 j ← j +1 10 return C Running-Time of “Merge”: – E.C.E., AUB – 14 Correctness Proof of Merge-sort ... (by induction) Worst-case running time of Merge-Sort Let T(n) be the max running time on all inputs of size n Recurrence: T(n) = � Θ(1) if n = 1 T � ⌈n 2⌉ � +T � ⌊n 2⌋ � +Θ(n) if n > 1 Consider a simplified version of the recurrence: n a power of 2 general case ... later Assume the running time of “Merge” is cn, where c is a positive constant ⇒ Recurrence: T(n) = � c0 if n = 1 2T �n 2 � +cn if n > 1 – E.C.E., AUB – 15 Solution: using the Recursion-tree method depth/height of the tree? count the leaves: T(n) = – E.C.E., AUB – 16 Summary • Insertion Sort • Merge Sort • Note: There are hidden constants in asymptotic running-time analysis • Recursive algorithm, Divide and Conquer approach, Recurrence relation, Recursion-Tree method, proof by Induction – E.C.E., AUB – 17 EECE 330 Data Structures and Algorithms American University of Beirut Topic #05: C++ REVIEW READINGS: [Malik] Chapters 14, 13 • TEMPLATES • VIRTUAL FUNCTIONS – E.C.E., AUB – 1 TEMPLATES Example • Arrays are essentially pointers in disguise An array “a” is a pointer to (memory address of) the first element of the array “a” “T a[size];” creates a variable a of type “T *” it will be pointing to “a[0]” Similarly, “a” is simply “&a[0]” In general: “a[i]” is equivalent to “*(a+i)” “a+i” is equivalent to “&a[i]” – E.C.E., AUB – 2 • To pass an array as an argument to a function void f(int * a, int n) { //do something } Or void f(int a[], int n) { //do something } – E.C.E., AUB – 3 Or void f(int a[10]) { //assume a has size 10 //do something } Misleading!, because • What if we want the compiler to fully enforce the type on the argument? (a function that takes as parameter an array of integers of size 10, i.e. the whole thing as one entity, not just the pointer) −→ pass the array by reference It fully preserves the information about the type of the array – E.C.E., AUB – 4 void f(int (&a)[10]) { . . . } • We lost some flexibility! We need a function for every possible array size void f(int (&a)[1]) { //process array of size 1 } void f(int (&a)[2]) { //process array of size 2 } . . void f(int (&a)[100]) { //process array of size 100 } – E.C.E., AUB – 5 • what if we can generate the appropriate function only when we need it? • C++ provides such ability using a template template <int n> void f(int (&a)[n]) { //process array of size n } • Represents an infinite number of functions, one for each possible value of n • Compiler however does not generate all of them (it is impossible to do so) • When needed, the compiler performs the appropriate specialization of the template, determines a specific value for n (called the parameter of the template) generates the corresponding function – E.C.E., AUB – 6 Can go further! make the function independent of the type of elements of the array template<class T, int n> void f(T (&a)[n]) { //process an array of Ts of size n } General syntax: for templated functions and classes template <class Type> declaration; “Type” is the type of the data; specifies type of parameters, return type of a function, declares variables within a function “declaration” is either a function declaration or a class declaration “class” refers to any user-defined type or built-in type – E.C.E., AUB – 7 #include <iostream> #include <string> using namespace std; template <class Type> Type larger(Type x, Type y); int main() { string str1 = "Hello"; string str2 = "Happy"; cout << "Larger of 5 and 6 = " << larger(5, 6) << endl; cout << "Larger of A and B = " << larger(’A’, ’B’) << endl; cout << "Larger of 5.6 and 3.2 = " << larger(5.6, 3.2) << endl; cout << "Larger of " << str1 << " and " << str2 << " = " << larger(str1, str2) << endl; return 0; } template<class Type> Type larger(Type x, Type y) { if (x >= y) return x; else return y; } – E.C.E., AUB – 8 Syntax: definition of member functions of templated classes template<class Type> returnType className<Type>::memberFunction(){ //do whatever it needs to do} −→ The function members of a class template are considered function templates className<specificType> anObject; For the compiler to specialize the template, all parameters of the template must be known at compile time Passing parameters to a function takes effect at run time Passing a parameter to a class template takes effect at compile time – E.C.E., AUB – 9 Consequences: Cannot compile the implementation file independently of the user code Can put class definition and the definitions of the function templates directly in the user code Can put class definition and the definitions of the function templates in the same header file Or you can have declaration in header .h file along with a directive to include definition from a definition .cpp file – E.C.E., AUB – 10 VIRTUAL FUNCTIONS • Recall a class object can be passed by value or by reference, but parameters need to match • In C++, we can pass an object of a derived class to a formal parameter of the base class type • Without virtual functions, C++ would associate the function with the proper class. This is called compile-time binding: necessary code to call a specific function is generated by the compiler. Also known as static binding – E.C.E., AUB – 11 Example: class baseClass { public: void print(); baseClass( int u = 0); private: int x; }; #include <iostream> #include "baseClass.h" using namespace std; void baseClass::print() //Note