tailieunhanh - Chapter 19 Standard Template Library

tandard Template Library STL generic set operation functions All assume containers stored in sorted order, Containers set, map, multiset, multimap. DO store in sorted order, so all set functions apply | Chapter 19 Standard Template Library Learning Objectives Iterators Constant and mutable iterators Reverse iterators Containers Sequential containers Container adapters stack and queue Generic Algorithms Big-O notation Sequence, set, and sorting algorithms Introduction Recall stack and queue data structures We created our own Large collection of standard data structures exists Make sense to have standard portable implementations of them! Standard Template Library (STL) Includes libraries for all such data structures Like container classes: stacks and queues Iterators Recall: generalization of a pointer Typically even implemented with pointer! "Abstraction" of iterators Designed to hide details of implementation Provide uniform interface across different container classes Each container class has "own" iterator type Similar to how each data type has own pointer type Manipulating Iterators Recall using overloaded operators: ++, --, ==, != * So if p is iterator variable, *p gives access | Chapter 19 Standard Template Library Learning Objectives Iterators Constant and mutable iterators Reverse iterators Containers Sequential containers Container adapters stack and queue Generic Algorithms Big-O notation Sequence, set, and sorting algorithms Introduction Recall stack and queue data structures We created our own Large collection of standard data structures exists Make sense to have standard portable implementations of them! Standard Template Library (STL) Includes libraries for all such data structures Like container classes: stacks and queues Iterators Recall: generalization of a pointer Typically even implemented with pointer! "Abstraction" of iterators Designed to hide details of implementation Provide uniform interface across different container classes Each container class has "own" iterator type Similar to how each data type has own pointer type Manipulating Iterators Recall using overloaded operators: ++, --, ==, != * So if p is iterator variable, *p gives access to data pointed to by p Vector template class Has all above overloads Also has members begin() and end() (); //Returns iterator for 1st item in c (); //Returns "test" value for end Cycling with Iterators Recall cycling ability: for (p=();p!=();p++) process *p //*p is current data item Big picture so far Keep in mind: Each container type in STL has own iterator types Even though they’re all used similarly Display Iterators Used with a Vector (1 of 2) Display Iterators Used with a Vector (2 of 2) Vector Iterator Types Iterators for vectors of ints are of type: std::vector::iterator Iterators for lists of ints are of type: std::list::iterator Vector is in std namespace, so need: using std::vector::iterator; Kinds of Iterators Different containers different iterators Vector iterators Most "general" form All operations work with vector iterators Vector container great for iterator examples Random Access: Display Bidirectional .