The c ++ Programming Language Lecture 3: Standard Template Library Generic Programming
The C++ Programming Language Lecture 3: Standard Template Library & Generic Programming
Brief introduction
Brief Introduction
Generic Programming Core idea Data structures and data types should be independent Data structures and algorithms should be independent Algorithms and data types should be independent (generic STL supports GP well Including 2 parts Container: vector, list, map, set..(basic data structures Generic Algorithm: find, sort, merge..(frequently used operations
Generic Programming ◼ Core idea ◼ Data structures and data types should be independent ◼ Data structures and algorithms should be independent ◼ Algorithms and data types should be independent (generic) ◼ STL supports GP well ◼ Including 2 parts ◼ Container: vector, list, map, set,… (basic data structures) ◼ Generic Algorithm: find, sort, merge,… (frequently used operations)
Generic Programming(cont u Container supported the independence between data types and data structures list, list Iterators supported the independence between data structures and algorithms sort(vec, begin, vec. endO; Function templates supported the independence between algorithms and data types template &, ElemType&)
Generic Programming (cont.) ◼ Container supported the independence between data types and data structures ◼ list, list ◼ Iterators supported the independence between data structures and algorithms ◼ sort(vec.begin(), vec.end()); ◼ Function templates supported the independence between algorithms and data types ◼ template binary_search(const vector&, ElemType&);
From Pointers to iterators
From Pointers to Iterators
From pointers to iterators J Request 1 u Given a vector of integer and an integer value, implement a findo function that if the value exists n vector, return a pointer to it, return 0 otherwise int* find(const vector& vec, int ivalue) for (int iX= 0; iX< vecsize; iX++) if (vec[iX]== iValue) return &vec[iXJH } return o
From pointers to iterators ◼ Request 1: ◼ Given a vector of integer and an integer value, implement a find() function that if the value exists in vector, return a pointer to it, return 0 otherwise int* find(const vector& vec, int iValue) { for (int iX = 0; iX < vec.size(); iX++) { if (vec[iX] == iValue) { return &vec[iX]; } } return 0; }
From pointers to iterators(cont,) J Request 2 u Let the previous findo function support any data types that having test equivalence operator(==) defined template ElemType* find( const vector &vec, const ElemType &value) for (int iX= 0; iX vec size; iX++) if (vec[iX]== Value) return &vec[]; return o
From pointers to iterators (cont.) ◼ Request 2: ◼ Let the previous find() function support any data types that having test equivalence operator (==) defined template ElemType* find(const vector &vec, const ElemType &Value) { for (int iX = 0; iX < vec.size(); iX++) { if (vec[iX] == Value) { return &vec[iX]; } } return 0; }
From pointers to iterators(cont,) Request 3 Let the previous findo function also support data elements in arrays Another overloaded function may solve it, but currently we try to use a single implementation Design philosophy: Divide and Conquer Pass the elements in array to findo, but never let the function be aware of the form of array a Pass the elements in vector to findo, but never let the function be aware of the form of vector
From pointers to iterators (cont.) ◼ Request 3: ◼ Let the previous find() function also support data elements in arrays ◼ Another overloaded function may solve it, but currently we try to use a single implementation ◼ Design philosophy: Divide and Conquer ◼ Pass the elements in array to find(), but never let the function be aware of the form of array ◼ Pass the elements in vector to find(), but never let the function be aware of the form of vector
From pointers to iterators(cont,) u For array, common ways are using pointers and subscription template ElemType* find(const ElemType* array int iSize, const ElemType &value) if((! array)I size 1) return 0 for(int iX= O; iX iSize; iX++) if (array[] = Value) return &array; return OF
From pointers to iterators (cont.) ◼ For array, common ways are using pointers and subscription template ElemType* find(const ElemType* array , int iSize, const ElemType &Value) { if ((! array) || size < 1) return 0; for (int iX = 0; iX < iSize; iX++) { if (array[iX] == Value) { return &array[iX]; } } return 0; }
From pointers to iterators(cont,) a better implementation adding a sentinel pointer that pointing to the next address of the last element, which could replace the size parameter using pointer dereference to replace subscription template ElemType* find(const Elem Type* first, const ElemType* last, const ElemType &value) if((! first)II(! last)) return O; for (i first != last; first++) if first = Value) return first } return OF }
From pointers to iterators (cont.) ◼ A better implementation: ◼ adding a sentinel pointer that pointing to the next address of the last element, which could replace the size parameter ◼ using pointer dereference to replace subscription template ElemType* find(const ElemType* first , const ElemType* last , const ElemType &Value) { if ((! first) || (! last)) return 0; for (; first != last; first++) { if (*first == Value) return first; } return 0; }