CS1C – Advanced Programming in C++Saddleback College Fall 2011 – J TateyamaIntroduction to the Standard Template LibraryChapter 16CS1C – Saddleback CollegeIntroduction to Standard Template Library (STL)In CS1B we looked at and implemented the stack and queue as Abstract Data TypesAlmost all nontrivial computer programs maintain a collection of elements of one type or another; so the study of data structures is fundamental to computer scienceThere are a small set of structures that are well suited for many software applications so it makes sense to create a library of these reusable data structuresSTL provides many of the basic algorithms and data structures of computer science Developed at Hewlett-Packard by Alexander Stepanov and Meng Lee, the STL is a collection of libraries containing data structures and basic algorithms written in C++ The STL is a collection of templates with a type parameter used to represent the type of the data to be storedThese classes are often referred to as container classesCS1C – Saddleback CollegeSTL OrganizationThe STL is organized into containers, iterators, and algorithms.Containers–A group of class templates that provide standardized, generic structures for storing data–Containers hold a collection of objects of a specific type–The data that can be stored in these containers has been left unspecified and these containers are often referred to as abstract containers–Have small interfaces and are easily understood–Can be greatly extended by the use of generic algorithmsCS1C – Saddleback CollegeContainers3 Categories of Containers–sequential containers (or fundamental containers)•Like an array, sequence containers organize data in a sequential fashion•Sequential containers include vector, list, and deque–adapters•Layered on top of the fundamental containers•adapter containers include stack, queue, and priority_queue–associative containers•Associative containers organize their data using keys which allow elements stored in the container to be accessed randomly•This random access is more rapid than sequential access •Associative containers include map, multimap, set and multisetUnlike items contained in the standard libraries such as <iostream> and <iomanip> that work on specific types, these classes and algorithms are generic (template classes and template functions).CS1C – Saddleback CollegeContainers Constraints and SelectionThere are constraints on the types that can be held by a container–element type must support assignment (=)–must also be able to copy objects of the element type–containers of IO types are invalid as they do not support assignment or copying–containers of references are also invalidSelecting the type of container for a task depends on the following–Type of operations required–Evaluations of execution timesCS1C – Saddleback CollegeContainer ClassesContainer Description Header Filevector A dynamic array <vector>stack A stack <stack>deque A double-ended queue <deque>list A linear list <list>map Stores key/value pairs <map>multimap Stores key value pairs with 1-many relationship<map>set Set in which each element is unique<set>multiset A set in which each element may not be unique<set>priority_queue A priority queue <queue>queue A queue <queue>bitset A set of bits <bitset>CS1C – Saddleback CollegeIterators–Are a means of accessing elements in the container including finding the predecessor and successor of an element–Iterators provide a way in which the algorithms can act upon the containers–Iterators are objects that act, more or less, like pointers–Unlike pointers, iterators can never have NULL value–Like pointers (*p).m is the same as p → m; same holds for iterators Iterator Types and Supported OperationsRandom Access ==, !=, ++, --, *, and → as well as iterator + n and iterator - iteratorBidirectional ==, !=, ++, --, *, and → (Note: it is best to use the prefix form (++p) unless needed to capture the old value)Forward ==, !=, ++, *, and → Input ==, !=, ++, *, and → only for returning a valueOutput ==, !=, ++, *, and → only for assignmentCS1C – Saddleback CollegePair IteratorsA pair of iterators can be used to describe a range of valuesThis is similar to using 2 pointers to describe a contiguous region in memory; however the values referenced by the iterators need not be adjacent memory locationsMember functions:–begin – describes a starting location–end – returns a past-the-end location Mismatched Iterators – always ensure an iterator pair come from the same container – this code compiles but an infinite loop may occurvector<int> valsOne;vector<int> valsTwo;....vector<int>::iterator p = valsOne.begin();while (p != valsTwo.end()){....++p}Watch out for mismatchesCS1C – Saddleback CollegeAlgorithmsAct on containersAre a set of function templates that provide functions used to perform common operations such as sorting and searching container objectsCapabilities include initialization, sorting, searching and transforming the contents of containersMany algorithms operate on a range of elements within a containerIf you do an internet search for C++ STL you will find many sites with information and sample programsCS1C – Saddleback CollegeGeneric AlgorithmsIn CS1A you learned about algorithmsIn CS1B you learned that algorithms can be represented by functionsLast week we generalized functions by using parameters and created Function TemplatesGeneric Algorithms take this one step further–They can not only operate with different values and data types–But they can also operate with different types of containersHow?–Use of templates allows algorithms to work with multiple types–Use iterators to tie the algorithms to containers, thus allowing the algorithm to work with many different containersFor generic algorithms–template arguments typically represent the type of iterator the algorithm will useCS1C – Saddleback CollegeFor Each Algorithm Example#include <iostream>#include <list>#include <algorithm> <<-- NOTICE THE NEW INCLUDEusing namespace std;void print_element(int value){cout << value << "\n";}int main(){list<int> vals; // Loading the list with some calculated values for(int i = 0; i < 10; ++i) vals.push_front(i*2+1); for_each(vals.begin(), vals.end(), print_element);}CS1C – Saddleback CollegeFor Each Algorithm