Department of Computer and Information Science, School of Science, IUPUIIntroductionNeed for STLStructure of STLContainersSequence ContainersAssociative ContainersSequence Containers - Example 1Slide 9Sequence Containers - Example 1 (output)Sequence Containers - Example 2Slide 12Sequence Containers - Example 2 (output)Sequence Containers - Example 3Slide 15Sequence Containers - Example 3 (output)Sequence Containers - Example 4Sequence Containers - Example 4 (output)AlgorithmsNon-mutating sequence operationsMutating sequence operationsSorting operationsC++ STL Reference01/14/19 1Dale RobertsDepartment of Computer and Information Science,School of Science, IUPUIDale Roberts, LecturerComputer Science, IUPUIE-mail: [email protected] Template LibraryStandard Template Library01/14/19 2Dale RobertsIntroduction Introduction Industrial revolution - Reuse software, not re-Industrial revolution - Reuse software, not re-write write Two main paradigms that permit code reuse - Two main paradigms that permit code reuse - Object oriented design, Generic Programming Object oriented design, Generic Programming OOD facilitates code reuse by data hiding - OOD facilitates code reuse by data hiding - Inheritance and Polymorphism Inheritance and Polymorphism Generic programming facilitates code reuse by Generic programming facilitates code reuse by data independence - Templates and Overloading data independence - Templates and Overloading STL is a combination of both OOD and Generic STL is a combination of both OOD and Generic programming - collection of generic algorithms programming - collection of generic algorithms and containers that communicate through and containers that communicate through iterators. iterators.01/14/19 3Dale RobertsNeed for STL Need for STL Reusability - adaptability and efficiency Reusability - adaptability and efficiency Highly adaptive components are usually implemented Highly adaptive components are usually implemented using complex inheritance, virtual function and RTTI - using complex inheritance, virtual function and RTTI - inefficient to be widely used inefficient to be widely used Highly efficient components - written in low level, Highly efficient components - written in low level, platform dependent code - non-portable, hard to platform dependent code - non-portable, hard to maintain maintain Solution:- Templates - containers and algorithms Solution:- Templates - containers and algorithms Drawback - Programmer implemented (home made), not Drawback - Programmer implemented (home made), not portable, less than 100% bug free and no common portable, less than 100% bug free and no common interface. interface. Thus, the lack of platform independent, bug free generic Thus, the lack of platform independent, bug free generic components gave rise to the creation of a library components gave rise to the creation of a library containing generic components with generic algorithms containing generic components with generic algorithms and common interface.and common interface.01/14/19 4Dale RobertsStructure of STL Structure of STL The Standard Template Library contains the The Standard Template Library contains the following five components following five components Containers Containers Iterators Iterators Algorithms Algorithms Function objects Function objects Adaptors Adaptors01/14/19 5Dale RobertsContainers Containers Holds other object as its element Holds other object as its element The allocation and deallocation of these objects The allocation and deallocation of these objects are controlled through constructors, are controlled through constructors, destructors, insertion, and erase operation destructors, insertion, and erase operation There are two types - There are two types - Sequence containers - vector, queue, dequeue, and list Sequence containers - vector, queue, dequeue, and list Associative containers - set, map, and multimap Associative containers - set, map, and multimap01/14/19 6Dale RobertsSequence Containers Sequence Containers Organizes a finite set of same type objects into a strictly Organizes a finite set of same type objects into a strictly linear arrangement linear arrangement There are 3 basic types - There are 3 basic types - vectorvector, , listlist and and dequeuedequeue The containers The containers queuequeue and and stackstack are implemented using are implemented using dequeuedequeue The following are the header files used: The following are the header files used: HeaderHeaderContentsContentsvectorvectorAn array of T An array of T listlistA doubly linked list of T A doubly linked list of T dequedequeA double ended queue of T A double ended queue of T queuequeueA queue of T A queue of T stackstackA stack of T A stack of T01/14/19 7Dale RobertsAssociative ContainersAssociative ContainersFacilitates fast retrieval of data based on Facilitates fast retrieval of data based on keykeys s There are four types of associative containers - There are four types of associative containers - setset, , multisetmultiset, , mapmap, , multimapmultimap Parameterized on Parameterized on keykey and an ordering relation Compare and an ordering relation Compare The The keykeys in s in setset and and mapmap are unique keys are unique keys The The keykeys in s in multisetmultiset and and multimapmultimap are equal keys are equal keys The following header files are used: The following header files are used: HeaderHeaderContentsContentsmap map An associative array of T An associative array of T set set A set of T A set of T bitset bitset A set of Boolean values A set of Boolean values01/14/19 8Dale RobertsSequence Containers - Example 1 Sequence Containers - Example 1 #include<iostream>#include<iostream>#include<vector>#include<vector>#include<string>#include<string>//using namespace std;//using namespace std;int main(){int main(){//An object of vector containing string objects are created//An object of vector containing string objects are createdvector <string> vs;vector <string> vs;//Make room for 10 strings using the reserve(n) function.//Make room for 10 strings using the reserve(n) function.//The reserve(n) function just allocates memory for n elements.//The reserve(n) function just allocates memory for n elements.//Thus, this changes the value returned by the capacity() funciton.//Thus, this changes the value returned by the capacity() funciton.vs.reserve(10);vs.reserve(10);//The member function push_back(T) appends a single