stl

CS 342: Object-Oriented Software Development Lab The C++ Standard Template Library Venkita Subramonian and Chris Gill Department of Computer Science and Engineering Washington University, St. Louis fvenkita,cdgillg@cs.wustl.edu http://classes.cec.wustl.edu/�cs342/home/ CS 342: OO Software Development Lab The C++ STL The C++ Standard Template Library � What is the STL? � Generic programming: why use the STL? � STL overview: helper class and function templates, containers, iterators, generic algorithms, function objects, adaptors � STL examples � Conclusions: writing less, doing more � References for more information on the STL Copyright c 1997-2001 Dept. of Computer Science, Washington University 1 CS 342: OO Software Development Lab The C++ STL What is the STL? The Standard Template Library provides a set of well structured generic C++ components that work together in a seamless way. –Alexander Stepanov & Meng Lee, The Standard Template Library Copyright c 1997-2001 Dept. of Computer Science, Washington University 2 CS 342: OO Software Development Lab The C++ STL What is the STL (cont’d)? � A collection of composable class and function templates – Helper class and function templates: operators, pair – Container and iterator class templates – Generic algorithms that operate over iterators – Function objects – Adaptors � Enables generic programming in C++ – Each generic algorithm can operate over any iterator for which the necessary operations are provided – Extensibile: can support new algorithms, containers, iterators Copyright c 1997-2001 Dept. of Computer Science, Washington University 3 CS 342: OO Software Development Lab The C++ STL Generic Programming: why use the STL? � Reuse: “write less, do more” – The STL hides complex, tedious and error prone details – The programmer can then focus on the problem at hand – Type-safe plug compatibility between STL components � Flexibility – Iterators decouple algorithms from containers – Unanticipated combinations easily supported � Efficiency – Templates avoid virtual function overhead – Strict attention to time complexity of algorithms Copyright c 1997-2001 Dept. of Computer Science, Washington University 4 CS 342: OO Software Development Lab The C++ STL STL Overview: helper operators template inline bool operator != (const T& t, const U& u) { return !(t == u); } template inline bool operator > (const T& t, const U& u) { return u < t; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 5 CS 342: OO Software Development Lab The C++ STL STL Overview: helper operators (cont’d) template inline bool operator <= (const T& t, const U& u) { return !(u < t); } template inline bool operator >= (const T& t, const U& u) { return !(t < u); } Copyright c 1997-2001 Dept. of Computer Science, Washington University 6 CS 342: OO Software Development Lab The C++ STL STL Overview: helper operators (cont’d) � Question: why require that parameterized types support operator == as well as operator and >= and <= are implemented only in terms of operator < on u and t (and ! on boolean results) – Could implement operator == as !(t < u) && !(u < t) so classes T and U only had to provide operator < and did not have to provide operator == � Answer: efficiency (two operator < calls are needed to implement operator == implicitly) � Answer: allows equivalence classes of ordered types Copyright c 1997-2001 Dept. of Computer Science, Washington University 7 CS 342: OO Software Development Lab The C++ STL STL Overview: operators example class String { public: String (const char *s) : s_ (s) {} String (const String &s) : s_ (s.s_) {} bool operator < (const String &s) const {return (strcmp (this->s_, s.s_) < 0) ? true : false;} bool operator == (const String &s) const {return (strcmp (this->s_, s.s_) == 0) ? true : false;} const char * s_; }; #include int main (int, char *[]) { const char * wp = "world"; const char * hp = "hello"; String w_str (wp); String h_str (hp); cout << false << endl; // 0 cout << true << endl; // 1 cout << (h_str < w_str) << endl; cout << (h_str == w_str) << endl; cout << (hp < wp) << endl; cout << (hp == wp) << endl; return 0; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 8 CS 342: OO Software Development Lab The C++ STL STL Overview: pair helper class template struct pair { // Data members T first; U second; // Default constructor pair () {} // Constructor from values pair (const T& t, const U& u) : first (t), second (u) {} }; Copyright c 1997-2001 Dept. of Computer Science, Washington University 9 CS 342: OO Software Development Lab The C++ STL STL Overview: pair helper class (cont’d) // Pair equivalence comparison operator template inline bool operator == (const pair& lhs, const pair& rhs) { return lhs.first == rhs.first && lhs.second == rhs.second; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 10 CS 342: OO Software Development Lab The C++ STL STL Overview: pair helper class (cont’d) // Pair less than comparison operator template inline bool operator < (const pair& lhs, const pair& rhs) { return lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second); } Copyright c 1997-2001 Dept. of Computer Science, Washington University 11 CS 342: OO Software Development Lab The C++ STL STL Overview: pair example class String { public: String (const char *s) : s_ (s) {} String (const String &s) : s_ (s.s_) {} bool operator < (const String &s) const {return (strcmp (this->s_, s.s_) < 0) ? true : false;} bool operator == (const String &s) const {return (strcmp (this->s_, s.s_) == 0) ? true : false;} const char * s_; }; #include #include int main (int, char *[]) { pair pair1 (3, String("hello")); pair pair2 (2, String("world")); cout << (pair1 == pair2) << endl; cout << (pair1 < pair2) << endl; return 0; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 12 CS 342: OO Software Development Lab The C++ STL STL Overview: containers, iterators, algorithms � Containers: – Sequence: vector, deque, list – Associative: set, multiset, map, multimap � Iterators: – Input, output, forward, bidirectional, random access – Each container declares a trait for the type of iterator it provides � Generic Algorithms: – Sequence (mutating and non-mutating), sorting, numeric Copyright c 1997-2001 Dept. of Computer Science, Washington University 13 CS 342: OO Software Development Lab The C++ STL STL Overview: containers � STL containers are Abstract Data Types (ADTs) � All containers are parameterized by the type(s) they contain � Sequence containers are ordered � Associative containers are unordered � Each container declares an iterator typedef (trait) � Each container provides special factory methods for iterators Copyright c 1997-2001 Dept. of Computer Science, Washington University 14 CS 342: OO Software Development Lab The C++ STL STL Overview: sequence containers � A vector is similar to our Array and Stack class templates – provides reallocation, indexed storage, push back, pop back � A deque (pronounced “deck”) is a double ended queue – adds efficient insertion and removal at the beginning as well as at the end of the sequence � A list has constant time insertion and deletion at any point in the sequence (not just at the beginning and end) – performance trade-off: does not offer a random access iterator Copyright c 1997-2001 Dept. of Computer Science, Washington University 15 CS 342: OO Software Development Lab The C++ STL STL Overview: associative containers � A set is an unordered collection of unique keys – e.g., a set of student id numbers � A map associates a value with each unique key – e.g., a student’s first name � A multiset or a multimap can support multiple equivalent (non- unique) keys – e.g., student last names � Uniqueness is determined by an equivalence relation – e.g., strncmp might treat last names that are distinguishable by strcmp as being the same Copyright c 1997-2001 Dept. of Computer Science, Washington University 16 CS 342: OO Software Development Lab The C++ STL STL Overview: container example #include #include #include "String.h" int main (int argc, char *argv[]) { int i; vector projects; // Names of the projects for (i = 1; i < argc; ++i) // Start with 1st arg { projects.push_back (String (argv [i])); cout << projects [i-1].s_ << endl; } return 0; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 17 CS 342: OO Software Development Lab The C++ STL STL Overview: iterators � Iterator categories depend on type parameterization rather than on inheritance: allows algorithms to operate seamlessly on both native (i.e., pointers) and user-defined iterator types � Iterator categories are hierarchical, with more refined categories adding constraints to more general ones – Forward iterators are both input and output iterators, but not all input or output iterators are forward iterators – Bidirectional iterators are all forward iterators, but not all forward iterators are bidirectional iterators – All random access iterators are bidirectional iterators, but not all bidirectional iterators are random access iterators Copyright c 1997-2001 Dept. of Computer Science, Washington University 18 CS 342: OO Software Development Lab The C++ STL STL Overview: iterators (cont’d) � Input iterators are used to read values from a sequence. � An input iterator must allow the following operations – Copy ctor and assignment operator for that same iterator type – Operators == and != for comparison with iterators of that type – Operators * (can be const) and ++ (both prefix and postfix) � Note that native types that meet the requirements (i.e., pointers) can be used as iterators of various kinds Copyright c 1997-2001 Dept. of Computer Science, Washington University 19 CS 342: OO Software Development Lab The C++ STL STL Overview: iterators (cont’d) � Output iterators differ from input operators as follows: – Operators = and == and != need not be defined (but could be) – Must support non-const operator * (e.g., *iter = 3) � Forward iterators must implement (roughly) the union of requirements for input and output iterators, plus a default ctor Copyright c 1997-2001 Dept. of Computer Science, Washington University 20 CS 342: OO Software Development Lab The C++ STL STL Overview: iterators (cont’d) � Bidirectional iterators must implement the requirements for forward iterators, plus decrement operators (prefix and postfix) � Random access iterators must implement the requirements for bidirectional iterators, plus: – Arithmetic assignment operators += and -= – Operators + and - (must handle symmetry of arguments) – Ordering operators < and > and <= and >= – Subscript operator [ ] Copyright c 1997-2001 Dept. of Computer Science, Washington University 21 CS 342: OO Software Development Lab The C++ STL STL Overview: iterator example #include #include #include "String.h" int main (int argc, char *argv[]) { vector projects; // Names of the projects for (int i = 1; i < argc; ++i) { projects.push_back (String (argv [i])); } for (vector::iterator j = projects.begin (); j != projects.end (); ++j) { cout << (*j).s_ << endl; } return 0; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 22 CS 342: OO Software Development Lab The C++ STL STL Overview: generic algorithms � Algorithms operate over iterators rather than containers � Each container declares an iterator as a trait – vector and deque declare random access iterators – list, map, set, multimap, and multiset declare bidirectional iterators � Each container declares factory methods for its iterator type: – begin ( ), end ( ), rbegin ( ), rend ( ) � Composing an algorithm with a container is done simply by invoking the algorithm with iterators for that container � Templates provide compile-time type safety for combinations of containers, iterators, and algorithms Copyright c 1997-2001 Dept. of Computer Science, Washington University 23 CS 342: OO Software Development Lab The C++ STL STL Overview: generic algorithms (cont’d) � Some examples of STL generic algorithms: – find: returns a forward iterator positioned at the first element in the given sequence range that matches a passed value – mismatch: returns a pair of iterators positioned respectively at the first elements that do not match in two given sequence ranges – copy: copies elements from a sequence range into an output iterator – replace: replaces all instances of a given existing value with a given new value, within a given sequence range – random shuffle: shuffles the elements in the given sequence range Copyright c 1997-2001 Dept. of Computer Science, Washington University 24 CS 342: OO Software Development Lab The C++ STL STL Overview: generic algorithm example #include #include #include #include "String.h" int main (int argc, char *argv[]) { vector projects; for (int i = 1; i < argc; ++i) projects.push_back (String (argv [i])); vector::iterator j = find (projects.begin (), projects.end (), String ("Lab8")); if (j == projects.end ()) return 1; assert ((*j) == String ("Lab8")); return 0; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 25 CS 342: OO Software Development Lab The C++ STL STL Overview: function objects � Function objects (aka functors) declare and define operator ( ) � STL provides helper base class templates unary function and binary function to facilitate writing user-defined function objects � STL provides a number of common-use function object class templates: – arithmetic: plus, minus, times, divides, modulus, negate – comparison: equal to, not equal to, greater, less, greater equal, less equal – logical: logical and, logical or, logical not � A number of STL generic algorithms can take STL-provided or user- defined function object arguments to extend algorithm behavior Copyright c 1997-2001 Dept. of Computer Science, Washington University 26 CS 342: OO Software Development Lab The C++ STL STL Overview: function objects example #include #include #include #include "String.h" int main (int argc, char *argv[]) { vector projects; for (int i = 0; i < argc; ++i) { projects.push_back (String (argv [i])); } // Sort in descending order: note explicit ctor for greater sort (projects.begin (), projects.end (), greater ()); return 0; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 27 CS 342: OO Software Development Lab The C++ STL STL Overview: adaptors � STL adaptors implement the Adapter design pattern – i.e., they convert one interface into another interface clients expect � Container adaptors include Stack, Queue, Priority Queue � Iterator adaptors include reverse and insert iterators � Function adaptors include negators and binders � STL adaptors can be used to narrow interfaces (e.g., a Stack adaptor for vector) Copyright c 1997-2001 Dept. of Computer Science, Washington University 28 CS 342: OO Software Development Lab The C++ STL STL Example: course schedule � Goals: – Read in a list of course names, along with the corresponding day(s) of the week and time(s) each course meets � Days of the week are read in as characters M,T,W,R,F,S,U � Times are read as unsigned decimal integers in 24 hour HHMM format, with no leading zeroes (e.g., 11:59pm should be read in as 2359, and midnight should be read in as 0) – Sort the list according to day of the week and then time of day – Detect any times of overlap between courses and print them out – Print out an ordered schedule for the week � STL provides most of the code for the above Copyright c 1997-2001 Dept. of Computer Science, Washington University 29 CS 342: OO Software Development Lab The C++ STL STL Example: course schedule (cont’d) // Meeting.h #include struct Meeting { enum Day_Of_Week {MO, TU, WE, TH, FR, SA, SU}; static Day_Of_Week day_of_week (char c); Meeting (const char * title, Day_Of_Week day, unsigned int start_time, unsigned int finish_time); Meeting (const Meeting & m); Meeting & operator = (const Meeting & m); bool operator < (const Meeting & m) const; bool operator == (const Meeting & m) const; // Meeting.h, continued ... const char * title_; // Title of the meeting Day_Of_Week day_; // Week day of meeting unsigned int start_time_; // Meeting start time in HHMM format unsigned int finish_time_; // Meeting finish time in HHMM format }; // Helper operator for output ostream & operator << (ostream &os, const Meeting & m); Copyright c 1997-2001 Dept. of Computer Science, Washington University 30 CS 342: OO Software Development Lab The C++ STL STL Example: course schedule (cont’d) // Meeting.cc #include #include "Meeting.h" Meeting::Day_Of_Week Meeting::day_of_week (char c) { switch (c) { case ’M’: return Meeting::MO; case ’T’: return Meeting::TU; case ’W’: return Meeting::WE; case ’R’: return Meeting::TH; case ’F’: return Meeting::FR; case ’S’: return Meeting::SA; case ’U’: return Meeting::SU; default: assert (!"not a week day"); return Meeting::MO; } } // Meeting.cc, continued ... Meeting::Meeting (const char * title, Day_Of_Week day, unsigned int start_time, unsigned int finish_time) : title_ (title), day_ (day), start_time_ (start_time), finish_time_ (finish_time) { } Meeting::Meeting (const Meeting & m) : title_ (m.title_), day_ (m.day_), start_time_ (m.start_time_), finish_time_ (m.finish_time_) { } Copyright c 1997-2001 Dept. of Computer Science, Washington University 31 CS 342: OO Software Development Lab The C++ STL STL Example: course schedule (cont’d) // Meeting.cc, continued ... Meeting & Meeting::operator = (const Meeting & m) { this->title_ = m.title_; this->day_ = m.day_; this->start_time_ = m.start_time_; this->finish_time_ = m.finish_time_; return *this; } bool Meeting::operator == (const Meeting & m) const { return (this->day_ == m.day_ && ((this->start_time_ < m.start_time_ && m.start_time_ < this->finish_time_) || (m.start_time_ < this->start_time_ && this->start_time_ < m.finish_time_))) ? true : false; } // Meeting.cc, continued ... bool Meeting::operator < (const Meeting & m) const { return (day_ < m.day_ || (day_ == m.day_ && start_time_ < m.start_time_) || (day_ == m.day_ && start_time_ == m.start_time_ && finish_time_ < m.finish_time_)) ? true : false; } Copyright c 1997-2001 Dept. of Computer Science, Washington University 32 CS 342: OO Software Development Lab The C++ STL STL Example: course schedule (cont’d) // Meeting.cc, continued ... ostream & operator << (ostream &os, const Meeting & m) { const char * dow = " "; switch (m.day_) { case Meeting::MO: dow="M "; break; case Meeting::TU: dow="T "; break; case Meeting::WE: dow="W "; break; case Meeting::TH: dow="R "; break; case Meeting::FR: dow="F "; break; case Meeting::SA: dow="S "; break; case Meeting::SU: dow="U "; break; } return os << m.title_ << " " << dow << m.start_time_ << " " << m.finish_time_ << endl; } #include // Main.cc #include #include #include #include #include "Meeting.h" int parse_args (int argc, char * argv[], vector& schedule) { for (int i = 1; i < argc; i+=4) { schedule.push_back (Meeting (argv [i], Meeting::day_of_week (*argv [i+1]), static_cast (atoi (argv [i+2])), static_cast (ato