11.Standard Template Library

11.Standard Template Library

Computer Science and Software Engineering University of Wisconsin - Platteville 11.Standard Template Library Yan Shi CS/SE 2630 Lecture Notes What is STL? The Standard Template Library (STL) is a subset of ISO/ANSI C++ standard library. It provides 3 kinds of facilities: containers iterators generic algorithms Appendix E in the textbook C++ References: http://www.cplusplus.com/reference/stl/ STL Container

Sequence containers: maintain the original ordering of inserted elements list, vector, deque, array, forward_list Associative containers: elements are inserted in a pre-defined order map, set, multiset, multimap Unordered associative containers: elements are inserted in a pre-defined order unordered_map, unordered_set, unordered_multiset, unordered_multimap Container adapters: simple variations of the sequence containers queue, stack, priority_queue they do NOT support iterators: cannot be used by STL algorithms! Container classes are template classes e.g. list, stack STL Iterators STL iterators enable cycling through a container, one item at a time allow C++ programs to access items in a container without knowing the internal structure of the container

each STL container class defines one or more iterator types: list::iterator iter; similar as GetNext()operation it simply represents the location of an item within the container a generalization of a pointer *iter // item referred to by iter iter++ // move to the next item Types of Iterators Input iterators: can only step forward; permit only fetching; used for istream Output iterators: can only step forward; permit only storing; used for ostream Forward iterators:

permit both fetching and storing Bidirectional iterators can move both forward and backward Random access iterators allow direct (random) access to any item in a container Random access > Bidirectional > Forward > Input/Output Behavior defines iterator: anything that acts like an iterator is an iterator! e.g., pointers to an array is an iterator. Iterator Operations Operations Input *r Y

r++; ++r Y Output Forward Bidirecti Random onal Access Y Y Y Y Y Y Y

Y Y r--; --r r == r2; r != r2 *r = value Y Y Y Y Y Y

Y Y Y r[i] Y r += i; r -= i; Y r + i; r i; Y r r2 //# of items Y

r < r2; r > r2 Y r <= r2; r >= r2 Y Iterator Operations Operations Input *r Y r++; ++r Y

Output Forward Bidirecti Random onal Access Y Y Y Y Y Y Y Y Y

r--; --r r == r2; r != r2 *r = value Y Y Y Y Y Y Y Y

Y r[i] Y r += i; r -= i; Y r + i; r i; Y r r2 //# of items Y r < r2; r > r2 Y

r <= r2; r >= r2 Y STL Algorithms An STL algorithm is a template function that has iterators for its parameter types. generic because it is a template and works with iterators, not containers vector v; int myArray[100]; sort( v.begin(), v.end() ); sort( &myArray[0], &myArray[100] ); sort( myArray, myArray+100 ); // why 100? sort algorithm: template void sort ( RandomAccessIterator first, The range used is [first, last)

http://www.cplusplus.com/reference/algorithm/ RandomAccessIterator last); Vector Class Generalize the concept of an array index: 0 to #elements 1 but growable! implemented with a dynamic array has random access iterator #include using namesapce std; vector nums(100); // array of 100 integers, initialized to 0 Operations:

operator[] does not do bound checking at(index) access item; throws out_of_range exception operator== returns true if two vectors are the same size() # of elements in the vector push_back(item) adds item to the end of the vector pop_back() deletes the element at the end of the vector front() returns a reference to the first element in the vector back() returns a reference to the last element in the vector http://www.cplusplus.com/reference/vector/vector/ Vector Class Be aware: Modifying a container while iterating over it can

"invalidate" the iterator! erase(iterator) : removes item at iterator position insert(iterator, item): insert item before iterator Both erase and insert invalidate all iterators beyond the insert/erase point they result in reallocating the array Vector Class The following discussion is true in general to all containers: a vector pointer? need to delete the pointer if pointing at dynamically allocated vector object a vector of pointers? need to manually delete all dynamically allocated objects those pointers are pointing at before the vector goes out of scope const_iterator: for iterators over a collection that cannot be changed vector::const_iterator iter;

