Algorithms & Data Structr
Algorithms & Data Structr CSE 382
Popular in Course
Popular in Computer Engineering
This 16 page Class Notes was uploaded by Amelie Murphy on Wednesday October 21, 2015. The Class Notes belongs to CSE 382 at Syracuse University taught by Staff in Fall. Since its upload, it has received 29 views. For similar materials see /class/225568/cse-382-syracuse-university in Computer Engineering at Syracuse University.
Reviews for Algorithms & Data Structr
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/21/15
H N STL Containers Supplementary Notes Jim Fawcett CSE 687 Spring 2002 Every container allocates and manages its own storage Type de nitions common to all containers valuetype type of values held in container reference valuetypeamp constreference iterator constiterator reverseiterator constreverseiterator differencetype sizetype difference between iterators size of container Member functions common to all containers 00 Cc C c2c1 C cbegin cend crbegin crend c1 c2 c1 c2 csize c maxsize cempty c1 lt c2 c1 gt c2 c1 lt c2 c1 gt c2 c1 c2 clswapc2 default constructor copy constructor destructor returns an iterator to first element returns an iterator after last element returns a reverse iterator to last elem returns a reverse iterator before first elem equality comparison for same type cont returns number of elements in cont returns size of largest number of elements returns true if cont is empty lexicographic comparison assignment operation swaps two containers P 0 Sequence containers vector simulates an expandable array occupying contiguous memory list based on doubly linked list deque a double ended queue which uses a directory managing blocks of contiguousmemory Member functions common to all sequence containers Cnt Citer l iterZ Cinsertitert cinsertiternt cinsertiter l iterZ iter3 ceraseiter ceraseiter l iterZ constructs a sequence of 11 copies of t constructs a sequence equal to the range iterliter2 inserts a copy of t before iter Returns an iter to t inserts 11 copies of t before iter inserts the sequence iter2iter3 before iterl erases the element pointed to by iter erases elements in range iterliter2 Invalidation of iterators Invalidation of iterators into vectors insertion in a vector invalidates iterators from the point of insertion to the end ofthe vector if insertion causes reallocation to provide more memory then all iterators become invalid erase invalidates all iterators at and past the point of erasure a safe strategy is to assume that any iterator into a vector becomes invalid after either insertion or erasure Invalidation of iterators into deques insertion and erasure in the interior invalidates all iterators Invalidation of iterators into lists list insertions never invalidate iterators and erase invalidates only iterators pointing to the erased items Use of invalid iterators The only safe things you can do with an invalid iterator is to reinitialize it by assigning a new iterator value to it or destroy it Sorted associative containers all are based on balanced redblack tree set set of elements sorted by value with no duplicates multi set set of elements sorted by value with duplicates map set of ltkeyvaluegt pairs sorted on key with no duplicates multi map set of ltkeyvaluegt pairs sorted on key with duplicates Types common to all sorted associative containers Ckeytype type of keys used to instantiate C Ckeycompare type of the comparison type used to instantiate C Cvaluecompare type for comparing objects of Cvaluetype Invalidation of iterators with associative containers insertion does not invalidate any iterators referring to container elements erasure invalidates only iterators pointing to erased elements Member functions common to all sorted associative containers C Ccomp Citer1iter21 Citer1iter2comp ckeycomp Cvaluecomp cinsertt cinsertitert cinsertiter1iter2 cerasekl ceraseiter ceraseiter1iter2 cfindk1 ccountkl clowerboundkl cupperboundkl cequalrangekl void constructor constructs empty container using comp for comparisons constructs empty container and inserts elements from iter1iter2 into it same as above except that comp is used for comparisons returns c s key comparison object returns c s value comparison object for sets and maps inserts t if and only if there is no equivalent key stored returns pairltiteratorboolgt The bool indicates if insertion succeeded and iterator points to the element equivalent to t for multi sets and multi maps inserts t and returns an iterator pointing to the inserted t same as above except that iter is a hint about where to start search inserts elements from the sequence iter1iter2 erases all elements in the container with key equal to kl Returns the number of elements erased erases the element pointed to erases all elements in the range iter1iter2 returns an iterator pointing to an element with key equal to k1 or to cend if no such element is found returns the number of elements with key equivalent to k1 returns an iterator pointing to first element with key not less than k1 returns an iterator pointing to first element with key greater than kl returns a pair of iterators with first lowerbound and second upperbound S TL I tera tors ll Iterators extend the functionality of native pointers Any container c defines valid iterators pointing to the first element returned by cbegin and one past the last element returned by cend an iterator range is a pair of iterators that serve as the beginning and end markers of some operation on container values Range iter1 iterZ includes the values pointed to by iterl through the value pointed to by the predecessor of iterZ iterators can be dereferenced eg if iter is an iterator for some container c iter returns valuetype whenever it is in the range cbegin cend if iter is in the range cbegin cend then either iter stays in the range or is equivalent to cend iterators can be mutable or constant depending on whether the result of operatorquot acts like a reference or a reference to a const 12 Input iterator requirements Ii copy constructor i j returns true if iterator i is equivalent to iteratorj i j returns true if and only ifi j returns false i returns valuetype if dereferenceable Ifi j then it must be true that i j Note don t attempt to write to i as it may not be an l value i gtm equivalent to im i returns an iterator pointing to the successor element to i or to cend i returns i then points to the successor of i or to cend Algorithms that use input iterators should be single pass 13 Output iterator requirements Ii copy constructor i t tis assigned through the iterator i returns an iterator pointing to the successor element to i or to cend i returns i then points to the successor of i or to cend The only valid use of i is on the left of an assignement Algorithms that use output iterators should be single pass 14 15 IO 11 ij ij ij 1 Forward iterator requirements void constructor result may be a singular value result must satisfyi Ii true ifi is equivalent to j true if ij is false result must satisfy i j returns valuetype if dereferenceable If i j then i j must be true Ifi is mutable then i t is valid equivalent to im returns an iterator pointing to the successor element to i or to cend i j and i dereferenceable implies that i j returns i then points to the successor of i or to cend Bidirectional iterator requirements meets all requirements of Forward iterators 1 Assume that there is a j such that j i Then i refers to the same element asj It must be true that i i and if i j then i j returns i then points to the predecessor of i 16 Random access iterator requirements 1n in 1n i n 1j in iltj igtj meets the requirements for a bidirectional iterator the result must be equivalent to incrementing i n times returns an iterator equivalent to i n the result must be equivalent to decrementing i n times returns an iterator equivalent to i 11 returns a value of type distance Ifi n j thenj 1 11 equivalent to i 11 must be a total order relationship returning bool must be a total order relationship returning true wheneveri lt j i j is false must be a total order relationship equivalent to i gt j must be a total order relationship equivalent to i lt j 139 Algorithms Non modifying Prata C Primer Plus Third Edition Waite Group foreach Applies a non modifying function object to each element in a range find Finds the first occurrence of a value in a range findif finds the first value satisfying a predicate test criterion in a range findend finds the last occurrence of a subsequence whose values match the values of a second sequence Matching may be by equality or by applying a binary predicate findfirstof Finds the first occurrence of any element of a second sequence that matches a value in the first sequence Matching may be by equality or be evaluated with a binary predicate adj acentfind Finds the first element that matches the element immediately following it Matching may be by equality or evaluated with a binary predicate count Returns the number of times a given value occurs in a range countif Returns the number of times a given value matches values in a range with a match determined by using a binary predicate mismatch Finds the first element in one range that does not match the corresponding element in a second range and returns iterators to both Matching may be by equality or be evaluated with a binary predicate Equal Returns true if each element in one range matches the corresponding element in a second range Matching may be by equality or evaluated with a binary predicate search Finds the first occurrence of a subsequence whose values match the values of a second sequence Matching may be by equality or by applying a binary predicate searchn Finds the first subsequence of n elements that each match a given value Matching may be by equality or applying a binary predicate Example template ltclass Tgt class Sum Sum sumi0 l void operatorTamp t sumi t result return sumi private T sumi stdlistltintgt li push on some elements foreach is the only algorithm that returns its operation eg Sum int sum foreachlibeginliendSumresult 18 Algorithms Modifying Prata C Primer Plus Third Edition Waite Group COPY Copies elements from a range to a location identified by an iterator copybackward Copies elements from a range to a location identified by an iterator Copying begins at the end of the range and proceeds backwards Swap Exchanges two values stored at locations specified by references Swapranges Exchanges corresponding values in two ranges iterswap Exchanges two values stored at locations specified by iterators transform Applies a function object to each element in a range or to each pair of elements in a pair of ranges copying the return value to the corresponding location of another range replace Replaces each occurrence of a value in a range with another value replaceif Replaces each occurrence of a value in a range with another value if a predicate function object applied to the original value returns true replacecopy Copies one range to another replacing each value for which a predicate function object is true with an indicated value fill Sets each value in a range to an indicated value filln Sets 11 consecutive elements to a value generate Sets each value in a range to the return value of a generator which is a function object that takes no arguments generaten Sets the first 11 values in a range to the return value of a generator which is a function object that takes no arguments remove Removes all occurrences of a value from a range and returns a past the end iterator for the resulting range removeif Removes all occurrences of values for which a predicate object returns true from a range and returns a past the end iterator for the resulting range removecopy Copies elements from one range to another omitting elements that equal a specified value removecopyif Copies elements from one range to another omitting elements for which a predicate function object returns true unique Reduces each sequence of two or more equivalent elements in a range to a single element uniquecopy Copies elements from one range to another reducing each sequence of two or more equivalent elements to one reverse Reverses the elements in a range reversecopy Copies a range in reverse order to a second range Rotate Treats a range as a circular ordering and rotates the elements left Rotatecopy Copies one range to another in a rotated order Randomshuf e Randomly rearranges the elements in a range partition Places all the elements that satisfy a predicate function object before all elements that don t Stable partition Places all the elements that satisfy a predicate function object before all elements that don t The relative order of elements in each group is preserved 19 Sorting 8 Related Operations Prata C Primer Plus Third Edition Waite Group sort Sorts a range stablesort Sorts a range preserving the relative order of equivalent elements partialsort Partially sorts a range providing the first 11 elements of a full sort partialsortcopy Copies a partially sorted range to another range nthelement Given an iterator into a range finds the element that would be there if the range were sorted and places that element there lowerbound Given a value finds the first position in a sorted range before which the value can be inserted while maintaining the ordering upperbound Given a value finds the last position in a sorted range before which the value can be inserted while maintaining the ordering equalrange Given a value finds the largest subrange of a sorted range such that the Vlue can be inserted before any element in the subrange without violating the ordering binarysearch Returns true if a sorted range contains a value equivalent to a given value and false otherwise merge Merges two sorted ranges into a third range in placemerge Merges two consecutive sorted ranges in place includes Returns true if every element in one set also is found in another set setunion Constructs the union of two sets which is a set containing all elements present in either set setintersection Constructs the intersection of two sets which is a set containing only those elements found in both sets setdifference Constructs the difference of two sets which is a set containing only those elements found in the first set but not the second setsymmetricdifference Constructs a set consisting of elements found in one set or the other but not both makeheap Converts a range to heap pushheap Adds an element to a heap popheap Removes the largest element from a heap sortheap Sorts a heap min Returns the lesser of two values max Returns the greater of two values minelement Finds the first occurrence of the smallest value in a range maxelement Finds the first occurrence of the largest value in a range lexicographiccompare Compares two sequences lexicographically returning true if the first sequence is lexicographically less than the second and false otherwise next permutation Generates the next permutation in a sequence previous permutation Generates the preceding permutation in a sequence 20 Predefined Function Objects Iosuttis C Standard Library AddisonWesley Effect Example stdlistltintgt ii push on some elements stdlistltintgtiterator itPos find first positive element in list itPos findiiflibeginliendbindangreaterltintgtO
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'