(*iter).Print(); // it has to be a const function! // or // iter->Print(); array Class Introduced in c++11 fixed-size sequence container begin(), end(), size(), empty(), front(), back(),swap() Zero-sized arrays are valid, but they should not be dereferenced Benefits over built-in array: Allow the use of c++ container operations. Provide bound check Function Objects Apply an operation to each of the elements in the range of a container template Function for_each (InputIterator first, InputIterator last, Function fn); Sort a range of element in a container in descending order:

template void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); Function object or functor: any object for which the function call class Double operator is defined. { public: int operator() ( int i ) { return 2*i; } }; ... Double f; int n = f(15); // n becomes 30 deque Class double-ended queue: First or Last In, First or Last Out very similar as a vector: provides fast random access into sequences of varying length. Differences from a vector:

provide fast insertion and deletion at both ends of the collection O(1) by providing unused reserve on both ends vector is fast only at the back Memory allocation is not guaranteed to be contiguous. accessing items in a deque tends to be slower than in a vector accessing elements in a deque by offsetting a pointer to another element may cause undefined behavior. Any insertion or deletion other than the ends invalidates all iterators to the deque. When to use deque? people wait in line. front gets served, end loses patience and leaves. http://www.cplusplus.com/reference/deque/deque/ list Class template for a doubly linked list has bidirectional iterator cheap insertion/deletion, O(i) to access item i

Inserting into a list while iterating over it is safe. If iter is an iterator, executing erase(iter) invalidates iter (and any iterator equal to iter) Erasing other positions is fine; if xs is a list: iterator y = x; x++; xs.erase(y); invalidates y but not x The list member functions merge, reverse, unique, remove, and remove_if have been optimized. http://www.cplusplus.com/reference/list/list/ forward_list Class Introduced in c++11 Designed with efficiency in mind Implemented using singly linked list Slightly more efficient insert/delete Can only use forward iterators No size() method (use distance algorithm to get the size in linear time)

http://www.cplusplus.com/reference/forward_list/forwa rd_list / stack Adaptor An adaptor does NOT directly implement the structure; instead, it provides a new interface for an existing container. By default, stack adapts deque : LIFO #include Operations: empty, pop, push, size, top, swap comparison ( <, >, <=, >=, ==, != ): lexicographical the first pair of element that are unequal determines the comparison result queue Adaptor By default, queue adapts deque: FIFO #include

Operations: empty, back, front, pop, push, size, emplace, swap comparison( <, >, <=, >=, ==, != ) priority_queue Adapter #include similar with queue: push() means enqueue pop() means dequeue different from queue: reordering right after enqueue to ensure the highest priority item is always at the front of the queue. Operations empty, pop, push, size, top, emplace, swap Example: job queue on a Linux server

Priority Queue Implementation Unsorted list enqueue: insert at the end of the list O(1) dequeue: search and fetch the highest priority item O(n) Array based sorted list enqueue: insert and keep the order O(n) dequeue: fetch the last item O(1) Sorted linked list enqueue: insert and keep the order O(n) dequeue: fetch the first item O(1) Binary search tree enqueue: insert and keep the order O(log2n) dequeue: fetch the last item O(1) string Class string is not part of STL, but is part of the standard library.

need to #include besides the operations we have learned, string has many other operations similar to STL containers: begin, end, clear, front, back, at, insert, erase, push_back, pop_back, ... http://www.cplusplus.com/reference/string/string/ Associative Containers The associative containers can be grouped into two subsets: maps and sets. Map, aka dictionary, consists of a key/value pair: key: used to order the sequence value: associated with that key map, multimap (allow multiple keys ) unordered_map, unordered_multimap store elements as a hash table to improve search time (c++11)

Set: an ascending container of unique elements set, multiset (allow multiple instances of an element) unordered_set, unordered_multiset (c++11) set Class an ascending container of unique elements < must be defined O(log2 n) insertion, deletion bidirectional iterator implemented based on balanced binary search tree (like a red-black tree): sorted the only thing that invalidates an iterator is an erase on that iterator: similar as list Operations:

size, empty, begin, end, find, lower_bound, upper_bound insert, erase http://msdn.microsoft.com/en-us/library/e8wh7665(v=vs.110).aspx Red-Black Tree A type of self-balancing binary search tree Rules for red-black trees (Data Structres and the STandard Template Library, William J. Collins, McGrawHill, 2003) all nodes are colored red or black if an item is red, its parent must be black the number of black items must be the same in all paths from the root item to an item with no children or with one child Maximum height is less than 2 log2 n a red-black tree demo std:: pair template struct pair; This class couples together a pair of values, which may be of different types (T1 and T2). The individual values can be accessed through its public

members first and second. Used a lot in stl set and map. multiset Class used when more than one instances of an element is possible The value serves as the key erase ( key_value ): returns the number of elements erased equal_range: returns a pair of iterator < upper_bound, lower_bound> map Class Each element is a pair of key and value. Sorted: key is unique and used to sort the data. Use bidirectional iterator.

implemented as balanced binary search tree the only thing that invalidates an iterator is an erase on that iterator: similar as list Operation begin, end, find, at, count, equal_range insert, erase Operator[]: mapobject[key] return the corresponding value multimap is used when the key is not necessarily unique. unordered_map & unordered_set Unordered sets/maps are containers that store unique elements in no particular order, and allow for fast retrieval of individual elements based on their keys (with a constant average time complexity on average).. Internally, the elements in the unordered_set are organized into buckets depending on their hash values generally less efficient for range iteration through a

subset of their elements. Both use forward iterators. Choosing Containers The choice of container type should be based in general on the type of searching and inserting required by the application. Use vector to manage a sequence if: random access to any element is at a premium insertions or deletions of elements are only required at the end of a sequence. Use deque if you want to use vector but also need to do insertion/deletion at the front of a sequence. Use list if need to do merge, reverse, unique, remove, and remove_if Associative containers are optimized for the operations of lookup, insertion and removal. Set/map: O(log2N) insertion/deletion. Unordered_set/unordered_map: O(1) average case. Insertion doesnt invalidate iterators; deletion only invalidates iterators pointing to the elements to delete.

Recently Viewed Presentations

  • Office 2010 Overview - SharePoint

    Office 2010 Overview - SharePoint

    Easily access rich client/server capabilities with the Backstage view in Office 2010 *Microsoft Office Communicator "14" and Microsoft Office Communications server "14," scheduled to release in the second half of 2010, will be required for this functionality.
  • Settlement and Integration of LGBTQ+ Newcomers to Canada

    Settlement and Integration of LGBTQ+ Newcomers to Canada

    Health, literacy, official language ability, education - due to their pre-migration conditions. Delayed access to the labour market and citizenship is an issue. Trafficked victims. and some. undocumented migrants . are more likely to: Experience abuse, isolation and dangerous situations.
  • Insert school logo Yr 3 Naplan Preparation Numeracy

    Insert school logo Yr 3 Naplan Preparation Numeracy

    Yr 3 Naplan Preparation - Numeracy. Facts, tips and hints for doing the Numeracy paper. Insert school logo. This powerpoint and questions are for the use of classroom teachers only.
  • Happy Halloween!! - Amphitheater Public Schools

    Happy Halloween!! - Amphitheater Public Schools

    Classwork Monday, October 31, 2016. I wanted to take a break from The Crucible today and enjoy a Halloween article…. Read the article and think about your Halloween memories. Write about your best costume as a kid or an adventure...
  • CAMPBELL BIOLOGY IN FOCUS URRY  CAIN  WASSERMAN  MINORSKY

    CAMPBELL BIOLOGY IN FOCUS URRY CAIN WASSERMAN MINORSKY

    Deposit a matrix of collagen and calcium phosphate: hardens into the mineral ... Their salt glands allow these animals to gain net water intake by drinking seawater. ... filtered fluid, called the filtrate, contains waste products along with water, electrolytes,...
  • H-E-B Workshop

    H-E-B Workshop

    Gen Y shoppers with children in the HH more "middle class", more likely to be home owners, and live in a smaller market.
  • Chapter 3: Producing Data - DePaul University

    Chapter 3: Producing Data - DePaul University

    Experimental Units, Subjects, Treatments. An experiment is a study in which we actually do something (a treatment) to people, animals, or objects (the experimental units) to observe the response. Here is the basic vocabulary of experiments. An . experimental unit...
  • Population Biology - LAMBERTH APES

    Population Biology - LAMBERTH APES

    Population Biology. AP Environmental Chapter 6. Dynamics of Population Growth. A population is defined as the number of an individual species at a given time in a defined area. Populations are dynamic meaning that a number of factors cause the...